STL容器之unordered_set类

1、unordered系列关联式容器

前面在讲map和set有提到过关联式容器，即使用键值对即< Key , Value >的形式来存储和访问数据，按照键值进行组织和查找。在数据检索时比序列式容器效率更高。常见的unordered系列关联式容器包括：

1. unordered_map: 哈希表实现的键值对集合，查找速度比map快，但是不保证元素的顺序。

2. unordered_set: 哈希表实现的关键字集合，查找速度比set快，但是不保证元素的顺序。

注意：map和set的结构是树形结构的关联式容器，用的是红黑树作为底层结构。unordered_map和unordered_set的结构是哈希结构的关联式容器，用的是哈希表作为底层结构。

---

2、unordered_set

2.1、unordered_set介绍

unordered_set的文档介绍

1. unordered_set是以不特定顺序存储独特元素的容器，并允许根据其值快速检索单个元素。

2. 在unordered_set中，元素的值同时是其键，唯一标识它。键是不可变的，因此，unordered_set中的元素不能在容器中修改 – 不过，它们可以插入和删除。

3. 在内部，unordered_set中的元素没有按任何特定顺序排序，而是根据其哈希值组织成桶，以便通过其值直接快速访问单个元素（平均时间复杂度恒定）。

4. unordered_set容器比set容器更快地通过其键访问单个元素，但是它通常在遍历元素子集的范围迭代方面效率较低。

5. 容器中的迭代器至少是前向iterators。

---

2.2、unordered_set的使用

2.2.1、unordered_set的常见构造

(constructor )函数名称	接口说明
unordered_set ( size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() )	构造空的unordered_set
unordered_set ( InputIterator first, InputIterator last, size_type n = /* see below */, const hasher& hf = hasher(), const key_equal& eql = key_equal(), const allocator_type& alloc = allocator_type() )	用[first,last)迭代区间构造unordered_set
unordered_set ( const unordered_set& ust )	unordered_set的拷贝构造

void test_us1() {unordered_set<int> us;int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};for (auto e: a) {us.insert(e);}for (auto e: us) {cout << e << " ";}cout << endl;cout << "=======================" << endl;unordered_set<int> us1(us.begin(), us.end());for (auto e: us1) {cout << e << " ";}cout << endl;cout << "=======================" << endl;unordered_set<int> us2(us1);for (auto e: us2) {cout << e << " ";}cout << endl;}

---

2.2.2、unordered_set的迭代器

函数名称	接口说明
begin()+end()	获取第一个元素位置的iterator和获取最后一个元素的后一个位置的iterator
cbegin()+cend()	获取第一个元素位置的const_iterator和获取最后一个元素的后一个位置的const_iterator

void test_us2() {unordered_set<int> us;int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};for (auto e: a) {us.insert(e);}unordered_set<int>::iterator it = us.begin();while (it != us.end()) {cout << *it << " ";++it;}cout << endl;cout << "=======================" << endl;unordered_set<int>::const_iterator it1 = us.cbegin();while (it1 != us.cend()) {cout << *it1 << " ";++it1;}cout << endl;
}

---

2.2.3、unordered_set的容量

函数名称	接口说明
empty	判断当前unordered_set是否为空
size	获取unordered_set的元素个数

void test_us3() {unordered_set<int> us;int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};for (auto e: a) {us.insert(e);}cout << us.empty() << endl;cout << us.size() << endl;us.clear();cout << us.empty() << endl;cout << us.size() << endl;
}

---

2.2.4、unordered_set的增删查

函数名称	接口说明
insert	在unordered_set中插入元素x，实际上插入的是<x,x>键值对，如果插入成功，返回<x插入位置,true>，插入失败说明unordered_set中已经有x，返回<x在unordered_set的位置,false>
erase	删除unordered_set中pos位置的元素，或者删除值为val的元素
swap	交换两个unordered_set的元素
clear	将unordered_set的元素置空
find	返回unordered_set中值为x的元素位置
count	返回unordered_set中值为x的元素个数

void test_us4() {unordered_set<int> us;int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};for (auto e: a) {us.insert(e);}for (auto e: us) {cout << e << " ";}cout << endl;cout << "========================" << endl;us.erase(1);us.erase(2);auto pos = us.find(11);us.erase(pos);for (auto e: us) {cout << e << " ";}cout << endl;cout << "========================" << endl;unordered_set<int> us1;us1.insert(100);us1.swap(us);cout << "us:";for (auto e: us) {cout << e << " ";}cout << endl;cout << "us1:";for (auto e: us1) {cout << e << " ";}cout << endl;cout << "========================" << endl;cout << us1.count(5) << endl;cout << us1.count(1) << endl;cout << "========================" << endl;us1.clear();cout << "us:";for (auto e: us) {cout << e << " ";}cout << endl;cout << "us1:";for (auto e: us1) {cout << e << " ";}cout << endl;}

