哈希表

• 核心：地址 = $H(key)$。理想情况 $O(1)$。
• 装填因子 ($\alpha$)：$\alpha =\text{填入表中的元素个数}/\text{哈希表长度}$。
  • $\alpha$ 越大，发生冲突的可能性越大。
• 常用哈希函数：
  • 除留余数法：$H(key)=key(\mathrm{mod}p)$。（$p$ 通常取不大于表长的最大质数）。
• 冲突处理：
  1. 开放定址法：$H_i=(H(key)+d_i)(\mathrm{mod}m)$
     • 线性探测：$d_i=1,2,3,\dots$ (易产生“堆积”现象)。
     • 二次探测：$d_i=1^2,-1^2,2^2,-2^2,\dots$
  2. 链地址法 (Chaining)：冲突元素挂在链表中 (无堆积现象，平均查找长度较短)。