技术文档哈希表

哈希表

数据结构
内容

Intro

Hash Table 是一种Table ADT，将大型可变长度数据集（称为键，不一定是整数）映射为固定长度的较小整数数据集，这种映射也叫哈希函数(hash function) Table ADT至少要有三个操作：

  • Search(v):确定v是否存在于ADT中
  • Insert(v):将v添加到ADT中
  • Remove(v):从ADT中删除v

python dict/set

在 Python 里，dict（字典）和set（集合）底层实际上都用到哈希表(Hash Table)这一数据结构。它们的差别主要在于：

  1. 用途/逻辑结构不同
    • dict 是"键-值 (key-value)"的映射；
    • set 只存储"不重复的元素"本身，没有"值(value)"的概念。
  2. 用法场景不同
    • 如果你需要"根据键（key）快速查找对应值"或"存放一些键值对"，就应该用 dict；
    • 如果你只关心某些元素是否出现过、不想有重复，那用 set 就足够了。
  3. 底层实现相似
    • 无论是 dict 还是 set，在查询（membership test）、插入、删除上都能提供平均意义下的 O(1)O(1) 时间复杂度，因为它们都是基于哈希表来完成索引的。 因此，对于"判断数组里是否有重复元素"这种只需要判断"元素出现过没出现过"的场景，直接用 set 比较自然；如果要记录更多信息（例如出现次数、或要关联其他数据），可以通过 dict 来完成。两者本质都能视为哈希表的不同接口形态：set 是只有「键(key)」的哈希表，dict 是有「键-值(key-value)」对的哈希表。

Hash Function

Direct Addressing Table(DAT)

当整数键的范围很小时，例如 [0..M-1]，我们可以使用大小为M的初始空（Boolean）数组A，并直接实现以下表ADT操作：

  1. 搜索（v）：检查A [v]是true（填充）还是false（空），
  2. 插入（v）：将A [v]设置为true（填充），
  3. 移除（v）：将A [v]设置为false（空白）。 就是这样，我们使用小整数键本身来确定数组A中的地址，因此称为直接寻址。 很明显，所有三种主要的ADT操作都是O(1)。

Limitations

  • 键必须是（或可以轻松映射到）非负整数值。
  • 键的范围必须很小。 如果我们有（非常）大范围的话，内存使用量会（非常的）大。
  • 键必须密集，即键值中没有太多空白。 否则DAT将包含太多的空的（浪费的）单元。

Hashing

哈希函数的作用

  1. 将（一些）非整数（例如字符串）键映射成整数键，
  2. 将大整数映射成较小的整数。

构建哈希函数的目标

  1. 快速计算，即在O（1）中，
  2. 尽可能使用最小插槽/散列表的大小M，
  3. 尽可能均匀地将键分散到不同的基地址∈[0..M-1]，
  4. 尽可能减少碰撞。

哈希函数的参数

  • h[v]=v%M
  • M:哈希表的大小，通常是个质数（prime number）
  • 负载因子：load factor alpha=N/M

Hash String

int hash_function(string v) { // 假设 1: v 只使用 ['A'..'Z']
  int sum = 0;                // 假设 2: v 是一个短字符串
  for (auto& c : v) // 对于 v 中的每个字符 c
    sum = ((sum*26)%M + (c-'A'+1))%M; // M 是表大小
  return sum;
}

Hash Collision Resolution

Closed Addressing

Separate Chaining(SC) 分离链表法

  • 使用Doubly Linked Lists,如果两个键a和b都有相同的哈希值i，那么它们都将被添加到双向链表i的（前/后）（在这个可视化中，我们在O(1)的帮助下添加到尾部）
  • Insert(v):加到双向链表的最后， O(1)
  • Search(v): O(1+α) α是链长度
  • Remove(v): O(1+α)

Open Addressing