---

2.2.5、unordered_set的桶操作

函数名称	接口说明
bucket_count	返回unordered_set中的桶的个数
bucket_size	返回第n个桶中元素的个数
bucket	返回元素k在哪个桶

void test_us5() {unordered_set<int> us;int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};for (auto e: a) {us.insert(e);}cout << us.bucket_count() << endl;cout << us.bucket_size(1) << endl;cout << us.bucket(11) << endl;
}

---

3、unordered_multiset

这个其实就和set和multiset一样，就是比unordered_set多了一个可以存重复值的特性。

演示一下：

void test_ums1() {unordered_multiset<int> ums;int a[]{1, 2, 5, 7, 2, 3, 5, 8, 2, 11, 9};for (auto e: a) {ums.insert(e);}for (auto e: ums) {cout << e << " ";}cout << endl;
}

---

4、unordered_set的底层结构

unordered系列的关联式容器之所以效率比较高，是因为其底层使用了哈希结构。

4.1、哈希概念

哈希（Hash）是一种常见的数据结构和算法，用于快速地将数据映射到固定大小的索引值，通常是一个整数。哈希函数将输入数据映射到索引值，这使得可以快速地在数据结构中查找、插入或删除数据，而无需遍历整个数据结构。

哈希是一种将任意长度的输入数据通过哈希函数转换为固定长度的输出数据的过程。哈希函数将输入数据映射到一个称为哈希值或散列值的固定大小的值。哈希函数通常设计为能够尽可能均匀地将不同的输入映射到不同的输出，以减少哈希碰撞的可能性。

例如：

问题：按上述映射，插入10会出现什么问题？

答：因为10%8=2，而2的位置已经被占了，那么我们就要想办法解决这个问题。常见有两个方案：

方案一：使用开放定址法，从2的位置向后找到一个没有使用的位置插入。

方案二：使用拉链法（哈希桶），让数组每个位置存的都是一个结点的指针，当出现映射到同一个位置时，直接进行头插。

---

4.2、哈希冲突

哈希冲突是指两个不同的输入数据经过哈希函数计算后，得到了相同的哈希值。由于哈希函数将不同的输入映射到有限的输出空间，而输入空间是无限的，所以在实际应用中，哈希冲突是不可避免的。

解决哈希冲突的常见方法包括：

1. 链表法（Separate Chaining）： 将具有相同哈希值的数据存储在同一个位置上，形成链表或其他数据结构。这样，当发生哈希冲突时，可以将冲突的数据连接在一起，不会丢失数据。
2. 开放地址法（Open Addressing）： 当发生哈希冲突时，通过探测序列（如线性探测、二次探测、双重哈希等）在哈希表中寻找另一个可用的位置来存储冲突的数据。

---

4.3、哈希函数

哈希函数是将输入数据映射到哈希值的函数。一个好的哈希函数应该尽可能地均匀地将输入映射到输出，以减少哈希冲突的发生。哈希函数的选择取决于应用的需求和数据的特性。

常见的哈希函数的构造方法：

1. 直接定址法（常用）：取关键字或关键字的某个线性函数值为哈希地址。即 H(key)=key 或 H(key)=a*key+b，其中a和b为常数。这种方法简单直观，但仅适用于关键字分布基本均匀的情况。若关键字的分布极不均匀，则哈希表中有的区域会很拥挤，而有的区域则可能空闲很多。
2. 除留余数法（常用）：选取关键字除以某个整数p的余数作为哈希地址。哈希函数的一般形式为：Hash(key)=key % p。这种方法的关键在于选择合适的p，通常要求p小于等于哈希表长度m，并且接近m。
3. 数字分析法：取关键字中某些取值较分散的数字位作为哈希地址。这种方法适合于所有关键字已知的情况，分析数字分布的情况，选择某些位作为哈希地址，尽量避免冲突。
4. 平方取中法：取关键字平方的中间几位作为哈希地址。具体取多少位视实际要求而定。
5. 折叠法：将关键字分割成位数相同的几段，然后将这些段叠加求和作为哈希地址。段的位数取决于哈希地址的位数，由实际需要而定。
6. 乘法哈希法：将输入乘以一个常数，再取结果的小数部分或整数部分作为哈希值。这种方法能够在一定程度上消除冲突，并且适用于输入数据分布不均匀的情况。

---

4.4、解决哈希冲突

4.4.1、开放地址法（Open Addressing）

开放地址法（Open Addressing）： 当发生哈希冲突时，通过探测序列（如线性探测、二次探测、双重哈希等）在哈希表中寻找另一个可用的位置来存储冲突的数据。

以下是开放定址法的一些常见方法：

1. 线性探测（Linear Probing）：

