[数据结构与算法]如何解决哈希冲突？

1.什么是哈希冲突？

1.1哈希算法

哈希算法是将任意长度的输入通过散列算法变成固定长度的输出。

1.2哈希表

哈希表是通过key可以直接访问到key-value存储位置的数据结构，通过hash函数将key映射到表中的某个位置，来加快数据的查找。

1.3哈希冲突

不同的key可能计算出相同的hash值

哈希冲突就是当前key的计算出hash值找到的位置已经被占用了

2.解决哈希冲突

哈希冲突不能完全避免，只能尽可能降低发生冲突的概率。

2.1链地址法（拉链法）

HashMap中使用链地址法解决哈希冲突
扩展
HashMap如何解决哈希冲突？

1. 使用链地址法来连接具有相同hash值的数据

将哈希表中发生哈希冲突的位置做成链表，将相同哈希值的key使用链表连接，数组中存储链表的头结点。

1. 计算当前key的哈希地址若地址对应链表为空，将数据插入链表中，不为空执行2
2. 计算key的下一个哈希地址，若改地址对应链表不为空，使用头插法or尾插法将元素插入链表

2.2开放定址法

ThreadLocal中使用开放定址法解决哈希冲突

使用key计算hash地址p=hash(key),若发生冲突（该位置不为空），继续计算 p1,p2…，直到找到不冲突的哈希地址。

2.2.1线性探测法

• 如果hash(key) % m的位置已经被占用
  尝试(hash(key) +1) % m的位置，若也被占用
  尝试+2，+3…依次类推，直到找到空位置

2.2.2二次探测法

• 如果hash(key) % m的位置已经被占用
  尝试(hash(key) + 1^2) % m，若也被占用
  尝试(hash(key) + -(1^2))% m…直到找到空位置
  1²,-1²,2²,-2²,3²,-3²…

2.3再哈希法

发生冲突时，使用不同的哈希函数计算新的哈希地址，直到不再发生冲突。

• 第二个哈希函数的特点

  1. 不能和第一个哈希函数相同
  2. 不能输出0，会死循环

  公式：Hi = 常量 - （key % 常量）
  其中常量是小于数组容量的质数

2.4建立公共溢出区

为所有发生冲突的key，建立一个公共溢出区来存储。

1. 在查找时，计算出key的哈希地址
2. 先和基本表进行比对，如果相等查找成功
3. 若不相等，去公共溢出表中查找。

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系