哈希函数、哈希表、HashMap，二叉搜索树简介

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

随着这篇文章，我们进入了本书的第五章——哈希表。

哈希函数

要理解哈希表，就需要先理解哈希函数，而想要理解哈希函数，最好从它的原理入手。我们为什么需要哈希函数，它的出现解决了一个什么实际的问题。

我们先来看一个简单的问题——班级花名册。某一次考试之后，老师拿到了全班所有同学的成绩。一般情况下会被记录进一个类似花名册的东西里。比如我们可以用一个结构体记录每个同学的信息，比如姓名、考试成绩、性别。之后再创建一个结构体数组就可以存下所有同学的信息。

但是在查询的时候就有问题了。假设我们要查询某个特定学生的成绩，比如张三的成绩，怎么办呢？我们没办法知道张三对应的数据存放在数组的什么位置。在这种情况下，我们只能遍历整个数组，依次判断，直到找到张三为止。这种枚举遍历的查找方式复杂度是

。

在数据量很小的情况下，这种方法当然没问题，现实中老师都是这么干的。然而一旦数据量很大、查询次数很多时，这样的复杂度就没办法接受了。

怎么样解决这个问题呢？

算法大佬们给出的答案就是哈希函数，所谓的哈希函数，它只做一件事情就是映射。我们使用数组来存储所有同学的数据，最大的问题是我们不知道每条信息存储的位置，所以只能遍历来查询。

假设我们可以设计出某种算法，它可以将学生的姓名映射成一个整数。名字不同，映射之后的结果也不同。那么利用这一点，我们是不是就可以解决这个问题了。

举个例子，假设我们拥有了某个哈希函数，它对“张三”的哈希结果是1。那么我们就把张三的数据存放进数组下标1的位置。在查询的“张三”的时候，我们再调用一次哈希函数传入“张三”，会得到1。1就是张三数据储存的下标，那么我们只要访问数组中对应的位置就可以拿到张三的数据了。

这种将非整数类型的数据映射成整数的函数就叫做哈希函数。

哈希表

现在我们理解了哈希函数，那么哈希表又是什么呢？

哈希表实际上就是一个数组，也就是用来存储哈希之后结果的数组。既然是数组，那么它的长度是固定的。但哈希函数返回的范围往往要大得多。这个时候，我们可以采用取模的方法来将哈希函数的结果重映射到数组的长度以内。

大家可以参考一下下面这段代码：

struct P {...};
P data[10];
// 对数组长度取模
int id = hash("张三") % 10;
data[id];

哈希表的原理很好理解，但是真正要去使用的话就会遇到一些问题。最大的问题就是哈希冲突或者哈希碰撞的问题。

哈希冲突

哈希函数可以将我们的输入映射成数字，我们可以保证，同样的输入可以得到同样的映射结果。但是反之，不同的输入映射之后的结果一定不同吗？

我们可以从输入输出的集合去思考这个问题，理论上来说我们的输入的可能性理论上是无穷的。那输出呢？哈希函数的返回类型往往是int32或者是int64，不论是哪一种，它的取值范围都是有限的。既然输入的范围无限而输出的范围有限，那么必然会存在多个不同的输入但输出结果相同的情况。

这种输入不同，但哈希之后的结果相同的情况就称为哈希冲突。

在哈希表当中，由于我们还需要将哈希之后的结果对表的长度取模，因此就更加容易遇到冲突。所以指望运气好没有遇到冲突是不现实的，我们必须在数据结构当中解决这个问题。

拉链法

针对这个问题，解决的方法有好几种，但细究起来根据原理只有两种，一种是拉链法，一种是探测法。

所谓探测法，即当我们插入新的数据与已有的元素发生哈希碰撞时，会探测另外一个可行的位置来代替。根据探测的方法不同又可以分成线性探测、二次探测、双哈希等方法。所以这些方法的本质是一样的，就是碰撞之后另外寻找一个空闲的位置来使用。

而拉链法不同，它不会另外探测其他的位置，而是会使用链表将所有哈希值相同的元素一起存放起来。所以完整的结构是一个链表的数组，存取元素的时候都会经过两步操作。首先通过哈希算法算出下标，找到对应位置的链表。然后再在链表当中进行遍历和插入的操作。

这里有一个trick，我们在修改链表中的元素时注意保证链表的有序性。这样在搜索元素时我们就不必遍历完整个链表，当遇到比要查找的元素更大的元素时，就已经说明要找的元素不存在了。

Java中的HashMap以及C++中的unordered_map，都是基于这样的哈希表实现的。

哈希函数可以被认为是

复杂度的操作，在链表中的元素不太多时，那么整体的增删改查的复杂度都可以控制在

。这样的复杂度看起来非常完美，但是这里面有一个小问题。哈希表数组的长度是一个定值，那么随着我们插入元素的增多，必然会导致链表的长度越来越长，也就没办法保持长度控制在

了。

针对这个问题，通常的做法是扩容 + rehash。比如Java中的HashMap会设置一个阈值，当表中元素的个数超过阈值时就会触发扩容。扩容时会将数组的长度增加一倍，接着把当前所有的元素全部读取一遍重新hash，再插入到扩容之后的哈希表当中。

扩容会带来额外的时间和空间开销，时间开销很好理解，所有元素全部重新插入一遍是

的操作。另外，扩容之后哈希表的长度翻倍，通常也会带来浪费，因为我们没法保证表中的元素是平均分配的。

二叉搜索树

我们要存储两个变量之间的映射关系，除了使用哈希表之外还可以使用二叉搜索树。

C++当中，这两者分别对应unordered_map和map。这两者的用法基本一致，不过底层的实现原理完全不同。前者基于哈希表，后者基于红黑树（二叉搜索树）。

红黑树会直接将映射前后的结果打包一起作为树中的节点存起来，利用键值的大小关系来建立二叉搜索树。所以它会要求键值必须是可比较的，如果是我们自定义的类型，需要我们重载比较符，而哈希表则不存在这个限制。一棵平衡的二叉搜索树的查找复杂度是

，要比哈希表

的复杂度要高，但二叉搜索树存储了节点之间的顺序，我们可以按照大小顺序遍历所有结果，但哈希表则不能。

关于哈希表原理的部分就聊到这里，下一篇文章我们将会结合例题来实际体会一下map的应用。