数据结构_Hash 表

前言

Hash 表是一种可以快速插入和查找的数据结构，将数据保存在通过 hash 函数计算得到的下标中。

插入和删除 所需时间为 O(1)。在确定容量、无需遍历时效果最好。

当其大小接近容量时，效率会变得很差。

存储方式

Hash 表有两种存储方式

1. 开放地址法

   开放地址法，直接将数据存储在数组中。

   当 hash 算出的地址已经被占用时，则走过一定的步长找到另外一个空位（在填充质数很大时就会很耗时）并保存数据。

2. 链地址法

   链地址法，创建保存数据的数组，该数组中不直接保存数据，而是保存一个用来存储这些数据的链表，将数据项直接存储的链表中。

   当 hash 算法计算出的地址时，遍历数组中对应的链表找到空位并保存。

其中，开放地址法又分为 3 种实现：

• 线性探测

  每次前进的步长为 1

  即查找的位置依次是x + 1,2,3,4,5,……

  存储达到容量 2/3 以上时候读写性能会很差
  

• 二次探测

  每次前进的步长为当前查找次数的平方

  即查找的位置依次是x + 1,4,9,……

  当前几次找不到之后就会很恐慌，步长越来越大到后面无法继续下去
  

• 再哈希法

  每次前进的步长是根据另外一个 hash 算法计算出来的值

  这个算法要求如下：

  1. 与第一次 hash 输出不同
  2. 不能输出 0
  

  已经有一个公认的比较好的二次 hash 算法：

  stepSize = constant - (key % constant)
  如：stepSize = 5 - (key % 5)
  * constant 是小于数组容量的质数
  

比较

再哈希法 VS 二次探测法

在小型哈希表中，再哈希法比二次探测好；

但如果容量充足，并且容量大小不再变化时，二次探测效果好，在装填因子小于 0.5 时几乎没有性能损失

开放地址法 VS 链地址法

hash 表容器大小未知时，用链地址法比较好

当装填因子变得很大时，开放地址法性能下降很快，但链地址法只是线性下降。

源码

👉 点这里查看源码