13 hash冲突怎么解决

vvEcho 2024-01-24 17:55:01
Categories: Tags:
  1. 链地址法(Separate Chaining):
    当哈希冲突发生时,将具有相同哈希值的元素存储在一个链表中。哈希表中的每个槽位都是一个链表的头指针。当需要查找、插入或删除一个元素时,只需在对应哈希值的链表中进行操作。这种方法的优点是实现简单,但可能会导致链表过长,影响查找性能。

  2. 开放寻址法(Open Addressing):
    当哈希冲突发生时,通过一定的探测策略在哈希表中寻找一个空闲槽位来存储元素。开放寻址法有以下几种常见的探测策略:

  1. 再哈希(Rehashing):
    当哈希冲突发生时,使用一个备用哈希函数重新计算哈希值。如果仍然发生冲突,可以尝试更多的备用哈希函数,直到找到一个空闲槽位。这种方法的优点是能降低聚集现象,但需要设计多个具有良好分布特性的哈希函数。

  2. 如果问的是hashMap发生hash冲突后怎么解决?
    hashMap没有解决hash冲突,而是当我们通过put(key, value)向hashmap中添加元素时,需要通过散列函数确定元素究竟应该放置在数组中的哪个位置,当不同的元素被放置在了数据的同一个位置时,后放入的元素会以链表的形式,插在前一个元素的尾部;(1.7是头插法,1.8后改为尾插法)