Hash在编程中的应用（一）

Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string. Hashing is used to index and retrieve items in a database because it is faster to find the item using the shorter hashed key than to find it using the original value. It is also used in many encryption algorithms.

——— SqlServer Essential Guide

这是一段摘于SqlServer的对于Hash的定义。

Hash（散列）定义上来讲：是将任意长度的字符串转换成有限（更短）的固定长度字符串，作为表示原始字符串的键。散列常用于索引和检索数据库，也常用于一些加密算法。

再通俗一点：用一个唯一的，特定的值来代表任意的数据，类比于人的基因序列，人的指纹等可以作为人的唯一标识。

因此，需要一个函数来生成键 , 这样函数又被称作为Hash函数。

特性

一个优秀的hash函数算法，它应该具有如下4个特性：

1. 正向快速：

原始数据需要在有限时间和有限资源内计算出hash值。

2. 逆向困难：

给定一个hash值，在有限时间内很难（基本不可能）逆推出原始数据。

3. 输入敏感：

原始数据修改一点信息，产生的hash值都应该不相同。

4. 冲突避免：

所谓冲突，指的是两段不同的原始数据，他们通过转换得到的hash值一样。冲突避免，则是任意的两个数据，其hash相同的可能性极小。

当然，在不同的使用场景，无法让每个特性都完美满足，在不同的领域，可能会对某一些特性有所侧重。

一个简单的hash算法

大家多多少少都接触过Java，以JDK中String.hashCode方法为例，源码如下：

上面代码就是使用最简单的乘法迭代算法实现获取唯一的hash值，最后的值如果用数学表达式来表示，则为：

hashCode在Java中的应用

在上面我们提到过，hash函数算法会有一定的冲突情况，比如在字符串的hashCode计算过程中，会出现两个不同的字符串但hashCode一样的情况，例如：

除了上述两种情况，还有很多冲突的案例，大家可以写代码尝试一下。

那问题来了，既然hashCode并不能完全表示唯一性，那Java中用什么来比较两个字符串，对象呢？hashCode还有什么作用呢？

equals

在Java中，我们比较字符串，比较对象，用的方法常常是，我们摘录equal重点部分：

我们看到，equals 对字符串做了严格字符级别比较，可以保证完全相同。

equals v.s. hashCode

由上面的分析，我们得出一下两个结论：

1.相等的两个对象他们的肯定相等，也就是用对比是绝对可靠的。

2.相等的两个对象他们的不一定相等，也就是不是绝对可靠的。

但，如果所有的比较都使用equal去比较，显然效率太低，所以解决方案是：

每当对比的时候，首先用hashCode去对比，如果hashCode不一样，则表示两个对象不相等。如果hashCode相同，此时再对比进行equal比较，如果equal相同就是真的相同。

HashSet, HashMap, HashTable

在Java 容器中（Set，Map，Table），经常会用到key值的检索，所以提供了，，三种具体实现方案，利用上面我们重点标注的解决方案【先hashCode，后equal比较】，可以大大提高对比检索效率。