哈希函数是一个映像,把任意长度的输入,通过Hash算法变换成固定长度的输出,这个输出就是Hash值;
当两个不同的输入,产生了同一个输出值即为哈希冲突
这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。
线性探测法:在ThreadLocalMap中使用;
该方法一次探测下一个地址,直到有空的地址后插入,若整个空间都找不到空余的地址,则产生溢出;
优点:只要哈希表还有位置,通过不断的探测,总能找到合适的位置。
缺点:
1.是探测的次数不可控,一旦探测次数骤增,会严重影响哈希表的读写性能;
2.删除比较麻烦;
将哈希码对应一个链表,插入元素时,如果哈希码冲突了,就将元素插入到链表,可选头插或尾插。
查询时,遍历哈希码对应的链表。
HashMap采用的就是这种方式。
优点:处理简单,容易删除,只需要简单地删去链表上相应的结点即可;
缺点:一旦哈希冲突多了,哈希表会退化成链表,查询效率会从O(1)变为O(n)。JDK8的HashMap针对这种情况有做优化,冲突超过8个会将链表转换为红黑树,提高查询效率。
采用哈希函数,而不是一个;
如果第一个哈希函数计算的哈希码发生冲突了,就采用第二个哈希函数重新计算哈希码,直到不冲突为止;
查询时也是一样,依次调用不同的哈希函数计算哈希码,直到Key相等。
int hash = hash1(key)、hash2(key)、hash3(key)......
缺点:这种方式会增加哈希计算的开销,影响读写的效率。
在创建哈希表的同时,再额外创建一个公共溢出区,专门用来存放发生哈希冲突的元素。查找时,先从哈希表查,查不到再去公共溢出区查。
缺点:哈希冲突多了,公共溢出区会膨胀的非常厉害,查询的效率也有影响。