[数据结构与算法]哈希表（散列表）知识点概述

引言

在查找数据过程中，有很多种方法，但是大部分都是通过数据间的比较进行的，有没有一种方法可以直接通过关键字得到要查找的数据的位置的方法呢？这就需要用到一种新的查找方法，散列查找法；

基本思想

记录存储位置与关键字之间存在的对应关系f，使得每个关键字key对应一个存储位置f(key)；

这里的对应关系f就是散列函数，也称为哈希函数；

所以哈希表定义也可以是
通过 关键字集合 由 哈希函数 推出 存储地址集合；
而这些集合的存储空间就是散列表（哈希表）；

散列技术既是一种存储方法也是一种查找方法，它所记录的数据之间不存在什么逻辑关系，只与关键字有关联，所以可以说，散列表主要是面向查找的存储结构；

所以散列表查找就有一个很大的优点：
查找速度极快，时间复杂度为O(1)，查找效率与元素个数无关；

相关术语

哈希函数（散列函数） ：在存储位置p和其关键字key之间建立的一个确定的对应关系f，使f(key) = p，则f为哈希函数，p为哈希地址；
哈希表 ：一个有限连续 的地址空间，用以存储按哈希函数计算得到相应哈希地址的数据记录。
冲突 ：不同的关键字映射到同一个哈希地址，即key1 不等于key2，而f(key1) = f(key2)；
同义词 ：具有相同函数值的两个关键字，即key1和key2

哈希函数构造方法

构造前需要考虑的因素：

1. 哈希表长度
2. 关键字长度
3. 关键字的分布情况
4. 计算哈希函数的时间
5. 记录的查找频率

同时，一个好的哈希函数需要遵循以下两个原则
1，计算简单
每一个关键字只能有一个散列地址与之对应（减少时间）
2，哈希地址分布均匀
函数的值域需要在表长范围内，这样计算出来的哈希地址分布均匀，减少冲突（减少空间）

构造哈希函数有好几种方法，这里就介绍最关键的一个方法——除留余数法
这个方法是最常用的构建哈希函数的方法，对于哈希表长为m的哈希函数公式为：

f(key) = key mod p (p <= m)

mod是取模，其实不仅可以对关键字取模，还可以在折叠平方中国取中后再取模，可以很直观的看出，这个方法运用的好坏全都取决于p的选取；
所以一般情况下，若哈希表长为m，通常p为小于或等于表长（最好接近m）的最大质数；

处理冲突的方法

在哈希表的实际运用中，很难避免不出现冲突，这时就需要有处理冲突的方法，处理方法和哈希表的本身组织形式有关，根据组织形式的同，通常分为两大类，开放定址法和链地址法；
开放定址法
基本思想：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入；

f(key) = (f(key) + d) mod m (d = 1,2,3,4,5,……m-1)

f为哈希函数，m为哈希表表长，d为增量序列，由d的取值不同，可以分为下列3种探测方法

1. 线性探测法
2. 二次探测法
3. 伪随机探测法

这里就不详细介绍这三种方法了，可以自行查阅；

链地址法
基本思想：相同哈希地址的记录连成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构；

即不同的key有相同的p，通过相同的p为表头将这些key连接起来

这个方法很像图中的 邻接表 的使用方法，可以类比理解，这里的哈希地址可以类比为邻接表里的顶点表，每个顶点相连的点就类似于哈希地址相同的关键字key；

这里就区别一下开放定址法和链地址法的特点

总结

这只是一些基本内容，对于哈希表的代码实现以后可能会补充，其实现在有很多造好的轮子可以使用，但是底层实现还是需要有了解的，这也是数据结构这门课程的存在原因。