散列表

散列表是一种基本的数据结构，那么散列表到底是什么样的一种数据结构呢？又有哪些应用场景呢？

假如我们要从一本电话本中查找一个人的电话号码

如果这个电话本不是有序的，那我们每一行去找O(n)

如果是排列有序的，那我们可以通过二分查找O(logn)

需要注意的是O(n)与O(logn)的运行时间有着天壤之别，假设每秒能查找10行，在我们使用简单查找O(n)与二分查找O(logn)耗时如下表：

如图二分查找效率已经高出很多，但是还要去扫描多行，那有没有更高效、常数级O(1)的查找呢？ 这就是散列表的用武之地。

散列函数

    我通俗解释为，把输入映射（转换）到数字，并满足一些条件：

必须是一致的，相同的输入必须转换到相同的数字，例如输入”张三”时得到的是0，那么每次输入”张三”得到的数值都必须是0。

将不同的输入映射成不同的数字，最为理想的情况下将不同的输入映射到不同的数字。

散列函数又有何用处呢？

如上图，散列函数准确的指出了”张三”的存储位置，根本不用查找，因为：

散列函数将同样的输入映射到了相同的索引。

散列函数将不同的输入映射到了不同的索引。

散列函数数组内的有效索引（没有超过数组的边界）。

冲突

    前面我们假设的散列函数总是能将不同的输入映射到了数组的不同位置。而实际上，几乎不可能编写出这样的散列函数。

不同的输入被分配到了同一个数组位置上了，这就是冲突。所以只能在这个索引位置上存储一个链表。

如上图，如果散列表除第3个位置上有存储了一个列表，其它位置上都是空的，换而言之就是说，这个散列表中的所有元素都在这个链表上。那性能会很糟糕O(n)。

所以，散列函数非常非常重要。

(有兴趣的朋友可以研究一下MurmurHash，https://en.wikipedia.org/wiki/MurmurHash)

一般常见语言都实现了散列表，如Java的HashMap

Go中的map

Python的字典

引伸一下应用，如Redis中字典的实现：

https://sourcegraph.com/github.com/antirez/redis@fe43406929dbf6e6316f53f891370850cd8e1c3f/-/blob/src/dict.h#L77

dictEntry：哈希表数组

size：哈希表大小

sizemask：散列表大小的掩码，用于计算索引值

used：使用节点的数量

key：键值中的键

v：键值中的值

next：下一下散列节点的指针（解决散列函数的碰撞问题）

Resize 散列表扩容

可以自行参考一下Redis的rehash与渐进式rehash，本文主要介绍一下散列表这种数据结构基础。

码农闲话