从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