哈希表（Hash Table）

哈希表也叫做散列表，它通过 key 能够快速访问 value。

我们知道数组通过 key 去搜索元素效率比较低，但是通过位置来访问速度是非常快的。例如：你要搜索值为 5 的元素，那么需要从头开始遍历，效率较低。但是，如要查找下标为 5 的元素，则直接计算位置偏移就能快速定位元素位置。哈希表就是利用了数组的这一特性，即：哈希表底层存储元素使用的也是数组，该数组我们也叫做散列表；

不同的 key 对应哪个位置呢？

数组的索引是 0-N 的数字来构成的，而我们的 key 则可能是字符串，也可能是其他类型的。此时就需要将不同类型的 key 转换为当前数组的下标，即：通过某个算法将 key 映射到某一个具体的数组位置。这个用于实现 key 到数组位置映射的函数叫做散列函数。在 C++ 标准库中实现 hash 函数，该函数使用 FNV-1a 哈希算法来计算 key 的哈希值，该函数已经对常见的基础类型实现哈希计算。如果要对自定义类型计算哈希值，则需要根据基础的 hash 实现来自行实现。下面是 hash 函数的简单用法：

#include <iostream>


int main()
{
	std::cout << std::hash<int>()(100) << std::endl;  // 14740360096876770257
	std::cout << std::hash<std::string>()("smith") << std::endl; // 4082712566559387408

	return 0;
}

有些同学说，计算得到的哈希值并不能够直接当做数组索引。是的，我们可以对该值取余数来得到其映射的位置索引。假如：散列表容量为 10，则只需要将哈希值对散列表容量取余数即可得到映射后的索引。

不同的 key 经过散列函数计算是否会出现映射到同一个数组位置的情况？
答案是肯定的，这也是实现哈希表时会碰到的一个问题，该问题叫做散列冲突。我们在设计实现哈希表时，会设置一个装填因子，该值为表的元素个数和表容量的比值，也就是说该值会随着哈希表中元素的增多而变大。该值越大，说明接下来再向哈希表填充元素时散列冲突的可能性就越大。所以，当哈希表的装填因子达到某个阈值时，我们就扩充容量，从而减小装填因子的值，减少散列冲突的情况。

当散列表容量扩容时，此时你会发现，所有的元素的散列位置都需要重新计算，这也是哈希表效率较低的地方。为了提高容器效率，减少重新散列的次数也是一个非常重要的因素。此时，可能就会想到空间换时间了。

即使增加装填因子也无法完全避免散列冲突的情况。当必须发生散列冲突时，我们仍然要对这种情况进行处理。常见的方法是通过链表法，即：每一个散列位置并不是存储一个元素，而是一个链表。当多个 key 散列到该位置时，我们就把这多个元素的 key/value 一同存储到链表中。查询时，先通过散列函数找到位置，再遍历位置上链表中的所有元素，找到指定 key 的元素。如下图所示：