我们很快就会看到，这三种模式的探测序列是（发生碰撞时的移动）：

  • LP线性探测：i=(base+step* 1) % M，
  • QP二次探测：i=(base+step* step) % M，和
  • DH双重哈希：i=(base+step* secondary) % M。 所有三种 OA 技术都要求负载因子 α = N/M < 1.0 (否则无法进行更多的插入)。 所有使用开放寻址的 Search(v)，Insert(v) 和 Remove(v) 操作都将是 O(1)

Linear Probing(LP) 线性探测

h(v) // 基地址
(h(v) + 1*1) % M // 如果有冲突，第1步探测
(h(v) + 2*1) % M // 如果仍然有冲突，第2步探测
(h(v) + 3*1) % M // 如果仍然有冲突，第3步探测
...
(h(v) + k*1) % M // 第k步探测，等等...
  • Insert(v):i=(base+step* 1) % M 往后挪1位
  • Remove(v): 设置 HT [i] = DELETED
  • Search(v): Search(35) - [0,1（绕过那个DELETED cell），2,3（找到键35）]
  • Insert(v)：覆盖DELETE的值
Primary Clustering

连着的一串占用的地址

Quadratic Probing(QP) 二次探测

i=(base+step* step) % M

 h（v）//基地址
（h（v）+ 1 * 1）％M //第一个探测步骤，如果发生碰撞
（h（v）+ 2 * 2）％M //第2次探测步骤，如果仍有冲突
（h（v）+ 3 * 3）％M //第三次探测步骤，如果仍有冲突
...
（h（v）+ k * k）％M //第k个探测步骤等...
就是这样，探针按照二次方跳转，根据需要环绕哈希表。
QP的条件

定理 如果 α < 0.5 并且 M 是一个质数（> 3），那么我们总是可以使用（这种形式的）二次探测找到一个空的插槽。回忆：α 是负载因子，M 是哈希表的大小（HT.length）。

证明 这里证明了不同步数x，y不会落到同一个点 我们将通过矛盾使用证据。 我们首先假设两个二次探测步骤：x和y，x！= y（假设x h(v) + x* x = h(v) + y* y (mod M) //假设所有空槽都被占用 x* x = y* y (mod M)//从两边敲出h（v） x* x - y* y = 0 (mod M) //将y * y移动到左边 (x-y)* (x+y) = 0 (mod M)//重新排列公式 现在，（x-y）或（x + y）必须等于零。 我们的假设是x != y, 那么（x-y）不能为0. 由于0≤ x 矛盾！

如果出现重复，(x-y)* (x+y)=k* M 因为x != y ，0<x<y<M/2（这里用到了负载因子） 所以

  • x-y !=0
  • x+y < M 说明不会出现重复

为什么M需要是一个质数？

  • 如果M是质数， M=1* M
  • 如果M不是质数，M=p* q （x-y）或（x + y）可以是q的倍数/p的倍数，会导致某些步长更频繁发生
Secondary Clustering

二次探测产生的集群（不一定连续）

Double Hashing(DH) 双倍散列

为了减少主要和次要群集，我们可以修改探针序列为： i=(base+step* secondary) % M

  h（v）//基地址
（h（v）+ 1 * h2（v））％M //第一个探测步骤，如果有碰撞
（h（v）+ 2 * h2（v））％M //第2次探测步骤，如果仍有冲突
（h（v）+ 3 * h2（v））％M //第三次探测步骤，如果仍有冲突
...
（h（v）+ k * h2（v））％M //第k个探测步骤等...

就是这样，探测器根据第二个散列函数h2（v）的值跳转，根据需要环绕散列表。

h2(v)
  • 如果h2（v）= 1，则双散列（Double Hashing）的工作方式与线性探测（Linear Probing）完全相同。 所以我们通常希望h2（v）> 1来避免主聚类。
  • 如果h2（v）= 0，那么Double Hashing不起作用的原因很明显，因为任何探测步数乘以0仍然是0。
  • 通常（对于整数键），h2（v）= M' - v％M'其中M'是一个小于M的质数。这使得h2（v）∈[1..M']，它足够多样.