模拟实现
哈希表的改造
增加迭代器
template<class K, class T, class Hash, class KeyofT> struct _Hashiterator { typedef Hashnode<T> node; typedef _Hashiterator<K, T, Hash, KeyofT> Self; typedef Hashbucket<K, T, Hash, KeyofT> HB; node* _node; //指向哈希桶的指针，用来获取 HB* _hb; _Hashiterator(node* node, HB* hb) :_node(node) , _hb(hb) { } T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } bool operator!=(const Self& s)const { return _node != s._node; } bool operator==(const Self& s)const { return _node == s._node; } Self& operator++() { if (_node->_next) { _node = _node->_next; } else { //当前的桶已经遍历完，需要到下一个桶进行遍历 KeyofT kot; Hash hash; size_t hashi = hash(kot(_node->_data)) % _hb->_table.size(); ++hashi; while (hashi < _hb->_table.size()) { if (_hb->_table[hashi]) { _node = _hb->_table[hashi]; break; } else { ++hashi; } } if (hashi == _hb->_table.size()) { _node = nullptr; } } return *this; } };
哈希表中每个元素的设计
template<class T> struct Hashnode { T _data; Hashnode<T>* _next; Hashnode(const T& data) :_data(data) , _next(nullptr) { } };
这里同样考虑到数据T，可能是键值key，也可能是键值对pair<K,V>;所以许还需要一个能够通过键值key获取实值value的仿函数KeyofT，此仿函数的实现在模拟实现的类对象中实现
//前置声明 template<class K,class T,class Hash,class KeyofT> class Hashbucket; template<class K, class T, class Hash, class KeyofT> struct _Hashiterator { typedef Hashnode<T> node; typedef _Hashiterator<K, T, Hash, KeyofT> Self; typedef Hashbucket<K, T, Hash, KeyofT> HB; node* _node; //指向哈希桶的指针，用来获取 HB* _hb; _Hashiterator(node* node, HB* hb) :_node(node) , _hb(hb) { } T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } bool operator!=(const Self& s)const { return _node != s._node; } bool operator==(const Self& s)const { return _node == s._node; } Self& operator++() { if (_node->_next) { _node = _node->_next; } else { //当前的桶已经遍历完，需要到下一个桶进行遍历 KeyofT kot; Hash hash; size_t hashi = hash(kot(_node->_data)) % _hb->_table.size(); ++hashi; while (hashi < _hb->_table.size()) { if (_hb->_table[hashi]) { _node = _hb->_table[hashi]; break; } else { ++hashi; } } if (hashi == _hb->_table.size()) { _node = nullptr; } } return *this; } }; template<class K, class T, class Hash,class KeyofT> class Hashbucket { typedef Hashnode<T> node; template<class K,class T,class Hash,class KeyofT> friend struct _Hashiterator; public: typedef _Hashiterator<K, T, Hash, KeyofT> iterator; Hashbucket() :_n(0) { _table.resize(10); } ~Hashbucket() { for (size_t i = 0; i < _table.size(); i++) { node* cur = _table[i]; while (cur) { node* next = cur->_next; delete cur; cur = next; } _table[i] = nullptr; } } iterator begin() { for (size_t i = 0; i < _table.size(); i++) { //寻找第一个不为空的位置 if (_table[i]) { return iterator(_table[i], this); } } return iterator(nullptr, this); } iterator end() { return iterator(nullptr, this); } iterator find(const K& key) { KeyofT kot; size_t hashi = Hash()(key) % _table.size(); node* cur = _table[hashi]; while (cur) { if (kot(cur->_data) == key) { return iterator(cur, this); } else { cur = cur->_next; } } return end(); } pair<iterator,bool> insert(const T&data) { KeyofT kot; iterator it = find(kot(data)); if (it != end()) { return make_pair(it, false); } if (_table.size() == _n) { vector<node*>newtable; newtable.resize(_table.size() * 2); for (size_t i = 0; i < _table.size(); i++) { node* cur = _table[i]; while (cur) { node* next = cur->_next; size_t hashi = Hash()(kot(data)) % newtable.size(); //头插到新表中 cur->_next = newtable[hashi]; newtable[hashi] = cur; cur = next; } _table[i] = nullptr; } _table.swap(newtable); } size_t hashi = Hash()(kot(data)) % _table.size(); //头插 node* newnode = new node(data); newnode->_next = _table[hashi]; _table[hashi] = newnode; ++_n; return make_pair(iterator(newnode, this), true); } bool erase(const K& key) { size_t hashi = Hash()(key) % _table.size(); node* prev = nullptr; node* cur = _table[hashi]; while (cur) { if (cur->_kv.first = key) { //准备删除 //没有哈希冲突 if (cur == _table[hashi]) { _table[hashi] = cur->_next; } else { prev->_next = cur->_next; } delete cur; --_n; return true; } else { prev = cur; cur = cur->_next; } } return false; } private: vector<node*> _table; size_t _n = 0;//表中存储元素的有效个数 };
模拟实现unordered_map
仿函数MapKeyofT的实现
struct MapKeyofT { const K& operator()(const pair<const K, V>& kv) { return kv.first; } };
完整代码
template<class K,class V,class Hash=HashFunc<K>> class unordered_map { struct MapKeyofT { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; public: typedef typename yjm::Hashbucket<K, pair<const K, V>, Hash, MapKeyofT>::iterator iterator; iterator begin() { return _hb.begin(); } iterator end() { return _hb.end(); } pair<iterator, bool> insert(const pair<K, V>& data) { return _hb.insert(data); } V& operator[](const K& key) { pair<iterator, bool> ret = _hb.insert(make_pair(key, V())); return ret.first->second; } private: yjm::Hashbucket<K, pair<const K, V>, Hash, MapKeyofT> _hb; };
测试
void test() { string arr[] = { "篮球","羽毛球","排球","乒乓球","羽毛球" ,"羽毛球" ,"排球" }; unordered_map<string, int> countmap; for (auto& e : arr) { countmap[e]++; } }
运行结果
哈希应用
位图
概念
所谓位图就是用每一位来存放某种状态，适用海量数据，数据无重复的场景，通常是用来判断某个数据存在或者不存在的信息，如果二进制比特位（byte) 1代表存在；0代表不存在
举个栗子
int arr[] = { 3,6,7,1,4,14 };
每个字节共有8个比特位，可以保存8个数据的状态（存在或不存在）
通过位图的概念解决一个问题
给40亿个不重复的无符号整数，没有排过序；给定一个无符号整数，如何快速判断这个数是否在这40亿个数中？？？
如果没有位图的概念，可能会想着将这些数放到红黑树或者哈希中，但是40亿个整数所需的内存大概是16G，所以这种想法不切实际；接下来就通过位图的概念进行解题
通过位图概念，首先要确定数据的位置，这里采用直接定址法：数据的值是几，就将第几个位标记成1
数据映射在第几个字节上：x/8；
在这个字节的第几个比特位上：x%8；
找到位置之后需要做的便是，如何设置状态，在之前的学习中位运算可以解决这个问题；接下来就是通过灵活运用位运算对数据的状态进行设置
其他位不变，第j位标记成1
如果第 j位之前就是1，结果也就是1；如果不是1，按位或之后也会变成1
void set(size_t x) { size_t i = x / 8; size_t j = x % 8; _bit[i] |= (1 << j); }
其他位不变，第j位标记成0
如果第 j位之前就是0，结果也就是0；如果不是0，按位与之后也会变成0
void reset(size_t x) { size_t i = x / 8; size_t j = x % 8; _bit[i] &= (~(1 << j)); }
测试该位的数据是否存在
bool test(size_t x) { size_t i = x >> 3; size_t j = x % 8; return _bit[i] & (1 << j); }
实现
此题目只是判断数据是否存在，一个比特位便可以进行判断： 0，不存在； 1，存在；由于是在40亿个数字中进行判断，所以将40亿个数据放入容量为 size_t int i=-1比特位的容器中进行判断
代码实现
template<size_t N> class bitset { public: bitset() { _bit.resize((N >> 3) + 1, 0); } void set(size_t x) { size_t i = x / 8; size_t j = x % 8; _bit[i] |= (1 << j); } void reset(size_t x) { size_t i = x / 8; size_t j = x % 8; _bit[i] &= (~(1 << j)); } bool test(size_t x) { size_t i = x >> 3; size_t j = x % 8; return _bit[i] & (1 << j); } private: vector<char> _bit; };
测试
void test() { bitset<-1> bs; bs.set(3); bs.set(6); bs.set(7); bs.set(1); bs.set(4); bs.set(14); cout << bs.test(3) << endl; cout << bs.test(6) << endl; cout << bs.test(7) << endl; cout << bs.test(1) << endl; cout << bs.test(4) << endl; cout << bs.test(14) << endl; bs.reset(3); bs.reset(6); bs.reset(7); bs.reset(1); bs.reset(4); bs.reset(14); cout << bs.test(3) << endl; cout << bs.test(6) << endl; cout << bs.test(7) << endl; cout << bs.test(1) << endl; cout << bs.test(4) << endl; cout << bs.test(14) << endl; }
运行结果
位图的应用：
快速查找某个数据是否存在一个集合中
排序+去重
求两个集合的交集，并集
操作系统中对磁盘进行标记
布隆过滤器
提出
当通过哈希函数对字符串映射到位图上时，可能会出现两个字符串同时映射到同一个比特位上，便会出现误判的情况，误判是不可避免的，那么又该如何降低误判呢？？？
概念
使用多个哈希函数，将一个数据映射到位图结构中，特点是高效地插入和查询，还可以节省大量的内存空间
对于一个字符串，通过不止一个哈希函数进行映射，便可以降低误判
对于判断为不存在时一定是正确的；判断存在时，不一定正确，可能存在着冲突
