一，Motivation：Direct address table

1. Direct-address table 的背景

Direct-address table 是一种简单且高效的数据结构，适用于当记录的键（key）是整数且范围已知的情况。假设键的范围是 [U]={0,1,2,...,U−1}，即键是从 0 到 U−1 的整数。

2. 数据结构

Direct-address table 使用一个数组 T 来存储记录：

数组 T 的大小为 U，即键的最大范围。
每个数组的索引 T[i] 对应一个键 i。
如果键 i 有对应的记录，则 T[i] 存储该记录；否则 T[i] 为 NULL（表示没有记录）。

3. 优缺点

优点：

操作（插入、删除、查找）的时间复杂度都是 O(1)，非常高效。
适合键范围较小且稠密的情况。

缺点：

如果键的范围 U 很大，但实际使用的键很少，会浪费大量空间（因为数组大小固定为 U）。
不适合键稀疏或范围未知的情况。

优点	缺点
查找极快（O(1)）	空间极度浪费，除非 key 很稠密
适合小型稠密 key 集合	不适合 key 空间巨大的实际场景（比如身份证号、手机号、字符串、UUID等）

所以这就是为什么现实中我们更常用：哈希表

• 哈希表用哈希函数把大 key 空间压缩到小数组空间中

• 空间效率高

• 查找、插入时间仍然是期望 O(1)

二，不同数据的插入和查找时间复杂度对比分析

结构	插入效率	查找效率	适用场景	优缺点
Direct Addressing	O(1)	O(1)	key 空间小且稠密	空间占用极大
Ordered Array	O(n)	O(log n)	查找多插入少	插入搬移代价大
Ordered Linked List	O(n)	O(n)	很少使用	两头都慢
Unordered Array	O(1)	O(n)	插入多查找少	查找慢
Unordered Linked List	O(1)	O(n)	插入删除多	查找慢
Binary Search Tree	O(log n)	O(log n)	插入和查找都频繁	要保证树平衡

三，Denotion & Definition

①Denotion

②Definition

1. 什么是哈希函数？
哈希函数是一种将输入数据（键）映射到固定范围内的地址（哈希值）的函数。它的主要目的是将数据分布到一个有限大小的表（哈希表）中，以便快速查找、插入和删除。

2. 数值型键的简单哈希函数
对于数值型键，一个常见的简单哈希函数是：
Hash(Key)=Keymod TableSize

Key：输入的数值型键。
TableSize：哈希表的大小，通常选择为一个素数（prime number），以减少冲突（collisions）。

为什么选择素数？

素数作为表的大小可以有效减少键值之间的模式冲突，从而使哈希值分布更均匀。

【会考察的题型：某一题中U和m是什么？】

四，Collision

冲突（Collisions）：

• 当两个不同的键映射到同一个地址时，就会发生冲突。例如：
  • 键值 987654118 和 555555555 都映射到地址 1688。

五，Hash Table ADT

六，collision resolution 1:Chaining

①createTable(sizem)

Assume ℎ(x) hashes keys to the range[ 0, m− 1]
◦ Create an array of size m with each entry storing a linked list

伪代码：

hashtable←allocate an array of size sizem
for i from 0 to sizem-1
    hashtable[i] <- allocate an empty linkedlist//对于每一个位置都allocate一个空的linkedlist
return hashtable

②search

hashid = h(key)//通过哈希函数 h() 把 key 映射成数组的索引（也就是哪个槽位）。
node=hashtable[hashid].head.next//创建一个node节点，存储这个hashid名下的第一个数据
        while node != hashtable[hashid].tail//如果没有遍历到tail端
                if node.data.key == key//并且如果node的key值等于要寻找的key
                return node.data.value//那么我就返回这个node的value（node是一个结构体有key值和value值）
        node = node.next
return NULL

③insertion

④delete(hashtable, key)

hashid = h(key)
node=hashtable[hashid].head.next
while node != hashtable[hashid].tail
                if node.data.key == key
                        break
                node = node.next
if node != hashtable[hashid].tail//如果 node 没有匹配 key（即走到 .tail），那说明没找到，就什么都不做。
        delete_linkedlist(hashtable[hashid], node)

七，Collision Resolution 2：open addressing 开放寻址

方法	核心策略	存储位置
链地址法 chaining	冲突的值挂到链表上	存在链表里，在哈希表外
开放地址法 open addressing	冲突的值在表里找空位继续存	表内找空位，绝不出门！

①Linear Probing

1，缺点：Deficiency of linear probing： Long sequence of occupied slots, which degrades the query efficiency

②double probing

example：

八，Factor Load

Load factor α: the average number of elements stored in a chain

九，Uniform hashing 均匀哈希

Elements are equally likely to hash into any of the m slots

十，Chaining和Open addressing的优缺点

explanation：chaining对hash函数不敏感。

无论你选的 hash 函数质量好不好、冲突多不多，Chaining 都能忍、都能正常用，不容易挂。

而 Open Addressing 就很娇气，hash 函数稍微设计得不好、冲突一多，效率就迅速崩溃。

十一，什么样的 hash function 才算“好”？

 一个好的哈希函数满足 uniform hashing（均匀散列） 的特性：

每个 key 映射到任何一个 slot 的概率是一样的，和其它 key 映射的位置毫无关系。

这句话的意思是：

• 假设你有 m 个桶（槽位）

• 不管其它 key 落在哪，当前这个 key 有 1/m 的概率落到每个槽上

• 分布是完全均匀的、不偏不倚的

这就是理想状态，能最大限度地避免冲突（collision）

十二，2 hashing function：division and universal hashing

①Universal Hashing

1. 什么是 Universal Hashing（通用哈希）？

这是一个“随机选择哈希函数”的策略，不再死板用一个固定函数，而是：

❝ 从一个预先设计好的哈希函数家族 𝓗 中，随机地挑一个 来用！❞

这么做的目的是：

• 避免坏人预测冲突点（防攻击）

• 保证冲突概率低（数学上可以证明）

“𝓗 is called universal if:
对于任何两个不同的 key：
选一个函数 h ∈ 𝓗 的概率地保证：

Pr⁡[h(k1)=h(k2)]≤1m\Pr[h(k_1) = h(k_2)] \leq \frac{1}{m}Pr[h(k1​)=h(k2​)]≤m1​

 关键词是：任意两不同的 key，被哈希到同一槽的概率非常小，最多就是 1/m

你可以理解为：

 “即使我乱选两个 key，只要我用的是 universal hash 函数，那这两个 key 撞位置的概率也不大！”

通用哈希的使用方式是：

1. 在初始化的时候（比如程序刚开始）

2. 从 𝓗 里随机选一个函数 h（可能是通过随机 a、b 实现）

3. 后面所有操作（插入、查找、删除）都用这个固定的 h

 是“一次性随机”，不是“每个 key 随机一次”！！

universal hashing 最核心的优势——随机打乱、分散冲突、防止预测