最常用的解决方式有两种：
1.Open Addressing 开放性地址
（1）Linear Probing（线性探索）
就是如果一个值hash之后，放到了index1的位置，另一个值hash之后如果也是要放在index1的位置，那么就从index1的位置往下找第一个为空的地址，把这个值放进去。
从插入来看：
在最差的情况下，如果产生了非常多的冲突，它的时间复杂度可能会变为O(n)。
从查找来看：
最差情况下，也可能变为O(n)，因为要寻找的值hash之后，如果本应该放在index1的位置，但是index1的位置不是这个值，那么就会依次向下寻找，找到第一个为空的位置结束。
从删除来看：
删除也可能变为O(n)。
而且如果index1~index10都是原本应该存储在index1的位置的值，要删除的元素在index2的位置，那么删除index2的元素之后，这个位置就为空了，再次查找hash后应该存放到index1位置的值是就会出现问题。
解决办法是，在index2这个位置的元素删除之后，在index2的位置设置一个标识，删除之后把这个表示为设置为True，证明index2的位置之前存放过某个元素。
缺点：
操作的时间复杂度可能会变为O(n)
还有一个缺点是，如果原本应该存放在index1的若干个元素，现在存放到了index1~index10，那么另外一个hash后应该存放到index6位置的元素就无法存放在index6的位置了，这时这一块区域都会堵塞（primary clustering）。
（2）Quadratic Probing（二次探索）
使用平方，第一个元素存放在index1，第二个元素如果本应该也放在index1，那么就放在index1 + 1的平方的位置，也就是index2，下一个元素如果也要存放在index1，那么它先查找index1的位置，满了的话，继续查找index1 + 1的平方的位置，如果还是满的，就查找index1 + 2的平方的位置，如果为空，就存放在这里。
优点就是不会产生很大的堵塞（primary clustering），但是会产生一个secondary clustering，它出现的概率会远远小于primary clustering。
2.Separate Chain（链地址法）
如果第一个元素a，hash之后要存在2的位置
1|
2|a
3|
4|
如果元素b，hash之后也要存在2的位置，就把a和b变成一个链表，2中存储的是链表的头指针。
1|
2| ——> a——>b
3|
4|
这种情况下，如果链表很长，操作的时间复杂度也可能变为O(n)。
在Python中，字典使用的是Open Addressing的方式。
Java使用的是Separate Chain。
还有别的解决冲突的方式，参考：
解决哈希冲突的常用方法分析
数据结构与算法：hash冲突解决
补充：
如果字典原来可以放x个元素，现在已经存放了y个元素，那么当y/x叫做满载率，当满载率大于一个值的时候，就会把x扩充到原来的2倍。
在python中，这个值是三分之二，大约是0.66。
x扩充到原来的二倍之后，存在这片区域的元素的下标会产生变化，重新计算，这叫rehash，再哈希。
网友评论