链地址法(Separate Chaining):
当哈希冲突发生时,将具有相同哈希值的元素存储在一个链表中。哈希表中的每个槽位都是一个链表的头指针。当需要查找、插入或删除一个元素时,只需在对应哈希值的链表中进行操作。这种方法的优点是实现简单,但可能会导致链表过长,影响查找性能。开放寻址法(Open Addressing):
当哈希冲突发生时,通过一定的探测策略在哈希表中寻找一个空闲槽位来存储元素。开放寻址法有以下几种常见的探测策略:
- 线性探测(Linear Probing):当冲突发生时,从当前位置开始,按固定步长(通常为 1)线性地向后探测,直到找到一个空闲槽位。
- 二次探测(Quadratic Probing):与线性探测类似,但探测步长为二次函数(如 i^2),这样可以更快地找到空闲槽位,减少聚集现象。
- 双散列(Double Hashing):使用两个不同的哈希函数,当冲突发生时,根据第二个哈希函数计算探测步长。这样可以进一步减少聚集现象,提高查找性能。
再哈希(Rehashing):
当哈希冲突发生时,使用一个备用哈希函数重新计算哈希值。如果仍然发生冲突,可以尝试更多的备用哈希函数,直到找到一个空闲槽位。这种方法的优点是能降低聚集现象,但需要设计多个具有良好分布特性的哈希函数。如果问的是hashMap发生hash冲突后怎么解决?
hashMap没有解决hash冲突,而是当我们通过put(key, value)向hashmap中添加元素时,需要通过散列函数确定元素究竟应该放置在数组中的哪个位置,当不同的元素被放置在了数据的同一个位置时,后放入的元素会以链表的形式,插在前一个元素的尾部;(1.7是头插法,1.8后改为尾插法)