目录

哈希表改造

哈希表结构 

仿函数实现 

哈希表迭代器 

结构

operator*和operator-> 

operator!=和==

operator++ 

构造函数 

拷贝构造 

析构函数 

拷贝构造 

哈希表完整代码 

unordered_set封装源码

unordered_map封装源码 

哈希表改造

我们知道unordered_map是K型结构，unordered_map是K，V型结构，那么如何通过一个哈希表实现对它们的封装呢？

下面我们对哈希表进行改造。（本篇采用开散列结构实现哈希表） 

T表示节点所存储的数据类型。 

哈希表结构 

templatestruct HashNode{T _data;HashNode* _next;HashNode(const T& data):_data(data),_next(nullptr){}};

 由于unordered_map是KV结构，我们我们需要增加一个模板参数来取出key值，也就是KeyofT,

并且哈希表需要将key值转换成可以取模的整数，所以再设置一个HashFunc参数，通过它们我们可以实现仿函数来达到我们的目的。

template>class HashTable{typedef HashNode Node;private:vector _table;//存储节点指针size_t _n=0;//有效数据个数};

仿函数实现 

struct MapKeyofT{const K& operator()(const pair& kv){return kv.first;}};
struct SetKeyofT{const K& operator()(const K& key){return key;}};

string类型通常也用作key，所以我们对string类型进行特化。 

template
struct Hash
{size_t operator()(const K& key){return key;}
};
template<>
struct Hash
{size_t operator()(const string& s){size_t ret = 0;for (auto e : s){ret *= 31;ret += e;}return ret;}
};

unordered_set结构：

template>class unordered_set{private:HashTable _ht;};

unordered_map结构： 

template>class unordered_map{struct MapKeyofT{const K& operator()(const pair& kv){return kv.first;}};private:HashTable, MapKeyofT, hash> _ht;};

哈希表迭代器 

首先明确unordered_map和unordered_set迭代器是单向的，所以我们内部哈希表的迭代器支持++操作即可。

我们采用的是开散列结构，如何实现迭代器++呢？

思路是先查找到一个非空哈希桶，++就是遍历该桶，那么如果该桶遍历完了呢？我们就要去下一个非空桶去，因此我们迭代器内部不仅要存储节点的地址，还要存储哈希表的地址。

结构

templatestruct HashTableIterator{typedef HashNode Node;typedef HashTableIterator self;//存储节点指针和一个哈希表的地址Node* _node;HashTable* _pht;HashTableIterator( Node* node, HashTable* pht):_node(node),_pht(pht)};

operator*和operator-> 

Ref operator*(){return _node->_data;}Ptr operator->(){return &(operator*());}

operator!=和==

 迭代器内部存储节点地址，比较是否相等可以直接使用节点地址去比较。

bool operator!=(const self& it)const{return _node != it._node;}bool operator==(const self& it)const{return _node == it._node;}

operator++ 

 如果下一个节点不为空，直接遍历到下一个节点。

如果为空，则要去寻找一个新的非空桶。

self& operator++(){if (_node->_next){_node = _node->_next;}else{KeyofT kot;HashFunc hf;Node* cur = _node;size_t index = hf(kot(cur->_data)) % _pht->_table.size();index++;while (index < _pht->_table.size()){if (_pht->_table[index]){break;}else{index++;}}if (index == _pht->_table.size()){_node = nullptr;}else{_node = _pht->_table[index];}}return *this;}

构造函数 

由于哈希表内部采用vector，所以我们不需要显示写构造函数。 

//指定编译器去默认生成构造函数HashTable() = default;

拷贝构造 

HashTable(const HashTable& ht){_table.resize(ht._table.size());for (size_t i = 0; i < ht._table.size(); ++i){Node* cur = ht._table[i];while (cur){Node* newnode = new Node(cur->_data);newnode->_next = _table[i];_table[i] = newnode;cur = cur->_next;}}}

析构函数 

遍历每一个哈希桶，并将其中节点释放。 

HashTable(const HashTable& ht){_table.resize(ht._table.size());for (size_t i = 0; i < ht._table.size(); ++i){Node* cur = ht._table[i];while (cur){Node* newnode = new Node(cur->_data);newnode->_next = _table[i];_table[i] = newnode;cur = cur->_next;}}}

拷贝构造 

self& operator=(self ht){_table.swap(ht._table);swap(_n, ht._n);return *this;}

哈希表完整代码 

//开散列，开放定址法，哈希桶
namespace LinkHash
{templatestruct HashNode{T _data;HashNode* _next;HashNode(const T& data):_data(data),_next(nullptr){}};templateclass HashTable;templatestruct HashTableIterator{typedef HashNode Node;typedef HashTableIterator self;//存储节点指针和一个哈希表的地址Node* _node;HashTable* _pht;HashTableIterator( Node* node, HashTable* pht):_node(node),_pht(pht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(operator*());}bool operator!=(const self& it)const{return _node != it._node;}bool operator==(const self& it)const{return _node == it._node;}self& operator++(){if (_node->_next){_node = _node->_next;}else{KeyofT kot;HashFunc hf;Node* cur = _node;size_t index = hf(kot(cur->_data)) % _pht->_table.size();index++;while (index < _pht->_table.size()){if (_pht->_table[index]){break;}else{index++;}}if (index == _pht->_table.size()){_node = nullptr;}else{_node = _pht->_table[index];}}return *this;}};template>class HashTable{typedef HashNode Node;friend struct HashTableIterator;typedef HashTable self;public:typedef HashTableIterator iterator;typedef HashTableIterator const_iterator;iterator begin(){for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){return iterator(_table[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}const_iterator begin()const{for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){return const_iterator(_table[i], this);}}return end();}const_iterator end()const{return const_iterator(nullptr, this);}//指定编译器去默认生成构造函数HashTable() = default;HashTable(const HashTable& ht){_table.resize(ht._table.size());for (size_t i = 0; i < ht._table.size(); ++i){Node* cur = ht._table[i];while (cur){Node* newnode = new Node(cur->_data);newnode->_next = _table[i];_table[i] = newnode;cur = cur->_next;}}}~HashTable(){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;}}self& operator=(self ht){_table.swap(ht._table);swap(_n, ht._n);return *this;}size_t GetNextPrime(size_t num){static const unsigned long __stl_prime_list[28] ={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 < 28; ++i){if (__stl_prime_list[i] > num){return __stl_prime_list[i];}}return __stl_prime_list[27];}bool erase(const K& key){if (_table.empty()){return false;}KeyofT kot;HashFunc hf;size_t index = hf(key) % _table.size();Node* cur = _table[index];Node* prev = nullptr;while (cur){if (kot(cur->_data) == key){if (prev == nullptr){_table[index] = cur->_next;}else{Node* next = cur->_next;prev->_next = next;}--_n;delete cur;return true;}else{prev = cur;cur = cur->_next;}}return false;}iterator Find(const K& key){if (_table.empty()){return iterator(nullptr,this);}KeyofT kot;HashFunc hf;size_t index = hf(key) % _table.size();Node* cur = _table[index];while (cur){if (kot(cur->_data) == key){return iterator(cur,this);}cur = cur->_next;}return iterator(nullptr, this);}pair insert(const T& data){KeyofT kot;auto ret = Find(kot(data));if (ret._node){return make_pair(ret,false);}HashFunc hf;if (_n == _table.size()){//扩容//size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;size_t newsize = GetNextPrime(_n);vector newTable;newTable.resize(newsize);for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){Node* cur = _table[i];while (cur){Node* next = cur->_next;size_t index = hf(kot(cur->_data)) % newsize;cur->_next = newTable[index];newTable[index] = cur;cur = next;}_table[i] = nullptr;}}_table.swap(newTable);}size_t index = hf(kot(data)) % _table.size();Node* newnode = new Node(data);newnode->_next = _table[index];_table[index] = newnode;++_n;return make_pair(iterator(newnode, this), true);}size_t size()const{return _n;}private:vector _table;//存储节点指针size_t _n=0;//有效数据个数};
}

unordered_set封装源码

namespace HashArea
{template>class unordered_set{struct SetKeyofT{const K& operator()(const K& key){return key;}};public:typedef typename LinkHash::HashTable::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}iterator Find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.erase(key);}pair insert(const K& key){return  _ht.insert(key);}private:LinkHash::HashTable _ht;};}

unordered_map封装源码 

namespace HashArea
{template>class unordered_map{struct MapKeyofT{const K& operator()(const pair& kv){return kv.first;}};public:typedef typename LinkHash::HashTable, MapKeyofT, hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool erase(const K& key){return _ht.erase(key);}pair insert(const pair& kv){return _ht.insert(kv);}iterator Find(const K& key){return _ht.Find(key);}size_t size()const{return _ht.size();}V& operator[](const K& key){auto ret = _ht.insert(make_pair(key, V()));return ret.first->second;}private:LinkHash::HashTable, MapKeyofT, hash> _ht;};
}