共计 2327 个字符，预计需要花费 6 分钟才能阅读完成。
明天在学习 hash 值的时候，忽然发现了这样的景象：
System.out.println("张小三".hashCode());//24152826
System.out.println("王精良".hashCode());//29448764而这重地和通话的哈希值却是一样的
System.out.println("重地".hashCode());//1179395
System.out.println("通话".hashCode());//1179395造成这样的状况都是因为哈希抵触，要了解到这一点，咱们接下来先说说哈希抵触以及如何解决哈希抵触
哈希抵触：哈希表其实就是一个寄存哈希值的一个数组，哈希值是通过哈希函数计算出来的，那么哈希抵触就是两个不同值的货色，通过哈希函数计算出来的哈希值雷同，这样他们存在数组中的时候就会发生冲突，这就是哈希抵触。
如何解决哈希抵触：
个别解决哈希抵触有以下四个办法：
1. 凋谢地址法
这种办法也称再散列法，其根本思维是：当关键字 key 的哈希地址 p =H（key）呈现抵触时，以 p 为根底，产生另一个哈希地址 p1，如果 p1 依然抵触，再以 p 为根底，产生另一个哈希地址 p2，…，直到找出一个不抵触的哈希地址 pi，将相应元素存入其中。
就是说当发生冲突时，就去寻找下一个空的地址把数据存入其中，只有哈希表足够大，就总能找到这样一个空的地址。Hi=（H（key）+di）% m i=1，2，…，n
其中 H（key）为哈希函数，m 为表长，di 称为增量序列。增量序列的取值形式不同，相应的再散列形式也不同。次要有以下三种：
线性探测再散列dii=1，2，3，…，m-1
这种办法的特点是：抵触产生时，程序查看表中下一单元，直到找出一个空单元或查遍全表。
二次探测再散列di=12，-12，22，-22，…，k2，-k2 (k<=m/2)
这种办法的特点是：抵触产生时，在表的左右进行跳跃式探测，比拟灵便。
伪随机探测再散列
di= 伪随机数序列。
具体实现时，应建设一个伪随机数发生器，（如 i =(i+p) % m），并给定一个随机数做终点。
例如，已知哈希表长度 m =11，哈希函数为：H（key）= key % 11，则 H（47）=3，H（26）=4，H（60）=5，假如下一个关键字为 69，则 H（69）=3，与 47 抵触。
如果用线性探测再散列解决抵触，下一个哈希地址为 H1=（3 + 1）% 11 = 4，依然抵触，再找下一个哈希地址为 H2=（3 + 2）% 11 = 5，还是抵触，持续找下一个哈希地址为 H3=（3 + 3）% 11 = 6，此时不再抵触，将 69 填入 5 号单元。
如果用二次探测再散列解决抵触，下一个哈希地址为 H1=（3 + 12）% 11 = 4，依然抵触，再找下一个哈希地址为 H2=（3 – 12）% 11 = 2，此时不再抵触，将 69 填入 2 号单元。
如果用伪随机探测再散列解决抵触，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为 H1=（3 + 2）% 11 = 5，依然抵触，再找下一个哈希地址为 H2=（3 + 5）% 11 = 8，此时不再抵触，将 69 填入 8 号单元。
2) 再哈希法
这种办法是同时结构多个不同的哈希函数：
Hi=RH1（key）i=1，2，…，k
当哈希地址 Hi=RH1（key）发生冲突时，再计算 Hi=RH2（key）……，直到抵触不再产生。这种办法不易产生汇集，但减少了计算工夫。
3）链地址法
这种办法的根本思维是将所有哈希地址为 i 的元素形成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因此查找、插入和删除次要在同义词链中进行。链地址法实用于常常进行插入和删除的状况。
4）建设公共溢出区
这种办法的根本思维是：将哈希表分为根本表和溢出表两局部，但凡和根本表发生冲突的元素，一律填入溢出表。
优缺点
凋谢散列表（open hashing）/ 拉链法（针对桶链构造）
1）长处：①对于记录总数频繁可变的状况，解决的比拟好（也就是防止了动静调整的开销）②因为记录存储在结点中，而结点是动态分配，不会造成内存的节约，所以尤其适宜那种记录自身尺寸（size）很大的状况，因为此时指针的开销能够忽略不计了 ③删除记录时，比拟不便，间接通过指针操作即可
2）毛病：①存储的记录是随机散布在内存中的，这样在查问记录时，相比结构紧凑的数据类型（比方数组），哈希表的跳转拜访会带来额定的工夫开销 ②如果所有的 key-value 对是能够提前预知，并之后不会发生变化时（即不容许插入和删除），能够人为创立一个不会产生抵触的完满哈希函数（perfect hash function），此时关闭散列的性能将远高于凋谢散列 ③因为应用指针，记录不容易进行序列化（serialize）操作
关闭散列（closed hashing）/ 凋谢定址法
1）长处：①记录更容易进行序列化（serialize）操作 ②如果记录总数能够预知，能够创立完满哈希函数，此时解决数据的效率是十分高的
2）毛病：①存储记录的数目不能超过桶数组的长度，如果超过就须要扩容，而扩容会导致某次操作的工夫老本飙升，这在实时或者交互式利用中可能会是一个重大的缺点 ②应用探测序列，有可能其计算的工夫老本过高，导致哈希表的解决性能升高 ③因为记录是寄存在桶数组中的，而桶数组必然存在空槽，所以当记录自身尺寸（size）很大并且记录总数规模很大时，空槽占用的空间会导致显著的内存节约 ④删除记录时，比拟麻烦。比方须要删除记录 a，记录 b 是在 a 之后插入桶数组的，然而和记录 a 有抵触，是通过探测序列再次跳转找到的地址，所以如果间接删除 a，a 的地位变为空槽，而空槽是查问记录失败的终止条件，这样会导致记录 b 在 a 的地位从新插入数据前不可见，所以不能间接删除 a，而是设置删除标记。这就须要额定的空间和操作。
