hash.md

引导

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

以上来自百度百科的粘贴，说的形象点就可以当成大范围映射小范围，也可以说给大范围做分组，有点像机器学习中的卷积层的概念，不过相比之下，Hash散列更加简单，例如对010的数组做Hash散列到03的范围中，我们只需要简单几行代码就可以做到：

for(int index = 0; index < 10; index ++){
	System.out.println(index + " & 3 = " + (index & 3));
}

控制台打印结果为：

0 & 3 = 0
1 & 3 = 1
2 & 3 = 2
3 & 3 = 3
4 & 3 = 0
5 & 3 = 1
6 & 3 = 2
7 & 3 = 3
8 & 3 = 0
9 & 3 = 1

结果值可以看出，我们的目的达到了，当然，Hash函数的实现不可能这么单调，它有着很多种实现：

• 直接取余法：f(x):= x mod maxM ; maxM一般是不太接近 2^t 的一个质数。
• 位运算法：f(x):= x & maxM。
• 乘法取整法：f(x):=trunc((x/maxX) * maxlongit) mod maxM，主要用于实数。
• 平方取中法：f(x):=(x*x div 1000 ) mod 1000000); 平方后取中间的，每位包含信息比较多。
• 直接定址法：直接以关键字k或者k加上某个常数（k+c）作为哈希地址。
• 数字分析法：提取关键字中取值比较均匀的数字作为哈希地址。
• 分段叠加法：按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
• 伪随机数法：采用一个伪随机数当作哈希函数。

当然，站在使用者的立场，我们只需要将Hash的特性用于正确的位置即可，在HashMap的实现中，则使用的是位运算法，相比于直接取余，位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快，位算法的实现如下：

7 & 33 = 1 过程如下

  000111(B)
& 100001(B)
——————————
  000001(B)

000001(B) = 1(D)

其他算法我们在开发日常中也常有用到，例如负载均衡、分库分表都依赖Hash来完成。

Hash冲突

假如我们将100个数做Hash之后存储在10个不同的容器中，必定会出现多个元素分布在同一个容器中，这种现象我们称之为：Hash冲突，而我们该如何解决Hash冲突呢？以下有几种处理方式：

链地址法

HashMap默认采用这种方式，将冲突的元素以链表的形式串起来，搜索的时候遍历该链表即可：

table-1：a -> b -> c -> d -> null
table-2：e -> f -> null
table-3：g -> h -> i -> null
table-4：null
......

开放定址法

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

Hi=（H（key）+di）% m i=1，2，…，n

其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。

再hash法

类似于开放定址法，只不过这里会实现构造多个不同的哈希函数，如果发生冲突了，则会根据顺序调用下一个hash函数，以此类推，直到不冲突或者分配完毕为止。

建立一个公共溢出区

将冲突的都放进去

总体看来，还是链地址法更加靠谱，在JDK1.8中的HashMap实现中，选用的就是这种方式，只不过在链表达到一定长度的时候会转为红黑树，优化了查询效率！！