【数据结构笔记39】哈希表/散列表、（数据关键字/字符串关键字）散列构造函数

本次笔记内容：
11.1.1 引子：散列的基本思路
11.1.2 什么是散列表
11.2.1 数据关键词的散列函数构造
11.2.2 字符串关键词的散列函数构造

散列表背景

基本思想引出

编译处理时，涉及变量及属性（如：变量类型）的管理：

• 插入：新变量定义；
• 查找：变量的引用。

编译处理中对变量的管理：一个动态查找问题。

如果利用AVL树进行变量管理，涉及到两个变量名（字符串）比较，效率不高。

那么是否可以先把字符串转换为数字，再处理？

已知查找方法与拓展

• 顺序查找：$O(N)$O(N)；
• 二分查找（静态查找）：$O(\log_2 N)$O(log2​N)；
• 二叉搜索树：$O(h)$O(h)，h为二叉查找树的高度；
• 平衡二叉树：$O(\log_2 N)$O(log2​N)。

如上图，在使用二分查找QQ账号信息时，时间空间还较为合理。但是这是一个动态查找的过程，插入和删除需要移动大量数据，不现实。

因此，需要考虑查找的本质：已知对象找位置。因此可以考虑：

• 有序安排对象：全序、半序；
• 直接“算出”对象位置：散列。

散列查找的基本工作

• 计算位置：构造散列函数，确定关键词存储位置；
• 解决冲突：应用某种策略，解决多个关键词位置相同的问题。

时间复杂度几乎是常量：$O(1)$O(1)，即查找时间与问题规模无关！

散列表（哈希表）

哈希表定义、操作如上图。

例子1：求余

如上图，其中使用了一种经典的哈希映射方案：求余。如果存放时遇到了“冲突”，则需要设立一种解决冲突的方案。

装填因子（Loading Factor）：用于表示哈希表中填满程度。

例子2：散列表

如上图，使用有2列的数组Table根据首字母排列数据。问题是，如果c开头的数据有三个或者三个以上，怎么办？之后讨论。

如果没有冲突（溢出）：
$T_{查询}=T_{插入}=T_{删除}=O(1)$T查询​=T插入​=T删除​=O(1)

散列（Hashing）基本思想

如上图，Hashing的基本思想是数据对象的存储地址的映射与冲突（Collision）解决策略的制定。

散列函数构造

一个“好”地散列函数一般应考虑下列两个因素：

1. 计算简单，以便提高转换速度；
2. 关键词对应的地址空间分布均匀，以尽量减少冲突。

数字关键词的散列函数构造

直接定址法

取关键词的某个线性函数值为散列地址，即

$h(key)=a \times key + b$h(key)=a×key+b

其中a、b为常数。

上图中，$h(key)=key-1990$h(key)=key−1990。

除留余数法

散列函数为$h(key)=key \; mod \; p$h(key)=keymodp。

如上图，p一般取素数。

数值分析法

如上图，手机号后四位可能变化很大（同一地区手机号开头可能一致），因此选取后四位作为地址。

h(key)=atoi(key+7)将key指针向后移动7位，并且将字符串转换为整数（int atoi(char *s)）。

如上图，对于key是身份证号时，取标蓝的六位作为散列地址较好。

折叠法

如上图，将数字折叠起来，求和取后三位是折叠方法的一种。

平方取中法

如上图，平法取中法是希望更多的位数能影响哈希地址。

字符关键词的散列函数构造

ASCII码加和法

如上图，简单加和容易导致产生冲突、哈希聚集。

简单的改进：前3个字符位移法

如上图，之所以取27是因为考虑到了26个字母与空格。但是依然会有冲突。并且，经过统计，只能产生3000个地址，但是前3个字符有26^3种组合。因此空间浪费很大。

好的散列函数：移位法

这里考虑32进制。

如上图，乘32级在二进制中将数值后移5位。因此该哈希函数得到了大大的简化。