散列（Hash）表

小灰灰 2021-12-10 02:29 495阅读 0赞

### 文章目录 ###

*  概念
 *  定义
 *  构造散列函数的方法。
 *   *  直接定址法
     *  数字分析法
     *  平方取中法
     *  折叠法
     *  除留余数法
     *  随机数法
 *  处理冲突的方法
 *   *  开放定址法
     *   *  线性探测再散列
         *  平方探测再散列
     *  例子
     *  链地址法
 *  散列表的查找
 *  散列表的性能

# 概念 #

静态查找表和动态查找树表的共同特点是记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。

用这类方法表示的查找表，其平均查找长度都不为零。不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。

对于频繁使用的查找表，希望 A S L = 0 ASL=0 ASL=0。只有一个办法：预先知道所查关键字在表中的位置，即，要求：记录在表中位置和其关键字之间存在一种确定的关系。

因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f ( k e y ) f(key) f(key)作为关键字为 k e y key key的记录在表中的位置，通常称这个函数 f ( k e y ) f(key) f(key)为散列函数。

例如:对于如下 9 个关键字`{Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei}`设散列函数。

f ( k e y ) = ⌊ ( O r d ( f i r s t l e t t e r ) − O r d ( ′ A ′ ) + 1 ) / 2 ⌋ f(key) = \\lfloor (Ord(first letter) -Ord(&\#x27;A&\#x27;)+1)/2 \\rfloor f(key)=⌊(Ord(firstletter)−Ord(′A′)\+1)/2⌋

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]

那么问题来了，如果现在添加关键字`Zhou`，怎么办？  
通过函数计算得到的位置已经被占了。

从这个例子可见:

1.  散列(Hash)函数是一个映象，即:将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可;
2.  由于散列函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： k e y 1 ≠ k e y 2 key1 ≠ key2 key1̸=key2，而  f ( k e y 1 ) = f ( k e y 2 ) f(key1) = f(key2) f(key1)=f(key2)。
3.  **很难找到一个不产生冲突的散列函数**。一般情况下，只能选择恰当的散列函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的散列函数之外;**还需要找到一种“处理冲突” 的方法**。

# 定义 #

根据设定的**散列函数 H ( k e y ) H(key) H(key)和所选中的处理冲突的方法**，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“散列表”。

# 构造散列函数的方法。 #

对数字的关键字可有下列构造方法:

1.  直接定址法
2.  数字分析法
3.  平方取中法
4.  折叠法
5.  除留余数法
6.  随机数法

若是非数字关键字，则需先对其进行数字化处理。

## 直接定址法 ##

散列函数为关键字的线性函数 H ( k e y ) = k e y H(key) = key H(key)=key或者  H ( k e y ) = a ∗ k e y + b H(key) = a \* key + b H(key)=a∗key\+b

此法仅适合于：**地址集合的大小=关键字集合的大小**

## 数字分析法 ##

假设关键字集合中的每个关键字都是由 s 位数字组成  ( u 1 , u 2 , . . . , u s ) (u1, u2, ..., us) (u1,u2,...,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。

**此方法仅适合于:能预先估计出全体关键字的每一位上各种数字出现的频度。**

## 平方取中法 ##

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。

**此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。**

## 折叠法 ##

将关键字分割成若干部分，然后取它们的叠加和为散列地址。有两种叠加处理的 方法:移位叠加和间界叠加.

**此方法适合于: 关键字的数字位数特别多。**

## 除留余数法 ##

设定散列函数为： H ( k e y ) = k e y M O D p H(key) = key \\ MOD \\ p H(key)=keyMODp 其中， p ≤ m p \\le m p≤m(表长)并且`p`应为不大于`m`的最大素数。

--------------------

为什么要对 p 加限制?（为什么非得是素数？）

例如：

给定一组关键字为: `12, 39, 18, 24, 33, 21`，若取  p = 9 p=9 p=9, 则他们对应的散列函数值 将为: `3, 3, 0, 6, 6, 3` 可见，若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。

## 随机数法 ##

设定散列函数为： H ( k e y ) = R a n d o m ( k e y ) H(key) = Random(key) H(key)=Random(key)其中，`Random`为伪随机函数。

通常，此方法用于对长度不等的关键字构造散列函数。

# 处理冲突的方法 #

## 开放定址法 ##

为产生冲突的地址 H ( k e y ) H(key) H(key)求得一个地址序列：`H0, H1, H2, ..., Hs` ， 1 ≤ s ≤ m − 1 1≤ s≤m-1 1≤s≤m−1

其中： H 0 = H ( k e y ) H0 = H(key) H0=H(key)、 H i = ( H ( k e y ) + d i ) M O D m H\_i = ( H(key) + d\_i ) \\ MOD \\ m Hi=(H(key)\+di)MODm ，`i=1, 2, ..., s` 对增量  d i d\_i di 有三种取法:

### 线性探测再散列 ###

d i = c × i d\_i=c × i di=c×i 最简单的情况 c = 1 c=1 c=1

实际就是，当发生冲突时，将位置递增，直到找到第一个为空的位置为止。

### 平方探测再散列 ###

d i = 1 2 , − 1 2 , 2 2 , − 2 2 , . . . , d\_i = 1^2, -1^2, 2^2, -2^2, ..., di=12,−12,22,−22,...,

当发生冲突时，先对当前位置加 1 2 1^2 12，如果不为空，则再加 − ( 1 2 ) -(1^2) −(12)，若还不为空则再加 2 2 2^2 22，以此类推，直至找到第一个不为空的位置为止。

## 例子 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]

## 链地址法 ##

将所有散列地址相同的记录都链接在同一链表中。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]

# 散列表的查找 #

散列表的查找 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为:

*  对于给定值`K`, 计算散列地址  i = H ( K ) i = H(K) i=H(K)
 *  若  r \[ i \] = N U L L r\[i\] = NULL r\[i\]=NULL 则查找不成功
 *  若  r \[ i \] . k e y = K r\[i\].key = K r\[i\].key=K 则查找成功
 *  否则 “求下一地址  H i H\_i Hi” ，直至 `r[Hi] = NULL` (查找不成功)或 `r[Hi].key = K` (查找成功) 为止。

# 散列表的性能 #

**从查找过程得知，散列表查找的平均查找长度实际上并不等于零**。

决定散列表查找的 ASL 的因素:

1.  选用的散列函数;
2.  选用的处理冲突的方法;
3.  散列表饱和的程度，装载因子  α = n / m α=n/m α=n/m 值的大小(n — 记录数，m — 表的长度)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20211209/dfadbd80f3a149c397ba91366fc91db0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20211209/5c48724bb1aa4173931bee1de5782af3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]: /images/20211209/2b20ad209e9246bfbde3fa4c762cf42b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 3]: /images/20211209/f1d3e4c21d01447680599781a40f290b.png