从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)（上）：https://developer.aliyun.com/article/1522330
884. 两句话中的不常见单词 - 力扣（LeetCode）
难度简单
句子 是一串由空格分隔的单词。每个 单词 仅由小写字母组成。
如果某个单词在其中一个句子中恰好出现一次，在另一个句子中却 没有出现 ，那么这个单词就是 不常见的 。
给你两个 句子 s1 和 s2 ，返回所有 不常用单词 的列表。返回列表中单词可以按 任意顺序 组织。
示例 1：
输入：s1 = "this apple is sweet", s2 = "this apple is sour"
输出：["sweet","sour"]
示例 2：
输入：s1 = "apple apple", s2 = "banana"
输出：["banana"]
提示：
1 <= s1.length, s2.length <= 200
s1和s2由小写英文字母和空格组成s1和s2都不含前导或尾随空格s1和s2中的所有单词间均由单个空格分隔
class Solution { public: vector<string> uncommonFromSentences(string s1, string s2) { } };
解析代码：（等价于：在两个句子中一共只出现一次的单词。）
大家可以百度stringstream类用法，这里讲一个小技巧：可以将字符串中每个单词按空格隔开。
class Solution { public: vector<string> uncommonFromSentences(string s1, string s2) { unordered_map<string, int> m; vector<string> retV; stringstream a, b; // 创建流对象 string s; a << s1; // 向流中传值 b << s2; while (a >> s) { m[s]++; //流向s中写入值，并且空格会自断开 //cout << s << "+"; } while (b >> s) { m[s]++; } for (const auto& m : m) { if (m.second == 1) { retV.push_back(m.first); //只需要看出现次数是1的单词 } } return retV; } };
如果解开注释：
2. 实现unordered_set和unordered_map
这里用我们上一篇写的开散列哈希桶的代码，闭散列不用就删掉，去掉命名空间复制一份过来：
#pragma once #include <iostream> #include <vector> using namespace std; template<class K, class V> struct HashNode { pair<K, V> _kv; HashNode* _next; // 不用存状态栏了，存下一个结点指针 HashNode(const pair<K, V>& kv) :_kv(kv) , _next(nullptr) {} }; template<class K> struct HashFunc // 可以把闭散列的HashFunc放在外面直接用，但是这就不放了 { size_t operator()(const K& key) { return (size_t)key; // 负数，浮点数，指针等可以直接转，string不行 } }; template<> struct HashFunc<string> // 上面的特化 { size_t operator()(const string& key) { size_t val = 0; for (const auto& ch : key) { val *= 131; val += ch; } return val; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: typedef HashNode<K, V> Node; ~HashTable() { for (size_t i = 0; i < _tables.size(); ++i) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } } Node* Find(const K& key) { if (_tables.size() == 0) { return nullptr; } Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) { return cur; } cur = cur->_next; } return nullptr; } inline size_t __stl_next_prime(size_t n) { static const size_t __stl_num_primes = 28; static const size_t __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; for (size_t i = 0; i < __stl_num_primes; ++i) { if (__stl_prime_list[i] > n) { return __stl_prime_list[i]; } } return -1; // 不会走到这，随便返回一个值 } bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) { return false; } Hash hs; if (_size == _tables.size()) // 负载因子到1就扩容 { //size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2; vector<Node*> newTables; //newTables.resize(newSize, nullptr); newTables.resize(__stl_next_prime(_tables.size()), nullptr); //取素数，前两注释改成这一条 for (size_t i = 0; i < _tables.size(); ++i) // 旧表中节点移动映射新表 { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hashi = hs(cur->_kv.first) % newTables.size(); cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } size_t hashi = hs(kv.first) % _tables.size(); // 哈希映射 Node* newnode = new Node(kv); // 头插 newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_size; return true; } bool Erase(const K& key) { if (_tables.size() == 0) // 防止除零错误 { return false; } Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) // 头插，先把指针数组存的指针指向cur的下一个 { _tables[hashi] = cur->_next; } else // 中间删 { prev->_next = cur->_next; } delete cur; // 统一在这delete return true; } prev = cur; // 往后走 cur = cur->_next; } return false; // 没找到 } size_t Size() // 存的数据个数 { return _size; } size_t TablesSize() // 表的长度 { return _tables.size(); } size_t BucketNum() // 桶的个数 { size_t num = 0; for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]) // 如果不是空就有桶 { ++num; } } return num; } size_t MaxBucketLenth() // 最长桶的长度 { size_t maxLen = 0; for (size_t i = 0; i < _tables.size(); ++i) { size_t len = 0; Node* cur = _tables[i]; while (cur) { ++len; cur = cur->_next; } if (len > maxLen) { maxLen = len; } } return maxLen; } protected: vector<Node*> _tables; // 指针数组 size_t _size; };
有了封装set和map的和学习了哈希的经验，直接写出框架：
UnorderedSet.h：
#pragma once #include "HashTable.h" namespace rtx { template<class K, class K> class unordered_map { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: protected: HashTable<K, k, Hash, MapKeyOfT> _ht; }; }
UnorderedMap.h：
#pragma once #include "HashTable.h" namespace rtx { template<class K, class V, class Hash = HashFunc<K>> class unordered_map { struct MapKeyOfT { const K& operator()(const pair<K, V>& kv) { return kv.first; } }; public: protected: HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht; }; }
用命名空间和STL库区分，第二个参数对于unordered_set是key，对于unordered_map是piar，
现在应该把ashNode的两个参数改为一个参数T，_pair 改为 _data
再把HashTable的第二个参数改为T，再加一个获取key的仿函数：
（这里不能在第三个仿函数给默认的了）
2.1 哈希桶的迭代器
迭代器是所有容器必须有的，先来看迭代器的++是如何实现的：
如上图所示，一个哈希表，其中有四个哈希桶，迭代器是it。
++it操作：
- 如果it不是某个桶的最后一个元素（桶里数据下一个不为空），则it指向下一个节点。
- 如果it是桶的最后一个元素（桶里数据下一个为空），则it指向下一个桶的头节点。
要想实现上面的操作，迭代器中不仅需要一个_node来记录当前节点，还需要一个哈希表的指针，以便找下一个桶，代码如下：（顺便写迭代器中的其他操作，如解引用，箭头，以及相等等运算符的重载就不再详细介绍了：）
template<class K, class T, class Hash, class KeyOfT> class HashTable; // 前置声明 template<class K, class T, class Hash, class KeyOfT> class __HashIterator { public: typedef HashNode<T> Node; typedef HashTable<K, T, Hash, KeyOfT> HT; typedef __HashIterator<K, T, Hash, KeyOfT> Self; Node* _node; // 数据结点 HT* _pht; // 哈希表指针 __HashIterator(Node* node, HT* pht) :_node(node) , _pht(pht) {} Self& operator++() { if (_node->_next) // 不是桶中的最后一个数据 { _node = _node->_next; } else // 是桶中的最后一个数据，找下一个桶 { Hash hs; KeyOfT kot; size_t i = hs(kot(_node->_data)) % _pht->_tables.size() + 1;//没+1是当前桶位置 for (; i < _pht->_tables.size(); ++i) { if (_pth->tables[i]) // 向后迭代找到了有桶的位置 { _node = _pth->tables[i]; // 把这个位置给_node break; } } if (_pht == _tables.size()) // 后面都没桶了 { _node = nullptr; } } return *this; // this调用该函数的对象（迭代器），指向下一个后解引用返回 } T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } bool operator!=(const Self& s) const { return s._node != _node; } bool operator==(const Self& s) const { return s._node == _node; } };
t不是处于某个桶的末尾，直接指向下一个节点。
当it是某个桶的末尾时，指向下一个桶。
首先需要确定当前桶的位置：
使用KeyOfT仿函数获取当前数据的key值(因为不知道是map还是set在调用)。再使用Hash仿函数将key值转换成可以模的整形(因为不知道key是整形还是字符串再或者其他自定义类型)。
然后开始寻找下一个桶：
从当前哈希表下标开始向后寻找，直到找到下一个桶，将桶的头节点地址赋值给_node。如果始终没有找到，说明没有桶了，也就是没有数据了，it指向end，这里使用空指针来代替end。 将++后的迭代器返回。
迭代器中有一个成员变量是哈希表的指针，如上图所示，所以在迭代器中typedef了HashTable成为 HT，方便我们使用。
根据我们前面实现迭代器的经验，迭代器其实是封装在Hashtable中的，也就是说，在HashTable中也会typedef迭代器：此时HashTable和HashIterator就构成了相互typedef的关系。哈希表和迭代器类的定义势必会有一个先后顺序，这里在定义的时候，在代码顺序上就是先定义迭代器，再定义的哈希表。此时迭代器在typedef的时候就找不到哈希表的定义，因为编译器只会向上寻找而不会向下寻找。所以必须在HashIterator类前面先声明一下HashTable类，这种操作被叫做前置声明。
前置声明一定要放在类外面，如果放在迭代器类里面，编译器只会在迭代器的命名空间中寻找哈希表的定义，这样是找不到的。
前置声明放在类外面的时候，编译器会在整个命名空间中寻找哈希表的定义，就可以找到。
在++迭代器的时候，会使用到哈希表指针，哈希表指针又会使用到HashTable中的_tables。（HashTable中的_tables是保护成员，在类外是不能访问的。）解决这个问题可以在HashTable中写一个公有的访问函数，也可以采用友元，这里用下友元。
类模板的友元声明需要写模板参数，在类名前面加friend关键字。（迭代器要访问HashTable的保护，所以迭代器要成为HashTable的友元）
从C语言到C++_31(unordered_set和unordered_map介绍+哈希桶封装)（下）：https://developer.aliyun.com/article/1522332
