链地址法介绍
-
链地址法是除开放地址法之外的另一种解决哈希冲突的方法。开放地址法的弊端是群集/堆积无法避免，只能通过二次探测、双重散列等办法减少这种现象产生的概率。群集/堆积现象会使哈希表增删查效率变低（每一次插入都会插入在群集元素的末尾，它们会像滚雪球一样越滚越大，最坏的结果是时间复杂度降为 O(N)）。
-
相对于开放地址法将所有的元素都存进表里面，链地址法中所有的数据都不再直接存储在哈希表里，而是每个存储位置存入一个指针。
-
当没有数据映射到表里的位置时，这个存储的指针为空，当有数据映射到这个位置时，会头插在空指针的前面，然后这个位置会存储这个新的头插来的数据的地址。当有冲突的数据映射到这个位置时，也会头插在这一串数据之前。这些冲突的数据会构成一个链表，挂在哈希表这个位置的下面，构成一个'桶'。
-
比如映射一组数据到 M = 11 的表中：{ 12, 27, 16, 7, 1, 2, 5 }：
-
由于不是直接存储数据，所以它的负载因子不像开放地址法<1，它可以大于 1，没有限制。负载因子越大，哈希冲突的概率越高，空间利用率越高；负载因子越小，哈希冲突的概率越小，空间利用率越低。STL 中 unordered_xxx 的最大负载因子基本控制在 1，大于 1 就会扩容，接下来我们的实现也采用这个对负载因子的限制条件。
-
哈希桶它不会因为哈希冲突而抢占别的映射位置，所以它的增删查效率不会因为开放定址法里会出现的群集/堆积现象而降低。只不过它会在扩容（负载因子大于 1）的时候效率突然下降，因为扩容也跟开放定址法一样需要将数据重新映射一遍。
链地址法实现
它的流程基本和开放地址法的实现差不多：搭建框架->实现 Insert（解决普通插入 + 扩容 + 去重）、Find、Erase 函数->实现能够将 key 转化为 size_t 类型的仿函数。
搭建框架
template<class K, class V> struct Node { Node(const pair<K, V>& kv) :_kv(kv) ,_next(nullptr) { } pair<K, V> _kv; Node<K, V>* _next; };
template<class K, class V, class Hash = HashFunc<K>> class HashBucket {
typedef Node<K, V> Node;
public:
HashBucket() :_tables(, ) ,_count() { }
~() {
i = ;
Node* cur = _tables[i];
(i < _tables.()) {
(cur) {
Node* next = cur->_next;
cur;
cur = next;
}
i++;
}
}
:
vector<Node*> _tables;
_count;
};
