什么是哈希表

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

哈希表有什么应用

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

一个贴切的例子

手机中的通讯录

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

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

哈希表的基本结构

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

  1. 数组
  2. 数组+链表
  3. 数组+树

哈希函数

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

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

  1. 直接寻址法:取keyword或keyword的某个线性函数值为哈希地址。即H(key)=key或H(key)=a•key+b,当中a和b为常数(这样的哈希函数叫做自身函数)
  2. 数字分析法:分析一组数据,比方一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体同样,这种话,出现冲突的几率就会非常大,可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大,假设用后面的数字来构成哈希地址,则冲突的几率会明显减少。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的哈希地址。
  3. 平方取中法:取keyword平方后的中间几位作为哈希地址。
  4. 折叠法:将keyword切割成位数同样的几部分,最后一部分位数能够不同,然后取这几部分的叠加和(去除进位)作为哈希地址。
  5. 随机数法:选择一随机函数,取keyword的随机值作为哈希地址,通经常使用于keyword长度不同的场合。
  6. 除留余数法:取keyword被某个不大于哈希表表长m的数p除后所得的余数为哈希地址。即H(key)=key%p,p<=m。不仅能够对keyword直接取模,也可在折叠、平方取中等运算之后取模。对p的选择非常重要,一般取素数或m,若p选的不好,容易产生碰撞.

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

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

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

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

哈希碰撞的解决方案

拉链法

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

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

开放寻址法

当我们数组大小大于键值对数量的时候,发生冲突时可以直接取数组空位来储存新元素,基于这种策略的方法统称为开放寻址法,而线性探测法是其中最简单的一种实现。

当发生碰撞时,我们直接检查数组中下一个位置(索引值加1),这样的线性探测可能会产生三种结果:

  1. 命中,该位置的键和被查找的键相同
  2. 未命中,键为空
  3. 继续查找,该位置的键和被查找的键不同

我们用哈希函数找到的键在数组中的索引,检查其中的键和被查找的键是否相同,如果不同则继续查找(索引继续增大,到达数组结尾时折回数组开头),知道找到该键或者遇到一个空元素。开放地址类的哈希表的核心思想是与其将内存用作链表,不如将它们作为哈希表里的空元素,这些空元素可以作为查找结束的标志。

开放寻址法的删除操作比较特别,我们不能直接将元素置空,因为空是被视为查找结束的标志,我们可以通过把被删除位置标记为删除状态,使得查找时遇到该状态的位置不会停下,而是继续查找,或者是把被删除位置后面的元素重新插入到哈希表中等方法实现删除。

线性探测的平均成本取决于元素在插入数组后聚集成的一组连续的条目,也叫做键簇,显然短小的键簇才能保证较高的效率,但这个要求很难满足,随着插入的键越来越多,较长的键簇也会越来越多,而在插入元素时,数组每个位置都有着相同的几率被插入一个新元素,而落在长键簇的几率会更大。

基于以上情况,我们应该实现一个根据当前哈希表键值对个数来动态调整数组大小的机制,以平衡性能。

再哈希法

实现多个不一样的哈希函数,对产生碰撞的键,换一种哈希函数进行计算,直到不碰撞为止。这种方法增加了哈希计算耗时。

公共溢出区

为所有碰撞的键建立一个公共的溢出区来存放。在查找时,对给定关键字通过哈希函数计算出哈希值后,先与数组中的位置进行比对,如果相等,则查找成功;如果不相等,则到溢出表进行顺序查找。如果相对于基本表而言,在产生碰撞的数据很少的情况下,公共溢出区的结构对查找性能来说还是非常高的。

总结

哈希表是算法在时间和空间上做出权衡的经典例子,哈希表在理论上的最优性能非常优秀,但它并非包治百病的灵丹妙药,因为:

  1. 每种类型的键都需要一个优秀的哈希函数。
  2. 性能保证来自于哈希函数的质量。
  3. 哈希函数的计算可能复杂而且昂贵。
  4. 难以支持有序性相关的操作。

游戏开发者(萌新