• 当发生碰撞时，依次检查下一个槽位，直到找到一个空槽位。
• 探测序列公式为：h(k,i) = (h′(k)+i) mod m其中 h′(k)初始哈希函数的值，i 是探测的步长， m 是哈希表的大小。
• 线性探测可能会产生一系列聚集现象，导致槽位的线性排列。

2. 二次探测（Quadratic Probing）：

• 当发生碰撞时，通过一个二次探测序列来寻找下一个槽位。
• 探测序列公式为：h(k,i)=(h′(k)+c1⋅i+c2⋅i^2) mod m，其中 c1 和 c2 是常数，m 是哈希表的大小。
• 二次探测在碰撞发生后，会以二次的步长来搜索下一个空槽位，有助于减少线性探测的聚集现象。

3. 双重哈希（Double Hashing）：

• 使用两个哈希函数来计算探测序列的步长。
• 探测序列公式为：h(k,i)=(h1(k)+i⋅h2(k)) mod m其中 h1(k) 和 h2(k) 是两个不同的哈希函数，m 是哈希表的大小。
• 双重哈希通常能够更好地减少聚集现象，并且对于大部分数据集合，具有较好的性能。

这里我们就只介绍线性探测法：

就像前面我们介绍的哈希概念中，当插入10的时候发生冲突了，怎么解决？我们从位置2顺序向后找到一个空位置填入就行。

这里我们需要考虑到一个问题！元素删除：当一个元素删除过后，我们直接给他删了吗？实际上是不行的，因为如果直接删除了，也就是这个位置置空了，但是它后面位置的值又可能也是之前发生冲突探测过来的值，那么下次找这些值就找不到了！所以我们的解决办法是给数组的每个位置添加一个标志位：存在（EXIST）、删除（DELETE）、空（EMPTY）。这样就在删除的时候，只需要把这个位置的标志设置为DELETE就行，即只要这个位置标志不是EMPTY就可以继续向后探测！

因此有每个元素的结构体：

