文章目录
article
哈希函数
AI文章摘要
gemini-2.0-flash-lite
这篇文章介绍了哈希函数和哈希冲突。一个好的哈希函数需要高效快速，将键均匀映射到哈希表索引，最小化哈希冲突，并具有较低负载系数。文章介绍了除法哈希和乘法哈希两种方法。由于键的数量通常大于哈希表索引数量，因此哈希冲突是不可避免的。文章介绍了解决哈希冲突的两种方法：单独链接和开放寻址。开放寻址又包括线性探测、平方探测和双重哈希三种方法。双重哈希的时间复杂度为O(n)。
哈希函数
一个好的哈希函数需要满足以下要求：
- 高效快速
- 将键均匀的映射到哈希表的所有索引
- 最小化哈希冲突
- 较低负载系数
除法哈希(Division Method)
$h(k)=k \mod n$
或
$h(k)=(n-1)\ \& \ k$
乘法哈希(Multiplication Method)
$h(k)=\lfloor m * (kA \mod 1) \rfloor$
哈希冲突
键的数量要远大于哈希表索引的数量，哈希函数在对键值映射到哈希表索引时，时不可避免的会发生碰撞。哈希冲突对数据的增删和修改产生困扰。
单独链接(Separate Chaining)
哈希表每个单元指向一个链表，相同哈希值的元素存储在链表中。
开放寻址(Open Addressing)
开放寻址即元素仍存储在哈希表，发生哈希冲突时采用逐个探测的方法寻找空位置。
线性探测(Linear Probing)
从原始哈希位置往下线性探测，如果位置被占据则继续下探直至寻找到空位置。
- 计算键的哈希索引 $i=h(k)$。
- 若$ht[i]$不为空，则循环$i = (i+1) \% n$直至$ht[i]$为空。
- 存储数据$ht[i]=data$。
平方探测(Quadratic Probing)
从原始哈希位置往下以某个二次函数的步进跳跃探测寻找空位置。
- 计算键的哈希索引 $i=h(k)$。
- 若$ht[i]$不为空，则循环$i = (i+x^{2}) \% n, x=1,2,…,n-1$，直至$ht[i]$为空。
- 存储数据$ht[i]=data$。
双重哈希(Double Hashing)
双重哈希使用$h_1$和$h_2$两个哈希函数，使用$h_1$获取哈希索引，发生冲突时引入$h_2$结合处理。
- 计算键的哈希索引 $i=h_1(k)$。
- 若$ht[i]$不为空，则循环$i = h(k,i)=(h_1(k) + i*h_2(k)) \% n$。
- 存储数据$ht[i]=data$。
双重哈希的时间复杂度为：$O(n)$