哈希表

散列表（Hash Table），又称哈希表。是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关，通过“散列函数（哈希函数）”：$Addr=H(key)$。

若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”

通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”

常见的散列函数

1. 除留余数法——$H(key)=key\%p$，散列表表长为$m$，取一个不大于$m$但最接近或等于$m$的质数$p$
2. 直接定址法——$H(key)=key$ 或$H(key)=a*key +b$，其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
3. 数字分析法——选取数码分布较为均匀的若干位作为散列地址，如手机号码。
4. 平方取中法——取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。如身份证号。

解决冲突

1. 拉链法：把所有“同义词”存储在一个链表中，Java中的HashMap、HashSet
2. 开放定址法：可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为：$H_{i}=\left(H(k e y)+d_{i}\right) \% m$，$i=0,1,2, \ldots, k \quad(k \leqslant m-1)$，其中$m$表示散列表表长；$d_i$为增量序列；$i$可理解为“第$i$次发生冲突”
   • 线性探测法：$d_{i}=0,1,2,3, \ldots, m-1$; 即发生冲突时，每次往后探测相邻的下一个单元是否为空
     • 线性探测法很容易造成同义词、非同义词的“聚集（堆积）”现象，严重影响查找效率
     • 产生原因——冲突后再探测一定是放在某个连续的位置
   • 平方探测法：当 $\mathrm{d}_{\mathrm{i}}=\mathbf{0}^{2}, \mathbf{1}^{2},-\mathbf{1}^{2}, \mathbf{2}^{2},-\mathbf{2}^{2}, \ldots, \mathbf{k}^{2},-\mathbf{k}^{2}$ 时，称为平方探测法，又称二次探测法其中 $\mathbf{k} \leq \mathbf{m} / \mathbf{2}$
     • 比起线性探测法更不易产生“聚集（堆积）”问题
     • 散列表长度m必须是一个可以表示成$4j+3$的素数，才能探测到所有位置
   • 伪随机序列法：$\mathbf{d}_{\mathrm{i}}$ 是一个伪随机序列，如 $\mathrm{d}_{\mathrm{i}}=\mathbf{0 , 5 , 2 4 , 1 1 , \ldots}$
3. 再散列法：除了原始的散列函数$H(key)$之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止：$\mathrm{H}_{\mathrm{i}}=\mathrm{RH}_{\mathrm{i}}(\mathrm{Key}) \quad \mathrm{i}=1,2,3 \ldots ., \mathrm{k}$

STL

• 无序集合：unordered_set
• 无序字典：unordered_map

练习

1. 洛谷——P4305 [JLOI2011]不重复数字：需要加快读
2. leetcode-1 两数之和 (简单)