enum State {EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData {pair<K, V> _kv;State _s;HashData(const pair<K, V> &kv = pair<K, V>()) : _kv(kv), _s(EMPTY) {}
};

哈希表：这里给了一个成员变量_n，用来记录当前哈希表中的元素个数

template<class K, class V>
class HashTable_OpenAddr {typedef HashData<K, V> Node;
public:HashTable_OpenAddr(size_t size = 10) {_tables.resize(size);}Node *Find(const K &key) {int hashi = key % _tables.size();while (_tables[hashi]._s == EXIST) {if (_tables[hashi]._kv.first == key)return &_tables[hashi];hashi++;hashi %= _tables.size(); // 可能从尾部到头部了}return nullptr;}bool Insert(const pair<K, V> &kv) {if (Find(kv.first))return false; // 存在就不插入了if (_n * 10 / _tables.size() >= 7) {// 装填因子为0.7，扩容size_t newSize = 2 * _tables.size();
//            _tables.resize(newSize);// 把原数据重新放到新空间中HashTable_OpenAddr<K, V,HashMode> newHashTable(newSize);for (auto &e: _tables) {if (e._s == EXIST) {newHashTable.Insert(e._kv);}}_tables.swap(newHashTable._tables);}int hashi = kv.first % _tables.size();while (_tables[hashi]._s == EXIST) {hashi++;hashi %= _tables.size(); // 可能从尾部到头部了}// 现在hashi的位置是空的或者是删除了的_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}bool Erase(const K &key) {Node *ret = Find(key);if (ret) {--_n;ret->_s = DELETE;return true;} else {return false;}}private:vector<Node> _tables;size_t _n = 0;
};

这里还会有一个问题：如果我们插入的值不是int类型呢？比如string类型，那么key就是string，直接插入将会报错。

我们可以设计一个仿函数，将string类型的key映射位size_t类型的值，来用来映射位置。

// 默认的取key的用来哈希的值
template<class K>
struct HashNodeFunc {size_t operator()(const K &key) {return (size_t) key;}
};//特化string类型的key的用来哈希的值
template<>
struct HashNodeFunc<string> {size_t operator()(const string &str) {size_t hash = 0;for (auto e: str) {e *= 131;hash += e;}return hash;}
};

这里string的特化函数，用的是BKDR方法（有大佬测试过这个方法取的值引起冲突的概率最小），其他的方法在这个网站字符串的Hash函数

因此我们的代码变为：

enum State {EMPTY,EXIST,DELETE
};// 哈希表 --- 开放定址法
template<class K, class V>
struct HashData {pair<K, V> _kv;State _s;HashData(const pair<K, V> &kv = pair<K, V>()) : _kv(kv), _s(EMPTY) {}
};template<class K>
struct HashNodeFunc {size_t operator()(const K &key) {return (size_t) key;}
};template<>
struct HashNodeFunc<string> {size_t operator()(const string &str) {size_t hash = 0;for (auto e: str) {e *= 131;hash += e;}return hash;}
};template<class K, class V, class HashMode = HashNodeFunc<K> >
class HashTable_OpenAddr {typedef HashData<K, V> Node;
public:HashTable_OpenAddr(size_t size = 10) {_tables.resize(size);}Node *Find(const K &key) {HashMode hs;int hashi = hs(key) % _tables.size();while (_tables[hashi]._s == EXIST) {if (_tables[hashi]._kv.first == key)return &_tables[hashi];hashi++;hashi %= _tables.size(); // 可能从尾部到头部了}return nullptr;}bool Insert(const pair<K, V> &kv) {if (Find(kv.first))return false; // 存在就不插入了HashMode hs;int hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._s == EXIST) {hashi++;hashi %= _tables.size(); // 可能从尾部到头部了}// 现在hashi的位置是空的或者是删除了的_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}bool Erase(const K &key) {Node *ret = Find(key);if (ret) {--_n;ret->_s = DELETE;return true;} else {return false;}}private:vector<Node> _tables;size_t _n = 0;
};

如果我们需要插入自定义类型，比如Date类型的元素，我们可以自己写一个哈希函数来传入模版参数。

如下，包含测试：

class Date {
public:Date(int year = 1999, int month = 11, int day = 14) : _year(year), _month(month), _day(day) {}int getYear() const {return _year;}int getMonth() const {return _month;}int getDay() const {return _day;}bool operator==(const Date& d) {return _year == d._year && _month == d._month && _day == d._day;}private:int _year;int _month;int _day;
};struct HashNodeDate{size_t operator()(const Date &d) {size_t hash = 0;hash += d.getYear() * 131;hash += d.getMonth() * 131;hash += d.getDay() * 131;return hash;}
};void test_Hash_Table4() {Date *d[] = {new Date(), new Date(1998, 1, 1), new Date(2000, 12, 11)};HashTable_OpenAddr<Date, Date, HashNodeDate> hs;for (auto e: d) {hs.Insert(make_pair(*e, *e));}hs.Erase(*new Date(1998, 1, 1));
}

当哈希表什么时候进行扩容？怎么扩容？

这里涉及到一个概念：装填因子。

装填因子 = 存入哈希表的元素个数/哈希表长。

对于开放定址法，装填因子是一个特别重要的元素，应该严格控制在0.7～0.8之间。

所以我们这里在装填因子为0.7的时候进行扩容，2倍扩容。

扩容方式是遍历旧表，状态为EXIST的元素插入到新表，按新表的映射方式进行插入。

代码如下：

if (_n * 10 / _tables.size() >= 7) {// 装填因子为0.7，扩容size_t newSize = 2 * _tables.size();
//            _tables.resize(newSize);// 把原数据重新放到新空间中HashTable_OpenAddr<K, V,HashMode> newHashTable(newSize);for (auto &e: _tables) {if (e._s == EXIST) {newHashTable.Insert(e._kv);}}_tables.swap(newHashTable._tables);
}

因此开放定址法的哈希表的整体代码为：

enum State {EMPTY,EXIST,DELETE
};// 哈希表 --- 开放定址法
template<class K, class V>
struct HashData {pair<K, V> _kv;State _s;HashData(const pair<K, V> &kv = pair<K, V>()) : _kv(kv), _s(EMPTY) {}
};template<class K>
struct HashNodeFunc {size_t operator()(const K &key) {return (size_t) key;}
};template<>
struct HashNodeFunc<string> {size_t operator()(const string &str) {size_t hash = 0;for (auto e: str) {e *= 131;hash += e;}return hash;}
};template<class K, class V, class HashMode = HashNodeFunc<K> >
class HashTable_OpenAddr {typedef HashData<K, V> Node;
public:HashTable_OpenAddr(size_t size = 10) {_tables.resize(size);}Node *Find(const K &key) {HashMode hs;int hashi = hs(key) % _tables.size();while (_tables[hashi]._s == EXIST) {if (_tables[hashi]._kv.first == key)return &_tables[hashi];hashi++;hashi %= _tables.size(); // 可能从尾部到头部了}return nullptr;}bool Insert(const pair<K, V> &kv) {if (Find(kv.first))return false; // 存在就不插入了if (_n * 10 / _tables.size() >= 7) {// 装填因子为0.7，扩容size_t newSize = 2 * _tables.size();
//            _tables.resize(newSize);// 把原数据重新放到新空间中HashTable_OpenAddr<K, V,HashMode> newHashTable(newSize);for (auto &e: _tables) {if (e._s == EXIST) {newHashTable.Insert(e._kv);}}_tables.swap(newHashTable._tables);}HashMode hs;int hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._s == EXIST) {hashi++;hashi %= _tables.size(); // 可能从尾部到头部了}// 现在hashi的位置是空的或者是删除了的_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}bool Erase(const K &key) {Node *ret = Find(key);if (ret) {--_n;ret->_s = DELETE;return true;} else {return false;}}private:vector<Node> _tables;size_t _n = 0;
};

---

4.4.2、链表法（Separate Chaining）

链表法（Separate Chaining）： 将具有相同哈希值的数据存储在同一个位置上，形成链表或其他数据结构。这样，当发生哈希冲突时，可以将冲突的数据连接在一起，不会丢失数据。

这里我们数组中存的元素必然是一个指针！如果偷懒的话，其实可以在vector中存一个list，即vector<list<pair<K,V>>> _tables。但是我们秉承着低耦合和高内聚的理念，我们还是自己写一个结构体用来存每个结点的数据。

存结点数据的结构体：

template<class K, class V>
struct HashNode {typedef HashNode<K, V> Node;Node *_next;pair<K, V> _kv;HashNode(const pair<K, V> &kv) : _kv(kv), _next(nullptr) {}};

**哈希表：**仿函数还是要写的，和开放定址法一样！

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {typedef HashNode<K, V> Node;
public:HashTable(size_t size = 10) {_tables.resize(size, nullptr);// 各结点初始化为空}Node *Find(const K &key) {Hash hs;// 先算出映射到哪里int hashi = hs(key) % _tables.size();Node *cur = _tables[hashi];while (cur) {if (cur->_kv.first == key) {return cur;}cur = cur->_next;}return nullptr; // 没找到}bool Erase(const K &key) {Hash hs;Node *ret = Find(key);if (ret) {int hashi = hs(key) % _tables.size();Node *cur = _tables[hashi];Node *prev = nullptr;while (cur) {if (cur->_kv.first == key) {if (prev == nullptr)_tables[hashi] = cur->_next; // 要删除的就是表中的结点，那么将它的下一个结点放到表中elseprev->_next = cur->_next; // 要删除的是表中的结点的后继中的某个delete cur; // 删除该结点并退出循环break;}prev = cur;cur = cur->_next;}--_n;return true;} else {return false;}}bool Insert(const pair<K, V> &kv) {Hash hs;if (Find(kv.first))return false;// 找到了// 先算出映射到哪里int hashi = hs(kv.first) % _tables.size();Node *cur = _tables[hashi];Node *newnode = new Node(kv);if (cur) {// 当前表中的结点不为空，则头插并链接newnode->_next = cur;_tables[hashi] = newnode;} else {// 当前表中的结点为空，则新结点直接放到这个表中_tables[hashi] = newnode;}++_n;return true;}private:vector<Node *> _tables;size_t _n = 0;
};

考虑一下哈希表的扩容？考虑极端情况下，也就是很多元素进行插入，但是我们这里初始的哈希表的长度为10，那么插入很多元素后会导致每个位置（我们这里叫桶）的结点下面的链表的长度很长，下次查找的时候需要遍历链表，很花时间！

官方的扩容条件是在装填因子为1的时候进行扩容！

那么这里是怎么进行扩容呢？

我们可以直接遍历旧表，将旧表的元素按新表的映射方式全部插入到新表中，并把旧表释放。

if (_n == _tables.size()) {// 扩容vector<Node *> newTables;newTables.resize(2 * _tables.size(), nullptr);for (int i = 0; i < _tables.size(); ++i) {Node *cur = _tables[i];while (cur) {Node *next = cur->_next; //记录下一个结点位置，防止找不到下一个结点// 映射到新表位置int hashi = hs(cur->_kv.first) % newTables.size();// 插入到新表位置Node *newcur = newTables[hashi];if (newcur) {// 当前表中的结点不为空，则头插并链接cur->_next = newcur;newTables[hashi] = cur;} else {// 当前表中的结点为空，则新结点直接放到这个表中newTables[hashi] = cur;cur->_next = nullptr;// 新插入的cur的_next不一定是空}cur = next;// 继续往下找}}_tables.swap(newTables);
}

因此链表法哈希表的整体代码为：

// 哈希表 --- 拉链法/哈希桶
template<class K, class V>
struct HashNode {typedef HashNode<K, V> Node;Node *_next;pair<K, V> _kv;HashNode(const pair<K, V> &kv) : _kv(kv), _next(nullptr) {}};template<class K>
struct HashFunc {size_t operator()(const K &key) {return (size_t) key;}
};template<>
struct HashFunc<string> {size_t operator()(const string &str) {size_t hash = 0;for (auto e: str) {hash += e;e *= 131;}return hash;}
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable {typedef HashNode<K, V> Node;
public:~HashTable() {for (int i = 0; i < _tables.size(); ++i) {_tables[i] = nullptr;}}HashTable(size_t size = 10) {_tables.resize(size, nullptr);// 各结点初始化为空}Node *Find(const K &key) {Hash hs;// 先算出映射到哪里int hashi = hs(key) % _tables.size();Node *cur = _tables[hashi];while (cur) {if (cur->_kv.first == key) {return cur;}cur = cur->_next;}return nullptr; // 没找到}bool Erase(const K &key) {Hash hs;Node *ret = Find(key);if (ret) {int hashi = hs(key) % _tables.size();Node *cur = _tables[hashi];Node *prev = nullptr;while (cur) {if (cur->_kv.first == key) {if (prev == nullptr)_tables[hashi] = cur->_next; // 要删除的就是表中的结点，那么将它的下一个结点放到表中elseprev->_next = cur->_next; // 要删除的是表中的结点的后继中的某个delete cur; // 删除该结点并退出循环break;}prev = cur;cur = cur->_next;}--_n;return true;} else {return false;}}bool Insert(const pair<K, V> &kv) {Hash hs;if (Find(kv.first))return false;// 找到了if (_n == _tables.size()) {// 扩容vector<Node *> newTables;newTables.resize(2 * _tables.size(), nullptr);for (int i = 0; i < _tables.size(); ++i) {Node *cur = _tables[i];while (cur) {Node *next = cur->_next; //记录下一个结点位置，防止找不到下一个结点// 映射到新表位置int hashi = hs(cur->_kv.first) % newTables.size();// 插入到新表位置Node *newcur = newTables[hashi];if (newcur) {// 当前表中的结点不为空，则头插并链接cur->_next = newcur;newTables[hashi] = cur;} else {// 当前表中的结点为空，则新结点直接放到这个表中newTables[hashi] = cur;cur->_next = nullptr;// 新插入的cur的_next不一定是空}cur = next;// 继续往下找}}_tables.swap(newTables);}// 先算出映射到哪里int hashi = hs(kv.first) % _tables.size();Node *cur = _tables[hashi];Node *newnode = new Node(kv);if (cur) {// 当前表中的结点不为空，则头插并链接newnode->_next = cur;_tables[hashi] = newnode;} else {// 当前表中的结点为空，则新结点直接放到这个表中_tables[hashi] = newnode;}++_n;return true;}private:vector<Node *> _tables;size_t _n = 0;
};

我们开放定址法和链表法用的扩容都是两倍扩容，但是官方用的是使用素数扩容，也就是每次扩容后哈希表的长度都是素数，据说这样会让元素更加分散。但其实并没有哈哈哈，Java底层就是2倍扩容。那么怎么做到差不多2倍扩容，每次扩容后哈希表长度都是素数呢？

size_t GetNextPrime(size_t prime) {const int PRIMECOUNT = 28;static const size_t primeList[PRIMECOUNT] ={53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,1572869ul, 3145739ul, 6291469ul, 12582917ul,25165843ul,50331653ul, 100663319ul, 201326611ul, 402653189ul,805306457ul,1610612741ul, 3221225473ul, 4294967291ul};size_t i = 0;for (; i < PRIMECOUNT; ++i) {if (primeList[i] > prime)return primeList[i];}return primeList[i];
}

---

5、unordered_set的模拟实现

以下我们自己模拟实现的时候，unordered_set的模拟实现我们使用MyUnordered_Set类用于区分，unordered_map的模拟实现我们使用MyUnordered_Map类用于区分。

5.1、改造哈希表（链表法）

结点的结构体需要修改一下，之前我们存的是pair<K,V>，但MyUnordered_Set是存K的，因此我们模版参数设置为一个参数T，MyUnordered_Set调用就是K，MyUnordered_Map调用就是pair<K,V>。

template<class T>
struct HashNode {typedef HashNode<T> Node;Node *_next;T _data;HashNode(const T &data) : _data(data), _next(nullptr) {}};

哈希表需要增加一个模版参数：取Key的仿函数，因为MyUnordered_Set插入的是K，但是MyUnordered_Map插入的是pair<K,V>，我们需要从pair<K,V>中取出K。因此插入也要改成bool Insert(const T &data){}

这个仿函数分别放在MyUnordered_Set和MyUnordered_Map的类中，用来传给哈希表。

MyUnordered_Set类中：

struct MapKeyOfT {K operator()(const pair<K, V> &kv) {return kv.first;}
};

MyUnordered_Map类中：

struct MapKeyOfT {K operator()(const pair<K, V> &kv) {return kv.first;}};

因此当前改造后的哈希表为：

template<class T>
struct HashNode {typedef HashNode<T> Node;Node *_next;T _data;HashNode(const T &data) : _data(data), _next(nullptr) {}};template<class K>
struct HashFunc {size_t operator()(const K &key) {return (size_t) key;}
};template<>
struct HashFunc<string> {size_t operator()(const string &str) {size_t hash = 0;for (auto e: str) {hash += e;e *= 131;}return hash;}
};template<class K, class T, class KeyOfT, class Hash>
class HashTable {typedef HashNode<T> Node;
public:~HashTable() {for (int i = 0; i < _tables.size(); ++i) {_tables[i] = nullptr;}}HashTable(size_t size = 10) {_tables.resize(size, nullptr);// 各结点初始化为空}Node* Find(const K &key) {Hash hs;KeyOfT kot;// 先算出映射到哪里int hashi = hs(key) % _tables.size();Node *cur = _tables[hashi];while (cur) {if (kot(cur->_data) == key) {return cur;}cur = cur->_next;}return nullptr; // 没找到}bool Erase(const K &key) {Hash hs;KeyOfT kot;iterator ret = Find(key);if (ret != end()) {int hashi = hs(key) % _tables.size();Node *cur = _tables[hashi];Node *prev = nullptr;while (cur) {if (kot(cur->_data) == key) {if (prev == nullptr)_tables[hashi] = cur->_next; // 要删除的就是表中的结点，那么将它的下一个结点放到表中elseprev->_next = cur->_next; // 要删除的是表中的结点的后继中的某个delete cur; // 删除该结点并退出循环break;}prev = cur;cur = cur->_next;}--_n;return true;} else {return false;}}bool Insert(const T &data) {Hash hs;KeyOfT kot;if (Find(kot(data)))return false;// 找到了if (_n == _tables.size()) {// 扩容vector<Node *> newTables;newTables.resize(2 * _tables.size(), nullptr);for (int i = 0; i < _tables.size(); ++i) {Node *cur = _tables[i];while (cur) {Node *next = cur->_next; //记录下一个结点位置，防止找不到下一个结点// 映射到新表位置int hashi = hs(kot(cur->_data)) % newTables.size();// 插入到新表位置Node *newcur = newTables[hashi];if (newcur) {// 当前表中的结点不为空，则头插并链接cur->_next = newcur;newTables[hashi] = cur;} else {// 当前表中的结点为空，则新结点直接放到这个表中newTables[hashi] = cur;cur->_next = nullptr;// 新插入的cur的_next不一定是空}cur = next;// 继续往下找}}_tables.swap(newTables);}// 先算出映射到哪里int hashi = hs(kot(data)) % _tables.size();Node *cur = _tables[hashi];Node *newnode = new Node(data);if (cur) {// 当前表中的结点不为空，则头插并链接newnode->_next = cur;_tables[hashi] = newnode;} else {// 当前表中的结点为空，则新结点直接放到这个表中_tables[hashi] = newnode;}++_n;return true;}private:vector<Node *> _tables;size_t _n = 0;
};

还需要增加迭代器，用来遍历哈希表。

// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator {typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HTIterator<K, T, KeyOfT, Hash> Self;Node *_node;HT *_ht;__HTIterator(Node *node, HT *ht) : _node(node), _ht(ht) {}T &operator*() {return _node->_data;}T *operator->() {return &_node->_data;}Self &operator++() {if (_node->_next) {// 当前结点还有后继结点_node = _node->_next;} else {// 当前桶走完了KeyOfT kot;Hash hs;// 先算出当前在哪个哈希桶int hashi = hs(kot(_node->_data)) % _ht->_tables.size();++hashi;// 走到下一个桶while (hashi < _ht->_tables.size()) {if (_ht->_tables[hashi]) {//  这个桶有结点_node = _ht->_tables[hashi];break;} else++hashi;// 这个桶没有有结点}if (hashi == _ht->_tables.size()) {// 走到最后了，没找到下一个位置_node = nullptr;}}return *this;}bool operator!=(const Self &s) {return s._node != _node;}
};

改造后的哈希表（终极版）：这里的插入的返回值由bool变为了pair<iterator,bool>，和官方保持一致。

template<class T>
struct HashNode {typedef HashNode<T> Node;Node *_next;T _data;HashNode(const T &data) : _data(data), _next(nullptr) {}};template<class K>
struct HashFunc {size_t operator()(const K &key) {return (size_t) key;}
};template<>
struct HashFunc<string> {size_t operator()(const string &str) {size_t hash = 0;for (auto e: str) {hash += e;e *= 131;}return hash;}
};// 前置声明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash>
struct __HTIterator {typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HTIterator<K, T, KeyOfT, Hash> Self;Node *_node;HT *_ht;__HTIterator(Node *node, HT *ht) : _node(node), _ht(ht) {}T &operator*() {return _node->_data;}T *operator->() {return &_node->_data;}Self &operator++() {if (_node->_next) {// 当前结点还有后继结点_node = _node->_next;} else {// 当前桶走完了KeyOfT kot;Hash hs;// 先算出当前在哪个哈希桶int hashi = hs(kot(_node->_data)) % _ht->_tables.size();++hashi;// 走到下一个桶while (hashi < _ht->_tables.size()) {if (_ht->_tables[hashi]) {//  这个桶有结点_node = _ht->_tables[hashi];break;} else++hashi;// 这个桶没有有结点}if (hashi == _ht->_tables.size()) {// 走到最后了，没找到下一个位置_node = nullptr;}}return *this;}bool operator!=(const Self &s) {return s._node != _node;}
};template<class K, class T, class KeyOfT, class Hash>
class HashTable {friend __HTIterator<K, T, KeyOfT, Hash>;// 为了能访问_tablestypedef HashNode<T> Node;
public:typedef __HTIterator<K, T, KeyOfT, Hash> iterator;iterator begin() {for (int i = 0; i < _tables.size(); ++i) {if (_tables[i])return iterator(_tables[i], this);// 从左找到第一个哈希桶的第一个结点}return end();}iterator end() {return iterator(nullptr, this);}~HashTable() {for (int i = 0; i < _tables.size(); ++i) {_tables[i] = nullptr;}}HashTable(size_t size = 10) {_tables.resize(size, nullptr);// 各结点初始化为空}iterator Find(const K &key) {Hash hs;KeyOfT kot;// 先算出映射到哪里int hashi = hs(key) % _tables.size();Node *cur = _tables[hashi];while (cur) {if (kot(cur->_data) == key) {return iterator(cur, this);}cur = cur->_next;}return iterator(nullptr, this); // 没找到}bool Erase(const K &key) {Hash hs;KeyOfT kot;iterator ret = Find(key);if (ret != end()) {int hashi = hs(key) % _tables.size();Node *cur = _tables[hashi];Node *prev = nullptr;while (cur) {if (kot(cur->_data) == key) {if (prev == nullptr)_tables[hashi] = cur->_next; // 要删除的就是表中的结点，那么将它的下一个结点放到表中elseprev->_next = cur->_next; // 要删除的是表中的结点的后继中的某个delete cur; // 删除该结点并退出循环break;}prev = cur;cur = cur->_next;}--_n;return true;} else {return false;}}pair<iterator, bool> Insert(const T &data) {Hash hs;KeyOfT kot;iterator it = Find(kot(data));if (it != end())return make_pair(it, false);// 找到了if (_n == _tables.size()) {// 扩容vector<Node *> newTables;newTables.resize(2 * _tables.size(), nullptr);for (int i = 0; i < _tables.size(); ++i) {Node *cur = _tables[i];while (cur) {Node *next = cur->_next; //记录下一个结点位置，防止找不到下一个结点// 映射到新表位置int hashi = hs(kot(cur->_data)) % newTables.size();// 插入到新表位置Node *newcur = newTables[hashi];if (newcur) {// 当前表中的结点不为空，则头插并链接cur->_next = newcur;newTables[hashi] = cur;} else {// 当前表中的结点为空，则新结点直接放到这个表中newTables[hashi] = cur;cur->_next = nullptr;// 新插入的cur的_next不一定是空}cur = next;// 继续往下找}}_tables.swap(newTables);}// 先算出映射到哪里int hashi = hs(kot(data)) % _tables.size();Node *cur = _tables[hashi];Node *newnode = new Node(data);if (cur) {// 当前表中的结点不为空，则头插并链接newnode->_next = cur;_tables[hashi] = newnode;} else {// 当前表中的结点为空，则新结点直接放到这个表中_tables[hashi] = newnode;}++_n;return make_pair(iterator(_tables[hashi], this), true);}private:vector<Node *> _tables;size_t _n = 0;
};

---

5.2、MyUnordered_Set类的构成

其实就是套了一层哈希表，多了一个SetKeyOfT用来传给哈希表的模版参数。

#include "HashTable_Bucket.h"template<class K, class Hash = HashFunc<K>>
class MyUnordered_Set {struct SetKeyOfT {K operator()(const K &key) {return key;}};public:typedef typename HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;iterator begin() {return _hs.begin();}iterator end() {return _hs.end();}pair<iterator,bool> insert(const K &key) {return _hs.Insert(key);}bool erase(const K &key) {return _hs.Erase(key);}iterator find(const K &key) {return _hs.Find(key);}private:HashTable<K, const K, SetKeyOfT, Hash> _hs;
};

---

OKOK，C++ STL容器之unordered_set类就到这里。如果你对Linux和C++也感兴趣的话，可以看看我的主页哦。下面是我的github主页，里面记录了我的学习代码和leetcode的一些题的题解，有兴趣的可以看看。

Xpccccc的github主页