解决hash冲突的方法

参考文章:解决hash冲突的方法

一）哈希表简介

非哈希表的特点：关键字在表中的位置和它之间不存在一个确定的关系，查找的过程为给定值一次和各个关键字进行比较，查找的效率取决于和给定值进行比较的次数。

    哈希表的特点：关键字在表中位置和它之间存在一种确定的关系。

哈希函数：一般情况下，需要在关键字与它在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。

hash : 翻译为“散列”，就是把任意长度的输入，通过散列算法，变成固定长度的输出，该输出就是散列值。

这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。

           简单的说就是一种将任意长度的消息压缩到莫伊固定长度的消息摘要的函数。

hash冲突：就是根据key即经过一个函数f(key)得到的结果的作为地址去存放当前的key value键值对(这个是hashmap的存值方式)，但是却发现算出来的地址上已经有人先来了。就是说这个地方要挤一挤啦。这就是所谓的hash冲突啦

二）哈希函数处理冲突的方法

其中 m 为表的长度

对增量di有三种取法：

线性探测再散列   di = 1 , 2 , 3 , ... , m-1

平方探测再散列   di = 1 2 , -12 , 22 , -22 , 32 , -32 , ... , k2 ,  -k2

2）链地址法

先按照ppt上的hash算法：h(key) = key % 7，算出来对应的hash值，这个hash值暂时就决定，当前的这个值，存放在数组的位置。

都算完之后，就可以，按照这个hash值，依次的，把这些数，都放在下面的数组上。然后就有我自己的这个截图。

和上面的ppt推算的是一致的。

这个做法就是Java的HashMap就是这么实现的，简单的解释下，这个HashMap源码的这个链表产生机制。

在put()方法里面，最后部分有个如下的调用。

addEntry(hash, key, value, i);

解释下几个参数的意思：

1，hash：就是根据key算出来的一个值，源码是这么滴--int hash = hash(key);，

这个算出来的这个就相当于是身份证号码，可以唯一确定一个人一样，唯一确定这个map

2，key：key就是我们在往hashmap里面put键值对的时候的key，使用map的时候，不是可以根据key拿到value吗。

3，value：这个同上啦，就是存的键值对的值。

4，i：源码里面是这么滴--int i = indexFor(hash, table.length);实际意思就是这个键值对存放在底层数组的索引下标。

然后这个i，可以对应到ppt上的那个取模之后的值，也就是确定在数组上的下标。

虽然在put的时候，可能会出现扩容的问题，但是在这咱就不考虑这个，只考虑如何生成链表，以及链表上的键值对的顺序。

createEntry(hash, key, value, bucketIndex);

这个方法就是真正的在创建一个节点到数组上。

这几个参数是一样的，和上面解释的一样的意思。

3.再hash法，就是算hashcode的方法不止一个，一个要是算出来重复啦，再用另一个算法去算。反正很多，直到不重复为止咯。大师兄猜的

4.建立一个公共溢出区域，就是把冲突的都放在另一个地方，不在表里面。

总结一下的就是下面的四行字：

1.开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）

2.再哈希法

3.链地址法(Java hashmap就是这么做的)

4.建立一个公共溢出区