Hash 表

263次阅读  |  发布于1年以前

Hash 表是一种将键映射到值的抽象数据结构,可以实现 key-value 键值对的存储与查找。

如上图,把 key 传给哈希函数(hash function),然后计算出 hash 值,hash 值映射到存储桶数组的下标,从而找到 value 值。这就建立了 hash 表中 key 和 value 的映射关系。

Hash 函数

hash function 在 hash 表中起到了非常关键的作用。hash 函数传入参数是 key,返回值是 hash 值。如果想建立完美的映射关系,hash function 最好能支持以下特性。

  1. 传入相同的 key ,经过 hash function 得到「始终相同」的 hash 值。
  2. 传入不同的key,经过 hash function 得到「始终不同」的 hash 值。

第一点保证了 key 和 hash 值对应关系的稳定性。第二点保证对应关系的唯一性,不过在实际场景中这几乎是不可能做到的,只能尽可能的减少不同 key 得到相同下标的概率。不同的 key 得到相同的 hash 值的现象称为 hash 冲突。

业界比较有名的 hash 算法:MD5、SHA系列。

支持操作

Hash 表通常需要支持插入、查找、删除操作。

插入:根据传入的 key ,经过 hash function 生成 hash 值,把 hash 值映射到数组中。在数组中存储指向 value 的地址。

查找:和插入过程一样,只不过最后返回查询到的 value 值。查找过程中除了 hash function 运算,就是在数组中根据下标找到值的过程。数组根据下标查找数据的时间复杂度是O(1),所以我们也常说 Hash 表查找的时间复杂度接近 O(1)。(因为存在 hash 冲突,其实 O(1) 是不准确的)

删除:删除过程一般采用软删除,把需要删除的元素找到之后标记为已删除,然后采用其它策略完成真正的删除。软删除避免了数组中删除元素时重新移动元素的问题。带来的副作用是删除元素并没有真正释放存储空间。

Hash 冲突

上文中提到的 hash function 无法做到“传入不同的key,经过 hash function 得到「始终不同」的 hash 值”。当不同的 key 得到相同的 hash 值时,就出现了 hash冲突。

解决 hash 冲突有两类方法:链表发和开放寻址发。

链表发是最常用的方法。

就像它的名字,它通过链表来存储出现 hash 冲突的元素。对某个 key 进行 hash 运算生成 hash 值,当发现 hash 表中已经存在这个 hash 值,但是 key 不相同时,采用链表,把这个 key 和 value 存在当前元素的后面。

开放寻址法的核心思想是在发生 hash 冲突时,重新探测一个空闲位置来存储数据。当下次查找时,根据相同的探测规则来查找到相应的 value 。开放寻址有线性探测、二次探测、双重 hash 等多种方法。

对于一些动态增加的 hash 表,随着 hash 表中数据增多,hash 冲突的概率会越来越大,也会导致其操作性能下降。通常通过装载因子来衡量一个 hash 表可能发生冲突的概率。

装载因子=填入表中的元素个数/散列表的长度

当装载因子过大,比如超过0.8时,往往通过对 hash 表进行动态扩容来减少 hash 冲突。动态扩容过程中需要进行 rehash 操作,往往会占用比较高的 cpu 和 存储。比较经典的解决方案是采用渐进式 rehash,缓慢的对 hash 表完成扩容。

局限性

总体来讲 hash 表是一种非常高效的索引数据结构,不过它也有一些局限性:

  1. 因为 key 和 hash 值的存储往往是无序的,所以通常认为 hash 表不擅长范围查找,更适合,单值查找。
  2. hash 表的 key 通常需要全部加载到内存中,多有当有大量 key 时会占用比较多的内存。(用磁盘来存储 key ,会产生很多随机磁盘 I/O ,效率比较低)

总结

本文我们主要介绍了 hash 表的基本概念、基本操作、 hash 冲突以及 hash 表的一些局限性。

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8