数据结构与算法总结——哈希表

什么是哈希表

哈希表（HashTable，也叫散列表），是根据关键码值(Key-value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

哈希表有什么应用

如C++的STL的unordered_map、Java中的HashMap、C#的Dictionary等都是基于哈希表实现。

一个贴切的例子

手机中的通讯录

在查找通讯录某一条目时，我们不需要从头看到尾找一遍，通讯录通常有按首字母分组的功能，例如我们需要找“张三”，我们只需要直接找到“z”索引即可，这就是哈希表查找为什么快的原理。
“张三”是怎么对应到“z”这个索引的，我们需要给出一个算法实现从这个键到索引的转换，我们称为哈希函数。
通讯录可能存在首字母相同的人，例如新增了一个“张飞”的人，他与“张三”一样对应着“z”索引，这种情况我们称为碰撞/冲突。

关于哈希表的基本结构、哈希函数的实现、冲突的解决方式是本文主要讨论内容。

哈希表的基本结构

哈希表的基本结构是一个数组，哈希表访问速度之所以快其实是基于数组拥有O(1)的随机访问速度的，但哈希表可以以任意类型键作为索引，而数组只能用整数类型当索引，所以哈希表内部要用数组储存值，就必须用一个哈希函数来实现从键到整数的转换，而这个键到数组索引的转换，是有可能存在不同键转换成相同索引的情况，这也就是发生冲突的情况，为了应对这种情况，我们可能需要更加复杂的结构，通常是以下几种方式：

数组
数组+链表
数组+树

哈希函数

哈希函数可以说是哈希表的核心部分，它本身的计算耗时，以及计算结果会直接影响哈希表的性能。如果哈希值计算本身耗时比较长，即使哈希表读取耗时是常数时间，但在一些情况下，也可能比一些查找树结构要慢。而哈希函数计算结果的均匀性则直接决定了碰撞率，碰撞率影响着哈希表的查找效率、内存利用率。

常见的哈希函数有以下几种方式：

直接寻址法：取keyword或keyword的某个线性函数值为哈希地址。即H(key)=key或H(key)=a•key+b，当中a和b为常数（这样的哈希函数叫做自身函数）

数字分析法：分析一组数据，比方一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体同样，这种话，出现冲突的几率就会非常大，可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大，假设用后面的数字来构成哈希地址，则冲突的几率会明显减少。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的哈希地址。

平方取中法：取keyword平方后的中间几位作为哈希地址。

折叠法：将keyword切割成位数同样的几部分，最后一部分位数能够不同，然后取这几部分的叠加和（去除进位）作为哈希地址。

随机数法：选择一随机函数，取keyword的随机值作为哈希地址，通经常使用于keyword长度不同的场合。

除留余数法：取keyword被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。即H(key)=key%p,p<=m。不仅能够对keyword直接取模，也可在折叠、平方取中等运算之后取模。对p的选择非常重要，一般取素数或m，若p选的不好，容易产生碰撞.

总的来说，要为一个数据类型实现一个优秀的哈希函数需要满足三个条件：

一致性——等价的键必然产生相等的哈希值
高效性——计算简便
均匀性——均匀散列所有的键

设计同时满足这三个条件的哈希函数通常是专家们的事。

另外，一般哈希函数的实现是返回一个32位整数，它的值可能会非常大，我们不太可能用来直接作为数组索引，而是把计算出来的哈希值再次分段映射到一个较小的数值范围内，每一段称之为一个桶，一般的映射方法就是直接把哈希值取余。可以看出，经过桶的再次映射，会进一步加剧哈希的碰撞。

哈希碰撞的解决方案

拉链法

把哈希表中的数组的每个元素指向一条链表，链表中的每个节点都储存了哈希值为该元素索引的键值对。这种方法被称为拉链法，因为发生冲突的元素都被储存在链表中。查找可以分为两步：首先根据哈希值找到对应的链表，然后沿着链表顺序查找对应的键。这个方法的基本思想是选择足够大的数组，使得链表都尽可能短以保证高效的查找。

在使用基于拉链法的哈希表时，我们的目标是选择合适的数组大小，既不会因为空链表而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。而拉链法的一个好处就是这并不是关键性选择。如果存入的键多于预期，查找所需的时间只会比选择更大的数组稍长；如果少于预期，虽然有些空间浪费但查找会非常快。当内存不是很紧张时，可以选择一个足够大的数组，使得查找需要的时间变为常数；当内存紧张时，选择一个尽量大的数组，仍然能将性能大幅提高。