本专栏中，我们会围绕一系列基础数据结构展开讨论。这些精妙的数据结构如果我们每天只是把它们用作容器调库就太遗憾了，在面试算法题目时也会吃亏。本专栏希望能够帮助大家利用碎片事件熟悉这些数据结构背后的原理，欢迎大家在留言讨论！
除了数组之外，字典是我们最长打交道的数据结构了，因为从 KEY 到 VALUE 的映射无处不见，如现实生活中根据学号查询名字，计算机科学中根据域名查询 IP 地址。散列表是字典最常见的实现形式，同时散列相关算法在各种场合如负载分配、加密等都有非常精妙的应用。
本系列文章将会带领大家实现一个极简版散列表字典，并借此深入理解散列、散列表和它们要解决的问题。
关于抽象数据结构与实现算法：我们提到字典是一种抽象数据结构，而散列表是其背后的实现算法。抽象数据结构的意思大概是规定了这种数据结构支持那些操作，并且通常有速度要求。如数据结构字典主要要求能够快速插入或者删除一个键 KEY 及对应的值 VALUE. 而散列表则是背后如何实现这个要求而采用的算法。
散列技术不仅仅能用于实现一个字典，而除了散列表之外，字典也可以采用二叉搜索树、跳表等方法实现。我们将会在专栏之后的文章中进行介绍。
首先，我们考虑一个最简单的散列表：以非负整数为 KEY, 非负整数为 VALUE 的散列表（也就是 map<int, int>）。我们原则上其实是可以把这些 KEY VALUE 对全部保存下来，每次查询时进行一遍遍历的：
vector<pair<int, int>> pairs;
void put(int key, int val)) {
pairs.push_back({key, val});
}
int get(int key) {
int val = -1;
for(const auto& p: pairs) {
if(p.first == key) val = p.second;
}
return val;
}
这种每次查询都对整个表进行遍历的操作乍看之下可能十分笨拙, 但这种做法有时候是有价值的：它的写入性能非常高。如果我们需要实现一个经常写入但极少进行查询的数据结构，可以考虑这种实现方案，比如日志数据库。
如果我们内存够大，并且我们知道 KEY 的范围不大，我们可以直接开一个足够大的数组，然后直接把 KEY 做下标就行了（算法竞赛中很多高手只要内存够大就喜欢这么干）：
const int MAX_KEY = 1024;
vector<int> tab(MAX_KEY);
void put(int key, int val) {
tab[key] = val;
}
int get(int key) {
return tab[key];
}
但如果内存不够大，或者我们不知道 KEY 的取值范围应该怎么办？这时候我们面临的问题其实是把 KEY 从未知范围映射到一个有限的区间 [0,SIZE) 上，以便作为数组下标。
最简单的映射方式是，取个模 key%SIZE 就可以了。这个从 KEY 映射到一个坐标值的函数称为散列函数。但这显然会导致一个问题：不同的 KEY 可能会被映射到相同的下标上，可能出现冲突。
比如，如果散列表尺寸 SIZE=1024, 存入两个 KEY 分别为 2,1026, 则取模后两个数都是 2. 这就是散列表最烦的冲突问题，散列表很多复杂的工作都是在避免冲突、处理冲突。
一种冲突解决方案是，我们在散列表的每个坐标位置上存一个链表，然后插入元素时直接插入到这个链表里，查询时则在对应的链表遍历。如果散列函数足够随机，并且散列表中的元素不要太多，这个链表长度就不会太长，从而性能不会变的太差。
也是 C++ 标准库的解决方案。这时我们可以把这个链表称为桶。当然，现在需要把 KEY 也保存在散列表里了，因为同一个桶不能保证 KEY 是一样的：
const int SIZE = 1024;
vector<list<pair<int, int>>> tab(SIZE);
int hash(int x) { return x % SIZE; }
void put(unsigned key, int val) {
auto& bucket = tab[hash(key)];
for(auto& p: bucket) {
if(p.first == key) p.second = val;
return;
}
bucket.push_back({key, val});
}
int get(int key) {
auto& bucket = tab[hash(key)];
for(auto& p: bucket) {
if(p.first == key) return p.second;
}
return -1; // not found
}
这里，我们没有实现删除、遍历两种操作。删除操作对于有些散列表实现会非常麻烦，C++ 标准库等之所以采用链表这种直觉上就不太优雅的实现方法（称为拉链法）一部分原因就是这种方法删除比较方便，找到对应的元素从链表中删掉就可以了。
刚刚我们提到，散列表的散列函数如果足够随机，并且散列表不是太满，则散列表冲突不会太严重。简单的估算一下，如果散列表半满，然后插入一个新元素，则冲突概率是 1/2. 如果插入两个新元素，都发生冲突的概率只有 1/2*1/2=1/4, 依此类推，连续冲突的概率是指数级别下降的。
散列表真正的问题是，首先，散列表可能过满，没有多少空余位置，此时冲突概率会很大，因此散列表跟动态数组一样，插入的元素个数在达到一定限制时需要重新申请空间、将所有元素移动到新空间上去。
另外，散列函数可能不够随机，将很多具有某个特征的元素映射到相同的桶里，导致散列表性能变得很差。举个简单的例子，如果我们散列表尺寸是 100, 用来存放某种事件的发生时刻，而这个事件恰好是周期事件，每 50 秒发生一次，如果我们使用了上文中的取模散列函数，那么所有的事件发生时刻都会被散列到 2 个桶里，导致散列表性能变得跟遍历链表差不多。因此，足够随机同时计算开销不能太大的散列函数对于散列表非常重要。
下一篇文章，我们将会更加深入的讨论散列函数相关的问题。