侯捷C++ STL：哈希表（unordered_set,unordered_multiset,unordered_map,unordered_multimap）的底层实现_c++中三种哈希表的底层实现

哈希表的产生由于内存不够一一映射。于是乎在空间不足时取余数。

为了防止某一个链表过长，这里根据经验来制定规则。当插入的元素个数等于buckets时这时哈希表要扩容。扩容因子是两倍。但是buckets值尽量是质数，选择质数是为了尽量做到均匀散列。所以扩容后要找两倍大后附近的质数。编译器将空间扩容的空间大小都自己定义好了，不用重新计算空间，53-97-193…。

底层实现：
HashFcn：一个对象如何映射为一个号码/编号。hasher,key_equal,ExtractKey是function object大小理论是0，实际都是1个字节。vector内含三个指针，所以大小是12字节。_hashtable_iterator很像deque的迭代器，当走到边缘有能力回到控制中心，跳到下一个缓冲区（篮子）。这个迭代器里cur指向现在的元素，ht指向哈希表（一堆菜篮子），让其有能力指向像一个菜篮子。

hashtable的一个栗子：

Key与Value一致，所以ExtractKey设计为identity，直接返回。比较字符串（Key)是否相等，是要比较const char*指向的内容而不是指针是否一致。eqstr必须传回bool，所以要把strcmp封装。最难点是HashFcn的设计，应该结合具体项目。这里有提供hash，这里用到了模板的特化，这里每个都重载了操作符()，成为一个仿函数。
这里是数值当成编号。char,short都是数值，ASCII数值。

这里是使用MD5，尽量打散他们。自己设计时可以把它分解成基本类型，然后合成。c++的字符串string标准库没有提供hash。

modulus决定落在哪个篮子里。求余数

C++将hash_set等重新换了一个名字，变成这四个：unordered_set,unordered_multiset,unordered_map,unordered_multimap。

hash的栗子：

有一点需要记住，篮子（buckets）的个数永远大于元素的个数。