哈希表的概念（散列表）

一、基本概念

散列表特点 ：
数据元素的关键字与存储地址直接相关

通过哈希函数建立“关键字”与“存储地址”的联系

若不同的关键字通过散列函数映射到同一个值，则称它们为 “同义词”
通过散列函数确定的位置已经存放了其他元素，则称这种情况为 “冲突”

---

二、常见散列函数

1. 除留取余法—H(key)=key%p
   表长为m，取不大于m但最接近或等于m的质数
2. 直接定址法—H(key)=a*key+b
   适合 关键字分布基本连续 的情况
3. 数字分析法—选取数码分布较为均匀的若干位作为散列地址
   
   4.平方取中法—取关键字的平方值的中间几位作为散列地址
   

散列查找是典型的 “用空间换时间” 的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。

三、处理冲突的方法

1.拉链法

用拉链法处理“冲突”：把所有“同义词”存储在一个链表中

2.开放定址法

空地址既对同义词开放，又向非同义词开放。其数学递推公式为
$$H_i=(H(key)+d_i)\%m$$
其中$i\in [0,m-1]$，m表示散列表表长，$d_i$为增量序列；H（key）表示初始地址；i理解为“第i次发生冲突”

(1) 线性探测法

$d_i=0,1,2,...,m-1$

1存储操作
即发生冲突时，每次往后探测一个单元（向后挪1单元）。若为空，放入，若发生冲突，则接着挪

【易错点】
$H(key)=key\%p$
$H_i=(H(key)+d_i)\%m$
m和p不一定相等
例如：

n=13；p为不大于n且与n互质的数，为13
m为表长为16
$H(25)=25\%13=12$
$H_1=(12+1)\%16=13$

查找操作与存储操作类同。当查找到第一个空位，仍未找到，则查找失败。（例如查找21，从位置8开始查找，直到位置13，仍未找到。查找失败）

缺点：

(2) 平方探测法

$d_i=0,1,2,...,m-1$

存储操作
即发生冲突时，每次往后探测一个单元（向后挪1单元）。若为空，放入，若发生冲突，则接着挪

查找操作与存储操作类同

(3) 伪随机序列法

$d_i=0,1,2,...,m-1$

• 存储方式
  即发生冲突时，每次往后探测一个单元（向后挪1单元）。若为空，放入，若发生冲突，则接着挪
• 查找方式

转载：https://blog.csdn.net/Dys_debug/article/details/128835725