namespace hash_bucket { template<class T> struct HashBucketNode { T _data; HashBucketNode<T>* _next; HashBucketNode(const T& data) :_data(data) ,_next(nullptr) {} }; // K 为 T 中key的类型 // T 可能是键值对，也可能是K // KeyOfT: 从T中提取key // Hash将key转化为整形，因为哈市函数使用除留余数法 template<class K, class T, class KeyOfT, class Hash> class HashBucket { typedef HashBucketNode<T> Node; public: HashBucket() { _tables.resize(10, nullptr); } // 哈希桶的销毁 ~HashBucket() { for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[cur]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } } } /********************************************************************/ unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. static const int __stl_num_primes = 28; static const unsigned long __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 }; const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } /********************************************************************/ // 插入值为data的元素，如果data存在则不插入 bool Insert(const T& data) { KeyOfT kot; Hash hash; if (_n == _tables.size()) { vector<Node*> newTables(__stl_next_prime(_tables.size() + 1), nullptr); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[cur]; while (cur) { Node* next = cur->_next; size_t hashi = hash(kot(cur->_data)) % newTables.size(); cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[hashi] = nullptr; } _tables.swap(newTables); } size_t hashi = hash(kot(data)) % _tables.size(); Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; } // 在哈希桶中查找值为key的元素，存在返回true否则返回false bool Find(const K& key) { KeyOfT kot; Hash hash; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { return true; } cur = cur->_next; } return false; } // 哈希桶中删除key的元素，删除成功返回true，否则返回false bool Erase(const K& key) { KeyOfT kot; Hash hash; size_t hashi = hash(key) % _tables.size(); Node* cur = _tables[hashi]; Node* prev = nullptr; while (cur) { if (kot(cur->_data) == key) { if (prev == nullptr) { _tables[hashi] = nullptr; } else { prev->_next = cur->_next; delete cur; --_n; return true; } } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _tables; // 指针数组 size_t _n = 0; // 表中存储数据个数 }; /***************************************************************************************************************************/ // 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身， template<class K, class V, class KeyOfValue, class HF> class HashBucket; // 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作 template <class K, class V, class KeyOfValue, class HF> struct HBIterator { typedef HashBucket<K, V, KeyOfValue, HF> HashBucket; typedef HashBucketNode<V>* PNode; typedef HBIterator<K, V, KeyOfValue, HF> Self; HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr) :_pNode(PNode) ,_pHt(pHt) {} Self& operator++() { // 当前迭代器所指节点后还有节点时直接取其下一个节点 if (_pNode->_pNext) _pNode = _pNode->_pNext; else { // 找下一个不空的桶，返回该桶中第一个节点 size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data)) + 1; for (; bucketNo < _pHt->BucketCount(); ++bucketNo) { if (_pNode = _pHt->_ht[bucketNo]) break; } } return *this; } Self operator++(int) { } V& operator*(); V* operator->(); bool operator==(const Self& it) const; bool operator!=(const Self& it) const; PNode _pNode; // 当前迭代器关联的节点 HashBucket* _pHt; // 哈希桶--主要是为了找下一个空桶时候方便 }; // unordered_map中存储的是pair<K, V>的键值对，K为key的类型，V为value的类型，HF哈希函数类型 // unordered_map在实现时，只需将hashbucket中的接口重新封装即可 template<class K, class V, class HF = DefHashF<K>> class unordered_map { typedef HashBucket<K, pair<K, V>, KeyOfValue, HF> HT; // 通过key获取value的操作 struct KeyOfValue { const K& operator()(const pair<K, V>& data) { return data.first; } }; public: typename typedef HT::Iterator iterator; public: unordered_map() : _ht() {} //////////////////////////////////////////////////// iterator begin() { return _ht.begin(); } iterator end() { return _ht.end(); } //////////////////////////////////////////////////////////// // capacity size_t size()const { return _ht.size(); } bool empty()const { return _ht.empty(); } /////////////////////////////////////////////////////////// // Acess V& operator[](const K& key) { pair<iterator, bool> ret = _ht.InsertUnique(pair<K, V>(key, V())); return ret.fisrt->second; } const V& operator[](const K& key)const; ////////////////////////////////////////////////////////// // lookup iterator find(const K& key) { return _ht.Find(key); } size_t count(const K& key) { return _ht.Count(key); } ///////////////////////////////////////////////// // modify pair<iterator, bool> insert(const pair<K, V>& valye) { return _ht.Insert(valye); } iterator erase(iterator position) { return _ht.Erase(position); } //////////////////////////////////////////////////////////// // bucket size_t bucket_count() { return _ht.BucketCount(); } size_t bucket_size(const K& key) { return _ht.BucketSize(key); } private: HT _ht; };如何编写Self operator++(int)