【数据结构】查找——散列表（哈希表小总结 附例题）

写在前面：

• 线性表、树表的查找方法基于关键字的比较为基础。当关键字多得不像话了怎么办？？
• 有木有一种方法可以在「元素的存储位置」和「关键字」之间建立某种关系，使得我很快就能找到关键字的家（在存储结构中的位置）呢？
• 有的，这就是散列表的思想：实现「关键字」—>「地址」的直接转换方法，无需反反复复比较。

1 散列表的一些概念

• 散列表（Hash Table），又叫哈希表，通常存储空间是个一维数组，散列地址是数组的下标。
• 特点：数据元素的关键字与其存储地址直接相关。
• 冲突：两个或两个以上的不同关键字映射到同一地址。（可以理解为别人和你抢地盘），是多对一的映射。这些相同函数值的关键字称为同义词。
• 冲突不可避免，但可以「选择一个好的散列函数」、「设计好处理冲突的方法」来尽可能减少冲突。

如何构造散列函数 ？？
如何处理冲突 ？？

2 散列表的构造方法

构造散列函数要注意：

• 定义域须包括全部关键字，值域依赖于散列表的大小或地址范围。
• 为***减少冲突***，散列函数计算出来的地址应等可能、均匀分布。
• 散列函数应***简单***、短时间内能够计算出相应的散列地址。

2.1 直接定址法

适合关键字分布基本连续的情况。

2.2 除留余数法

散列函数：

• H( key ) = key % p
• 散列表长为 m，p < = m，其中 p 是最接近 m 的质数。
• 比如表长13，p 为13；表长15，p 为13；表长为100，p 为97。
  （质数：只有 1 和 它本身 两个因子。如果是合数，公因子很多，有很多相似的特征，会较容易发生冲突）
• 特征：关键是选好 p ，是每个关键字等概率映射到地址上，尽可能减少冲突。

2.3 数字分析法

适用于：事先知道所有关键字每一位上各种数字的分布情况。
例子：统一出版社的ISBN码

2.4 平方取中法

也会发生冲突。
方法： 取关键字的平方值的中间几位作为散列地址。这是因为一个数平方后的中间几位数和数的每一位都相关。
适用于： 关键字情况未知，每位取值都不够均匀 或 小于散列地址所需的位数。

3 处理冲突的方法

冲突前：「一个好的散列函数」可在一定程度上减少冲突；
冲突后：「选择一个有效的处理冲突的方法」是另一个关键问题。

3.1 开放定址法

• 空闲地址既向同义词表项开放，又向非同义词表项开放。
• 公式：
  
  其中H( key)：散列函数 。m：散列表表长。d(i)：增量序列。
• 根据 d(i) 不同，有下面4种探测方法：

3.1.1 线性探测法

d(i) = 1、2、3、4…. m-1

• 可以将散列表假设成一个循环表，发生冲突时顺序寻找空单元，直至找到一个空位。若回到表头开始也为找到，说明散列表已满，进行溢出处理。
• 同义词、非同义词均可能发生冲突。
• 对空指针的判断算一次比较。
• 会出现聚集（堆积），大大降低查找效率。

3.1.2 二次探测法

d(i) = 1、-1、4、-4 … k^ 2、 -k^2

• 表长 m 可以是 4j+3 的质数

3.1.3 伪随机探测法

d(i) = 伪随机序列数

小试牛刀～

• 来道例题试试叭～～
  

3.2 拉链法

思想：把具有相同散列地址的记录放在同一单链表中。
只有同义词冲突，把同义词存储在同一个链表。
适用于：经常插入、删除的情况。

• 来道例题试试叭～～

4 散列表的性能分析

装填因子 = n / m
n：表中记录数。m：散列表表长。

• 装填因子定义为表装满程度，越大越容易发生冲突。在操作中，装填因子越小越好。
• 要会求散列表的查找成功时的平均查找长度和查找失败时平均查找长度。
• 散列表查找效率三因素：散列函数、处理冲突的方法、装填因子。

来道例题试试叭～～