大家好，我是梁唐。有了这篇文章，我们就进入了本书的第五章——HashTables。哈希函数要了解哈希表，首先要了解哈希函数，而要了解哈希函数，最好从它的原理入手。为什么我们需要哈希函数，它解决了什么实际问题。先来看一个简单的问题——班级花名??册。某次考试后，老师得到了班上所有学生的成绩。通常情况下，它会记录在花名册之类的东西中。比如我们可以用一个结构体来记录每个同学的信息，比如姓名、考试成绩、性别等。然后创建一个结构数组来存储所有学生的信息。但是查询的时候出现了问题。假设我们要查询某个学生的成绩，比如张三的成绩，怎么办？张三对应的数据存放在数组的什么位置，我们无从知晓。这种情况下，我们只能遍历整个数组，依次判断，直到找到张三。本次枚举遍历查找方法的复杂度为。在数据量不大的情况下，这种方法当然没问题，现实中老师也是这样做的。但是，一旦数据量很大，查询次数很多，这样的复杂度是不可接受的。如何解决这个问题呢？算法大师们给出的答案就是哈希函数，所谓哈希函数，它只做一件事，就是映射。我们使用数组来存储所有学生的数据。最大的问题是我们不知道每条信息存放在哪里，只能遍历查询。假设我们可以设计一种将学生姓名映射到整数的算法。名字不同，映射后的结果也不同。所以通过使用这个，我们可以解决这个问题。例如，假设我们有一个哈希函数，它对“张三”的哈希结果为1，那么我们将张三的数据存储在数组下标1的位置。在查询“张三”时，我们再次调用hash函数，传入“张三”，得到1。1是张三数据存储的下标，那么我们只需要访问数组中对应的位置即可get是张三的数据。这种将非整数数据映射为整数的函数称为散列函数。哈希表了解了哈希函数之后，什么是哈希表呢？哈希表其实就是一个数组，也就是用来存放哈希后结果的数组。因为是数组，所以长度是固定的。但是哈希函数返回的范围往往要大得多。这时候我们可以使用取模的方法，将哈希函数的结果重新映射到数组的长度范围内。可以参考如下代码：structP{...};Pdata[10];//对数组长度取模intid=hash("张三")%10;data[id];Hash表的原理很容易理解，但是真正要用起来就会遇到一些问题。最大的问题就是hashcollision或者hashcollision的问题。哈希碰撞哈希函数可以将我们的输入映射成数字，我们可以保证相同的输入得到相同的映射结果。但是反过来说，不同输入映射的结果一定是不同的吗？我们可以从输入输出的集合来思考这个问题。理论上，我们输入的可能性在理论上是无限的。输出怎么样？哈希函数的返回类型往往是int32或int64，无论是哪一种，其取值范围都是有限的。由于输入的范围是无限的，而输出的范围是有限的，因此必然存在多个不同输入具有相同输出的情况。这种输入不同但散列后的结果相同的情况称为散列冲突。在哈希表中，由于我们还需要对哈希后的表长度取模，所以比较容易遇到冲突。所以指望好运不遇到冲突是不现实的。我们必须在数据结构中解决这个问题。用拉链法解决这个问题有几种方法，但从原理上来说只有两种方法，一种是拉链法，一种是检测法。所谓检测法，就是当我们插入新的数据，与已有元素发生哈希冲突时，取而代之的是检测另一个可行的位置。根据检测方法的不同，可分为线性检测、二次检测、双重哈希等方法。所以这些方法的本质都是一样的，都是碰撞之后再找一个空闲的位置使用。zipper方法则不同，它不检测其他位置，而是用一个链表将所有哈希值相同的元素存储在一起。所以完整的结构是一个链表数组，访问元素有两步。首先通过hash算法计算下标，找到对应位置的链表。然后在链表中进行遍历和插入操作。这里有个技巧，我们在修改链表中的元素时注意保证链表的顺序。这样我们在查找元素的时候就不用遍历整个链表了。当我们遇到比我们要找的元素还大的元素时，就说明我们要找的元素不存在。Java中的HashMap和C++中的unordered_map都是基于这样的哈希表实现的。哈希函数可以被认为是一个复杂的操作。当链表中的元素不多时，可以控制整体增删改查的复杂度。这种复杂度看起来很完美，但是有一个小问题。哈希表数组的长度是一个固定值，所以随着我们插入的元素越多，链表的长度必然会越来越长，长度是没有办法控制的。解决这个问题，通常的做法是扩容+rehash。比如Java中的HashMap会设置一个阈值，当表中的元素个数超过阈值时，就会触发扩容。展开时，数组的长度会加倍，然后读取当前所有元素，重新哈希，然后插入到展开后的哈希表中。扩容会带来额外的时间和空间开销。时间开销很容易理解。它是重新插入所有元素的操作。另外，哈希表扩容后加倍长度通常会造成浪费，因为我们无法保证表中的元素是均匀分布的。二叉搜索树我们要存储两个变量之间的映射关系。除了使用哈希表，还可以使用二叉搜索树。在C++中，这两个分别对应unordered_map和map。两者的用法基本相同，只是底层实现原理完全不同。前者基于哈希表，后者基于红黑树（二叉搜索树）。红黑树会直接将映射前后的结果打包存储为树中的节点，利用键值的大小关系构建二叉搜索树。所以会要求键值必须是可比较的。如果是我们自定义的类型，我们需要重载比较器，但是哈希表没有这个限制。平衡二叉搜索树的搜索复杂度比哈希表要高，但是二叉搜索树存储了节点之间的顺序，我们可以按照大小的顺序遍历所有的结果，而哈希表不行。关于哈希表原理的部分就到这里了。在下一篇文章中，我们将结合实例来体验地图的应用。感谢您的阅读，如果您喜欢，请帮助传播。算法学习之旅，与你同行。
