哈希表是基于映射思想的数据结构，核心在于哈希函数和冲突处理。文章阐述了哈希值的获取、常用哈希函数及冲突处理方法，如开放定址法和哈希桶。重点解析了 C++ STL 中 unordered_map 与 unordered_set 共享底层哈希桶模板的实现细节，包括自定义类型键值的提取与比较机制。
首先要理解哈希和哈希表有什么不同。哈希就是映射，是一种算法思想。哈希表就是映射表，是利用映射这种思想写出的一种数据结构。 所有的哈希表的算法流程都是类似的——拿到一个 key，利用哈希函数进行 hash(key)，得到的空间位置存放我们想要存放的数据 Value。 或者——拿到一个 key，利用哈希函数进行 hash(key)，从得到的空间位置取出我们想要查找的数据 Value。
理解哈希表，我们要分为三层去学习。第一层是理解哈希值，第二层是学习各种哈希函数，第三层是解决哈希冲突。 为什么要这么学习，因为 STL 哈希表中的底层哈希函数，其实都是对哈希值去进行 Hash。这个哈希值是一个整形，整形它本身就是哈希值；其他的自定义类型不管你 Key 的类型是 string，还是 vector。这些自定义类型，想要存储到哈希表中，上层最终都要让它们能够转为哈希值。 所以我们要先得到哈希值。然后再去使用哈希函数进行 hash 得到对应的映射位置。 另外，其实最基本的哈希表，逻辑上就是可以看作是一个数组。既然是数组，那么他就一定有大小。有大小，那么就一定存在 hash 的数据太多，数组空间不够的情况。这时再 hash，就有了哈希冲突。更不用提两个不同的自定义类型的数量远远大于哈希值的数量，自定义类型可能哈希值相同，就更会存在哈希冲突。所以，哈希是哈希表的功能。哈希冲突，是这个功能产生的一种可能存在的结果。所以两者存在因果的关系。 所以我们的理解链应该是：哈希值——》哈希函数——》哈希冲突
为什么要有哈希值？是因为哈希函数都是对一个整形进行哈希，比如直接定址、除留余数、平方取中，基数转换等等。最重要的是 STL 里面使用的也是除留余数（只不过不是传统的除留余数，大佬们有其他优化）。 我们在用 STL 的时候，如果想要对一个自定义类型进行哈希，那么就必须提供这个自定义类型向哈希值的转换方法。本篇文章中我们以后称为'转换策略'。 有了这个转换策略，就可以将自定义类型转化为一个哈希值。然后再将这个哈希值交给 STL 底层的哈希函数进行哈希。得到的结果经过哈希冲突的处理得到映射位置，这个映射位置就是最后这一次哈希要存储的位置了。 转化哈希值一般要定义为一个仿函数，然后作为 unordered_map 的第三个模板参数传进去。这样就能让一个任意类型能够去进行哈希了。 要注意转化哈希值要注意速度快，离散高。常见的转化策略比如 string 类型向整形转化的 BKDR 哈希，DJB 哈希、多成员复杂结构，结构中含有整形和 string 的 hash_combine、以及对含少量成员的异或组合。里面有嵌套容器的递归哈希等等。 这里只挑选熟悉的演示：
优点：实现简单，计算快；离散高，冲突少；不同种子可以计算出不同哈希值。 实现方法是选取一个种子 seed，然后对字符串里面的每一个字符进行处理：
size_t BKDRHash(const string &str) {
size_t seed = 131; // 31 131 1313 13131 131313
size_t hash = 1;
for (auto e : str) {
hash *= seed;
hash += e;
}
return hash & 0x7FFFFFFF; // 确保返回正数
}
这个种子的值可以是 31，131，1313，13131，131313...。
优点：实现简单，计算快。缺点：冲突率高
struct PointHash {
size_t operator()(const vector<int> &vec) {
int hash = 0;
for (auto e : vec) {
hash ^= (e << 1);
}
return hash;
}
};
优点是冲突率低，比较推荐。
template <typename T> void hash_combine(std::size_t& seed, const T& val) {
seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
struct Person {
std::string name;
int age;
// 重载==符号是为了在哈希桶的桶内 Find
bool operator==(const Person& p) const {
return name == p.name && age == p.age;
}
};
struct PersonHash {
std::size_t operator()(const Person& p) const {
std::size_t seed = 0;
hash_combine(seed, p.name);
hash_combine(seed, p.age);
return seed;
}
};
哈希表进行哈希有可能产生哈希冲突。但是我们说哈希其实就是映射，在数学中也有映射，一元一次方程，一元二次方程其实都是映射。有没有那么一种映射关系，不会存在两个哈希值同时映射到一个空间上呢？其实是有的，比如直接定址法。 直接定址法就是数学中一个具有单调性的函数，每一个哈希值都对应唯一的一个映射位置（x 映射唯一的 y）。这样做的方法有利有坏，好处是没有哈希冲突，因为每一个哈希都有唯一的数组下标与其对应；坏处是如果这一组整形很分散，假如有 1，99999，那么消耗的空间很大。所以对于直接定址法只适用于很集中的一组数。
对哈希表的大小的进行取模。得到一个结果，这个就叫做除留余数法。一个哈希表的大小为 m，就要取一个不大于 m 的，接近 m 的质数 p 作为模数。 假如一个哈希表大小为 10，那么 p 可以取 7。想要对键值为 12，13，1 的键值对进行映射，那么就是用他们模 7，然后就能得到映射的区域。
平方取中法是通过取关键字的哈希值的平方数中间几位作为哈希地址。 例子 1：假如有一个哈希表 1000（0 ~ 999），一个键值对的 key 为 1234。运用平方取中法就是：1234 ^ 2 = 1522756。因为哈希表的大小为 1000，那么就要取平方数的中间三位。取得 227，这个 227 就是最后的哈希地址。 例子 2：假如有一个哈希表的大小为 50（0 ~ 49），一个键值对的 key 为 68。运用平方取中法就是：68 * 68 = 4624。因为哈希表的大小为 50，那么就要去平方数的中间两位。取得 62。但是 62 比 50 大，所以我们可以让他们取模得到 12。最后 12 就是哈希地址。 平方取中法的优点：对于一些连续的键值能够将它们打散。不像除留余数法那样需要取值，防止取值不合适加剧冲突。
基数转换法就是将一个十进制数转化为其他进制的数字（比如十二进制，十三进制，十六进制），然后把转化后的数字看成是十进制，最后再把这个转化后的数字对哈希表的大小进行取模。但是如果转化后的数字里面有字母，就把这个字母看成他的 ASCII 码值。比如 255，转化成十六进制为 FF，看成十进制就是 7070。所以 255 进制基数转换后就是 7070。如果哈希表大小为 10，那么取模后就是 7070 % 10 = 0。
上面的所有的哈希函数除了直接定址法，都有一个问题。就是有可能两个不同的键值映射到了同一个哈希地址上面。这种情况就叫做哈希冲突。哈希冲突也是哈希表的核心问题之一。 哈希表里面有负载因子的概念。负载因子 = 已插入数据的个数 / 表大小。负载因子越大，越容易发生哈希冲突。因为负载因子大，说明哈希表中的数据很多，再插入数据时就很容易映射到有数据的地址，就发生了冲突。 很明显，如果插入数据映射到有数据的地址，就要重新映射，这样效率非常低。所以哈希冲突会影响哈希表的效率。那么为了缓解冲突带来的影响，哈希冲突有两种常见的解决方案：开放定址法、哈希桶。
解决方法：开放定址法就是当哈希冲突时，键值对会向后偏移。比如 a 本来映射到 1 号位，但是 1 号位被占用了，那么 a 就按照规律向后偏移，直到遇到一个没有被占用的位置。 （这里的规律有两种：一种叫做线性探测，即一格一格的向后遍历，1 号位被占用，去探测 2 号位。2 号位没有，去探测 3 号位，依此类推。第二种叫做二次探测，即按照平方数进行探测。假如探测位置为 i，那么线性探测就是每次 i++，二次探测就是每次 (i++) ^ 2。） 负载因子：负载因子通常需要小于 0.7。如果太大探测次数就很多，效率就会很低。甚至插入数据的时间复杂度可能逼近 O（n）了。 这里举个例子模拟开放定址法的处理方法： 此时已经插入了三个数据 1，12，3。如果又要插入一个 11，那么 11 % 10 等于 1。应该映射到 1 号位。但是 1 号位已经被占用了。假如是线性探测，那么就要响应后进行遍历，找到 2 号位，发现不为空，继续向后遍历。找到 3 号位，发现不为空，继续向后遍历。找到 4 号位，发现为空，说明找到了，那么就将 11 插入到这个位置就行了。 下面是开放定址法的 demo：
template <class K, class V> class HashData {
public:
/*状态值为什么要有 DELETE？因为要进行查找 Key。查找 Key 的时候，遇到 DELETE 和 EXIST 不会停止，遇到 EMPTY 停止查找，说明没有找到。因为查找操作，应该是只要该位置有过数据，就要向后查找，直到遇到一个 没有数据插入过的位置，就结束。因为会出现 Key 与这里的数据发生冲突，向后 便宜了，但是之后这里的数据又删除了。这样如果没有 DELETE，查找到这里就停止了 就错了。所以要有 DELETE。*/
enum State { EMPTY, EXIST, DELETE };
public:
pair<K, V> _kv;
State _state;
};
template <class K, class V> class HashTable {
public:
bool insert(const pair<K, V> &kv) {
/*使用开放定址法：会不会找不到合适的位置，不会。因为有负载因子。哈希表要判断负载因子，负载因子越大，哈希冲突越多，效率越低。负载因子越小，哈希冲突越小，效率越高，但是会占用大量空间。*/
if (_tables.size() == 0 || (_n * 10) / _tables.size() >= 7) {
/*超过了负载因子，那么就要扩容了。*/
UpMemory();
}
if (Find(kv.first)) return false;
/*插入主逻辑，就是向后去找，直到遇到没有数据的地方。*/
int hashi = kv.first % _tables.size();
while (_tables[hashi]._state == HashData<K, V>::State::EXIST) {
hashi++;
hashi %= _tables.size();
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = HashData<K, V>::State::EXIST;
_n++;
}
HashData<K, V> *Find(const K &key) /*查找，如果找到了，就返回对应的地址，如果没找到，就返回 nullptr*/
{
/*这里不用循环遍历找？直接 hashi，直到 hashi 对应的值是 key*/
int hashi = key % _tables.size();
/*先映射，这个位置应该是原本应该在的位置，但是可能被别人占用了，这个 时候就要向后遍历，只要一发现，这个位置不是空的，DELETE 也算，因为 DELETE 说明这个位置之前有数据，不知道这个数据在元数据之前是否 插入的。就要继续向后找。*/
int tmp = hashi;
while (_tables[hashi]._state != HashData<K, V>::EMPTY) {
if (_tables[hashi]._state == HashData<K, V>::EXIST && _tables[hashi]._kv.first == key) {
return &_tables[hashi];
}
hashi++;
hashi %= _tables.size();
if (hashi == tmp) return nullptr;
}
return nullptr;
}
bool Erase(const K &key) /*删除操作，查找到对应的地址，然后就将对应的地址位置变成 Delete*/
{
HashData<K, V> *pdata = Find(key);
if (pdata == nullptr) return false;
/*找到了，不是空，那么久 false*/
pdata->_state = HashData<K, V>::DELETE;
--_n;
return true;
}
void Order() {
cout << _n << endl;
for (int i = 0; i < _tables.size(); i++) {
if (_tables[i]._state == HashData<K, V>::EXIST) cout << _tables[i]._kv.first << " : " << _tables[i]._kv.second << endl;
}
}
private:
void UpMemory() {
/*扩容步骤：创建一段新空间 重新映射 删除旧空间 */
int newsize = (_tables.size() == 0) ? 5 : 2 * _tables.size();
/*如果空间为零就初始化空间为 5，否则就扩容 2 倍。*/
//*创建一个新的哈希表，让这个哈希表去扩容 newsize 个大小的空间并把是数据都重新插入一遍。*/
HashTable<K, V> NewHT;
NewHT._tables.resize(newsize);
for (int i = 0; i < _tables.size(); i++) {
if (_tables[i]._state == HashData<K, V>::EXIST) {
NewHT.insert(_tables[i]._kv);
}
}
/*新表处理完成后，新表的_tables 里面就是扩容后我们需要的哈希表。所以把新表的_tables 和哈希表的_tables 换一下位置。*/
_tables.swap(NewHT._tables);
}
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
public:
static void Test1() {
HashTable<int, int> hash;
hash.insert({1, 1});
hash.insert({12, 1});
hash.insert({13, 1});
hash.insert({16, 1});
hash.insert({161, 1});
hash.insert({162, 1});
hash.insert({163, 1});
hash.insert({164, 1});
hash.insert({165, 1});
hash.insert({16, 1});
hash.insert({-16, 1});
hash.Erase(16);
hash.Erase(161);
hash.Erase(162);
hash.Erase(163);
hash.insert({16, 1});
hash.Erase(16);
hash.insert({16, 1});
hash.Order();
}
};
如果说开放定址法的结构是一个数组。那么哈希桶本质上其实结构已经不单单是一个数组了，而是一个数组，但是这个数组里面挂上了一串串链表。 解决方法：哈希桶解决哈希冲突的方法是在数组本该存放数据的位置不放数据了，改为数据节点的指针。以后如果有数据映射到了这个位置，就创建节点，将数据链入到该位置的链表里面。因为链表挂在数组上面就像一个桶，所以就叫做哈希桶。数组里面的每一个元素都叫做一个桶。 哈希桶效率比开放定址法要高。在负载因子为 1 的情况下（STL 下也为 1），只要不出现极端情况，插入几百万条随机数据，最长的桶的长度也会保持在 6，7，8 左右。也就是说，每次我们 hash 查找数据，是一个常数级别的时间复杂度。 C++ unordered_map 和 unordered_set 的底层就是用的哈希桶。接下来，我们就要讲解一下，在 STL 中，是怎么实现哈希桶的。
首先，它们的定义分别是：
/*哈希桶*/
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
/*unordered_set*/
template<class Key, class Hash, class Pred.......>
/*unordered_map*/
template<class Key, class T, class Hash, class Pred......>
先来只看哈希桶里面的前两个模板参数。这里的 Key 和 Value 并不是传统意义上的键值对。因为 set 没有键值对，只有键值。而 map 有键值对。这就说明 unordered_set 不需要两个模板参数，unordered_map 需要两个模板参数。所以，为了解决 unordered_set 和 unordered_map 复用模板类的问题，大佬们把 unordered_set 里面那个哈希桶的第二个模板参数也传成了 Key。把 unordered_map 里面那个哈希桶的第二个模板参数直接传承了 pair<Key, T> 即：
template<class Key, class Hash, class Pred.....>
class unordered_set {
//省略...........
typedef HashBucket<Key, Key, ....> //省略......
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
//省略...........
typedef HashBucket<Key, pair<Key, T>, ....> //省略......
};
这样有有什么用？下面讲解： 对于哈希桶的查找和删除，是一定，并且只会用到 Key，不管上层存储的是键值对还是单个键。就是利用键 Key 进行查找和删除。
/*哈希桶*/
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
/*省略.........*/
Find(const Key &key);
Erase(const Key &key);
/*省略.........*/
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
//省略...........
typedef HashBucket<Key, Key, ....> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
//省略......
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
//省略...........
typedef HashBucket<Key, pair<Key, T>, ....> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
//省略......
};
但是对于插入，unordered_set 和 unordered_map 是不一样的。因为前者插入的是一个 Key 类型数据，而后者插入的是一个 pair<Key, T> 类型的数据。正好 unordered_set 里面的哈希桶第二个模板参数是 Key，又恰好 unordered_map 里面的哈希桶的第二个模板参数是 pair<Key, T>。所以，在哈希桶内部的 Insert 的参数是 Value 类型的数据。但是在外层，其实 unordered_set 传的是 Key，unordered_map 传的是 pair<Key, T>。如下：
/*哈希桶*/
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
/*省略.........*/
Find(const Key &key);
Erase(const Key &key);
Insert(const Value &data);
/*省略.........*/
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
//省略...........
typedef HashBucket<Key, Key, ....> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
/*调用的哈希桶的 Insert，传的是 Key 类型数据，此时哈希桶的 Insert 用的也是 unordermap 传给他的 pair<Key, T>*/
Insert(const Key &data) { return _ht.Insert(data); }
//省略......
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
//省略...........
typedef HashBucket<Key, pair<Key, T>, ....> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
/*调用的哈希桶的 Insert，传的是 pair<Key, T> 类型数据，此时哈希桶的 Insert 用的也是 unordermap 传给他的 pair<Key, T>*/
Insert(const pair<K, T> &data) { return _ht.Insert(data); }
//省略......
};
上面我们讲解的是大佬们如何解决的 unordered_set 和 unordered_map 公用一个底层哈希桶的问题，是框架。现在我们讲解了这个框架的结构。然后就要去实现里面的细节。
这里有两处细节，首先第一处细节：Insert 怎么得到键值？ 我们上面说哈希桶的删除和查找，是一定，并且是只会用到键 Key 的。不管上层存储的是键值对还是单个键。所以 unordered_set 和 unordered_map 的 Find 和 Erase 直接按照逻辑实现代码就行。 而哈希桶的插入 unordered_set 和 unordered_map 传入的类型不同。那么得到键的方法就不一样了。unordered_set 是直接拿过来用就行。unordered_map 是要拿到里面的 first。这个时候聪明的小伙伴已经想到办法了，没错，就是利用仿函数。对于哈希桶，它要对外提供一个模板参数来来接受获取 Value 里面键值的方法。这，就是我们的哈希桶里面的第四个模板参数 ExtractKey（第三个是一个空间配置器，与本节没有关系）。以后，unordered_set 传送他的拿到键值的方法，unordered_map 传送他的拿到键值对方法，哈希桶只管接收，然后 Insert 想要用键 Key 的时候，就用传过来的方法对 data 进行处理，就能拿到这个键 Key。
/*哈希桶*/
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
/*省略.........*/
Find(const Key &key);
Erase(const Key &key);
Insert(const Value &data);
/*省略.........*/
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
//省略...........
///////
struct KeyOfValue {
const K &operator()(const K &key) { return key; }
};
///////
typedef HashBucket<Key, Key, Alloc, KeyOfValue..> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
/*调用的哈希桶的 Insert，传的是 Key 类型数据，此时哈希桶的 Insert 用的也是 unordermap 传给他的 pair<Key, T>*/
Insert(const Key &data) { return _ht.Insert(data); }
//省略......
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
//省略...........
////////////
struct KeyOfValue {
const K& operator()(const pair<K, V> &_kv) { return _kv.first; }
};
/////////////
typedef HashBucket<Key, pair<Key, T>, Alloc, KeyOfValue, ...> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
/*调用的哈希桶的 Insert，传的是 pair<Key, T> 类型数据，此时哈希桶的 Insert 用的也是 unordermap 传给他的 pair<Key, T>*/
Insert(const pair<K, T> &data) { return _ht.Insert(data); }
//省略......
};
最后一个细节，unordered_set 和 unordered_map 是怎么处理自定义类型的键的？ 其实本篇文章在一开始就在为这一点做铺垫了，就是上面的哈希值。对于任意的自定义类型，都可以作为键，但是前提要实现这个自定义类型向整形转化的仿函数和自定义类型的==重载或 equal 仿函数。 哈希桶的底层插入或者查找或者删除，哈希函数用的是类似于除留余数法（大佬们肯定做了特殊处理），如果是一个整形，比如 10，桶大小为 5。那么 10 % 5 == 0. 此时这个值就放到 0 号桶里面了。下面 insert 的伪代码
insert(const Value &data) {
KeyOfT key; //_tables 是整个数组，里面存放了一串串的桶，_tables.size() 是桶的个数
int hashi = key(data) % _tables.size(); /*得到存储的桶*/
//头插将新数据链入桶内
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
}
但是一个自定义类型是不能进行取模的。所以大佬们就想到了办法：哈希值。就是先将自定义类型转化成一个哈希值。然后用哈希值去取模找桶。所以哈希桶就有提供了第五个模板参数 Hash。并且，又因为自定义类型是上层使用 unordered_map 和 unordered_set 的人自定义的，所以必须由上层的人提供这个转化策略。继而 unordered_map 和 unordered_set 也都新增了一个模板参数 Hash。这个模板参数就是 unorder_set 或者 unordered_map 接收到上层传过来的转化策略。然后 unordered_map 或者 unordered_set 传给哈希桶，哈希桶就能用这个方法拿到键的哈希值，然后就能找桶了。
/*哈希桶*/
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
/*省略.........*/
Find(const Key &key);
Erase(const Key &key);
Insert(const Value &data);
/*省略.........*/
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
//省略...........
///////
struct KeyOfValue {
const K &operator()(const K &key) { return key; }
};
///////
typedef HashBucket<Key, Key, Alloc, KeyOfValue, Hash, ...> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
/*调用的哈希桶的 Insert，传的是 Key 类型数据，此时哈希桶的 Insert 用的也是 unordermap 传给他的 pair<Key, T>*/
Insert(const Key &data) { return _ht.Insert(data); }
//省略......
};
template<class Key, class T, class Hash, class Pred.....>
class unordered_map {
//省略...........
////////////
struct KeyOfValue {
const K& operator()(const pair<K, V> &_kv) { return _kv.first; }
};
/////////////
typedef HashBucket<Key, pair<Key, T>, Alloc, KeyOfValue, Hash, ...> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
/*调用的哈希桶的 Insert，传的是 pair<Key, T> 类型数据，此时哈希桶的 Insert 用的也是 unordermap 传给他的 pair<Key, T>*/
Insert(const pair<K, T> &data) { return _ht.Insert(data); }
//省略......
};
但是，这里还存在一个问题，就是查找的问题。查找要判断一个数据是否存在，就一定会用到比较。这个比较不能用哈希值进行比较。因为哈希值是整形，是有限的，而自定义类型的对象是无限的。所以一定会存在两个不同的自定义类型对象有着相同的哈希值。所以想要查找这个数据存在不存在，还是要用原生类型的比较。这里哈希桶和 unordered_map, unorder_set 都提供了一个模板参数 Pred。就是一个 equal 的仿函数。这里其实也可以直接重载==符号。
/*哈希桶*/
template<class Key, class Value, class Alloc, class ExtractKey, class Hash, class __Pred, .....>
class HashBucket {
/*省略.........*/
Find(const Key &key);
Erase(const Key &key);
Insert(const Value &data);
/*省略.........*/
};
template<class Key, class Hash, class Pred.....>
class unordered_set {
//省略...........
///////
struct KeyOfValue {
const K &operator()(const K &key) { return key; }
};
///////
typedef HashBucket<Key, Key, Alloc, KeyOfValue, Hash, Pred, ...> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
/*调用的哈希桶的 Insert，传的是 Key 类型数据，此时哈希桶的 Insert 用的也是 unordermap 传给他的 pair<Key, T>*/
Insert(const Key &data) { return _ht.Insert(data); }
//省略......
};
template<class Key, class T, class Hash, class Pred....>
class unordered_map {
//省略...........
////////////
struct KeyOfValue {
const K& operator()(const pair<K, V> &_kv) { return _kv.first; }
};
/////////////
typedef HashBucket<Key, pair<Key, T>, Alloc, KeyOfValue, Hash, Pred, ...> HT;
HT _ht; /*定义一个哈希桶对象*/
Find(const Key &key) { return _ht.Find(key); }
Erase(const Key &key) { return _ht.Erase(key); }
/*调用的哈希桶的 Insert，传的是 pair<Key, T> 类型数据，此时哈希桶的 Insert 用的也是 unordermap 传给他的 pair<Key, T>*/
Insert(const pair<K, T> &data) { return _ht.Insert(data); }
//省略......
};
以上，就是关于哈希表理解的全部内容。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online