【哈希表封装实现】—— 我与C++的不解之缘（二十九）
前言
我们知道unordered_set和unordered_map的底层是哈希表，那现在我们就是使用我们自己实现的HashTable来封装实现出简单的unordered_set和unordered_map。
一、了解源码
在SGL-STL30版本之前源代码中是没有unordered_set和unordered_map的
unordered_set和unordered_map是C++11之后才更新的；SGL-STL30是C++11之前的版本
但是想SGL-STL30中实现了哈希表，但容器的名字叫做hash_map和hash_set（它是作为非标准的容器出现的）
源代码在hash_map/hash_set/stl_hash_map/stl_hash_map/stl_hash_set/stl_hashtable.h中
这里截取其中的一部分来看一下：
// stl_hash_set
template
class hash_set
{
private:
typedef hashtable ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::const_iterator iterator;
typedef typename ht::const_iterator const_iterator;
hasher hash_funct() const { return rep.hash_funct(); }
key_equal key_eq() const { return rep.key_eq(); }
};
// stl_hash_map
template
class hash_map
{
private:
typedef hashtable ht;
ht rep;
public:
typedef typename ht::key_type key_type;
typedef T data_type;
typedef T mapped_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::iterator iterator;
typedef typename ht::const_iterator const_iterator;
};
// stl_hashtable.h
template
class hashtable {
public:
typedef Key key_type;
typedef Value value_type;
typedef HashFcn hasher;
typedef EqualKey key_equal;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node node;
vector buckets;
size_type num_elements;
public:
typedef __hashtable_iterator iterator;
pair insert_unique(const value_type& obj);
const_iterator find(const key_type& key) const;
};
template
struct __hashtable_node
{
__hashtable_node* next;
Value val;
};
简单了解一下源码：（这里和map/set大致是一样的）
这里hashtable实现的是结构，第一个参数V表示存储的数据类型，第二个参数K表示关键值key。
结构上依然是unordered_set和unordered_map使用同一个哈希表实现Key和Key/Value结构；unordered_set传、unordered_map传。
这里呢它第一个参数是Value，感觉有点怪怪的；我们在实现的时候依然按照来实现。
二、封装实现unordered_set和unordered_map
1. 复用哈希表框架，实现insert
- 根据我们上篇博客实现的哈希表，我们要复用这个框架，写出来unordered_set和unordered_map的大致框架并支持insert操作。
- 这里我们就按照红黑树封装实现set和map的逻辑，Key参数就用K，Value参数就用V来实现；对于哈希表存储的数据类型，就用T来表示。
- 这里我们将数据类型用T来表示，就导致了我们在HashTable中不知道T是K还是pair，所以我们要像实现set和map那样，用一个模版参数KeyOfT来让我们在HashTable中能通过T取到K。
- 那这个KeyOfT就只能从unordered_set和unordered_map中传（因为在unordered_set和unordered_map中才知道数据类型是K还是pair）
这里再重述一下为什么要用KeyOfT：因为我们不知道T到底是K还是pair
如果是K那可以直接进行转换成整型然后取模操作。
但如果是pair，pair是不支持转换成整型的，所以我们要实现KeyOfT通过T取出K，然后对K进行转化整型然后取模操作。
逻辑理清楚了，现在来代码（这里有了KeyOfT，那每次使用Key转整型并取模操作之前都要套上一层取Key操作）。
先来看我们的HashTable.h
template struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template struct HashFunc { size_t operator()(const string& str) { size_t ret = 1; int i = 1; for (auto& ch : str) { ret += ch * i; i++; } return ret; } }; template struct HashNode { HashNode(const T& data) :_data(data) , _next(nullptr) {} T _data; HashNode* _next; }; template class HashTable { typedef HashNode Node; public: HashTable() { _table.resize(__stl_next_prime(0)); } bool insert(const T& data) { KeyOfT kof; if (find(kof(data)) != nullptr) return false; Hash hs; //扩容 if ((double)_n / (double)_table.size() >= 1) { size_t newsize = __stl_next_prime(_table.size() + 1); vector newtable; newtable.resize(newsize); for (int i = 0; i _next; size_t hash0 = hs(kof(cur->_data)) % newsize; //size_t hash0 = hs(cur->_kv.first) % newsize; //size_t hash0 = cur->_kv.first % newsize; cur->_next = newtable[hash0]; newtable[hash0] = cur; cur = next; } } _table.swap(newtable); } //插入 size_t hash0 = hs(kof(data)) % _table.size(); //size_t hash0 = hs(kv.first) % _table.size(); //size_t hash0 = kv.first % _table.size(); //头插到当前位置 Node* newnode = new Node(data); newnode->_next = _table[hash0]; _table[hash0] = newnode; _n++; return true; } Node* find(const K& key) { Hash hs; KeyOfT kof; size_t hashi = hs(key) % _table.size(); //size_t hashi = key % _table.size(); Node* cur = _table[hashi]; while (cur) { if (kof(cur->_data) == key) return cur; cur = cur->_next; } return nullptr; } bool erase(const K& key) { KeyOfT kof; for (int i = 0; i _data)) //if (key == cur->_kv.first) { if (prve == nullptr) { _table[i] = cur->_next; } else { prve->_next = cur->_next; } delete cur; --_n; return true; } prve = cur; cur = cur->_next; } } } ~HashTable() { for (int i = 0; i _next; delete cur; cur = next; } _table[i] = nullptr; } } private: vector _table; size_t _n = 0; };再来看unordered_set.h
namespace HL { template class unordered_set { struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: bool insert(const K& key) { return _hash.insert(key); } private: HashTable _hash; }; void test_set() { unordered_set ust; for (int i = 0; i int x = rand(); ust.insert(x); } } } template struct MapKeyOfT { const K& operator()(const pair return kv.first; } }; public: bool insert(const pair return _hash.insert(kv); } private: HashTable unordered_map int x = rand(); ump.insert({ x,i }); } } } typedef HashNode return _node == it._node; } bool operator!=(const Self& it) { return _node != it._node; } Ref operator*() { return _node-_data; } Ptr operator->() { return &_node->_data; } Self& operator++() { if (_node->_next != nullptr) { _node = _node->_next; } else { //当前桶走完了，找到下一个桶 KeyOfT kof; Hash hs; size_t hashi = hs(kof(_node->_data)) % _ht->_table.size(); hashi++; while (hashi _table.size()) { if (_ht->_table[hashi]) { _node = _ht->_table[hashi]; break; } hashi++; } if (hashi == _ht->_table.size()) _node = nullptr; } return *this; } HashIterator(Node* node, const HT* ht) :_node(node) ,_ht(ht) {} private: Node* _node; const HT* _ht; };当然不要忘了在HashTable中声明友元
这里就只展示出了HashTable中新增的部分。
template class HashTable { //友元 template friend class HashIterator; public: typedef HashIterator Iterator; typedef HashIterator ConstIterator; //迭代器部分 Iterator begin() { //找到第一个迭代器的位置 for (int i = 0; iunordered_set和unordered_map迭代器：
对于unordered_set和unordered_map迭代器对HashTable的迭代器进行复用即可。
unordered_set迭代器
typedef typename HashTable::Iterator iterator; typedef typename HashTable::ConstIterator const_iterator; iterator begin() { return _hash.begin(); } iterator end() { return _hash.end(); } const_iterator begin() const { return _hash.begin(); } const_iterator end() const { return _hash.end(); }unordered_map迭代器
typedef typename HashTable::Iterator iterator; typedef typename HashTable::ConstIterator const_iterator; iterator begin() { return _hash.begin(); } iterator end() { return _hash.end(); } const_iterator begin() const { return _hash.begin(); } const_iterator end() const { return _hash.end(); }这里博主还写出了测试迭代器的代码（只有普通迭代器的）
void test_set() { unordered_set ust; for (int i = 0; i int x = rand(); ust.insert(x); } auto it = ust.begin(); while (it != ust.end()) { cout unordered_map int x = rand(); ump.insert({ x,i }); } auto it = ump.begin(); while (it != ump.end()) { cout KeyOfT kof; //if (find(kof(data)) != nullptr) // return false; Iterator it = find(kof(data)); if (it != end()) return { it,false }; Hash hs; //扩容 if ((double)_n / (double)_table.size() = 1) { size_t newsize = __stl_next_prime(_table.size() + 1); vector Node* cur = _table[i]; while (cur) { Node* next = cur-_next; size_t hash0 = hs(kof(cur-_data)) % newsize; //size_t hash0 = hs(cur-_kv.first) % newsize; //size_t hash0 = cur-_kv.first % newsize; cur-_next = newtable[hash0]; newtable[hash0] = cur; cur = next; } } _table.swap(newtable); } //插入 size_t hash0 = hs(kof(data)) % _table.size(); //size_t hash0 = hs(kv.first) % _table.size(); //size_t hash0 = kv.first % _table.size(); //头插到当前位置 Node* newnode = new Node(data); newnode-_next = _table[hash0]; _table[hash0] = newnode; _n++; //return true; return { {newnode,this},true }; } //Node* find(const K& key) Iterator find(const K& key) { Hash hs; KeyOfT kof; size_t hashi = hs(key) % _table.size(); //size_t hashi = key % _table.size(); Node* cur = _table[hashi]; while (cur) { if (kof(cur-_data) == key) return { cur,this }; //return cur; cur = cur->_next; } //return nullptr; return { nullptr,this }; }unordered_set的insert：
//bool insert(const K& key) pair insert(const K& key) { return _hash.insert(key); }unordered_map的insert和operator[]：
//bool insert(const pair& kv) pair insert(const pair& kv) { return _hash.insert(kv); } V& operator[](const K& key) { pair p = insert({ key,V() }); return p.first->second; }这里提供了测试unordered_map的方法：
void test_map() { HL::unordered_map ump; ump.insert({ "sort", "排序" }); ump.insert({ "left", "左边" }); ump.insert({ "right", "右边" }); ump["left"] = "左边，剩余"; ump["insert"] = "插入"; ump["string"]; HL::unordered_map::iterator it = ump.begin(); while (it != ump.end()) { it->second += 'x'; cout first HL::unordered_map "sort", "排序" }); ump.insert({ "left", "左边" }); ump.insert({ "right", "右边" }); ump["left"] = "左边，剩余"; ump["insert"] = "插入"; ump["string"]; HL::unordered_map it-second += 'x'; cout
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们。
