哈希表的封装

目录

引入

哈希表封装

修改哈希表参数

修改哈希表成员

修改%时使用的变量

修改读取时获得的变量

迭代器的实现

迭代器的定义

迭代器++

迭代器*解引用

迭代器->成员访问

迭代器重载==和!=

封装迭代器

HashTable迭代器封装

非const版本

const版本

unordered_set迭代器封装

unordered_map迭代器封装

修改insert的返回值

unordered_map的[ ]解引用重载  

代码汇总

---

引入

unordered_set和unordered_map是由哈希表封装而来的。前面介绍了解决哈希冲突的两种方式：开散列和闭散列。此篇博客将会采用开散列进行封装，模拟实现unordered_set和unordered_map。

哈希表(开散列)的实现-CSDN博客文章浏览阅读523次，点赞24次，收藏26次。通过除留余数法确定数据位置，再根据开散列的方法解决哈希冲突。本篇博客对哈希表开散列的实现进行细致剖析，帮助读者理解哈希表性能的优缺点。https://blog.csdn.net/2401_87944878/article/details/146923387哈希表(闭散列)的实现-CSDN博客文章浏览阅读925次，点赞43次，收藏44次。通过除留余数法确定数据位置，再根据闭散列的方法解决哈希冲突。本篇博客对哈希表闭散列的实现进行细致剖析，帮助读者理解哈希表性能的优缺点。https://blog.csdn.net/2401_87944878/article/details/146922720

此处贴出哈希表开散列的代码，如有疑问可以参考。我们将借助一下代码对哈希表进行封装。

template<class K,class V>
struct HashNode
{//默认构造HashNode(const pair<K,V>& kv=pair()):_kv(kv),_next(nullptr){ }pair<K, V> _kv;HashNode* _next;
};template<class K,class V>
class HashTable
{typedef HashNode<K, V> Node;
public://默认构造HashTable(){_table.resize(10);  //初始情况下数组有10个空间_n = 0;}//扩容void More(){if ((double)_n / _table.size() >= 1){//进行扩容HashTable newtable;size_t newsize = 2 * _table.size();newtable._table.resize(newsize);  //扩容两倍扩size_t hashi = 0;while (hashi < _table.size()){if (_table[hashi]){//将数据进行头插Node* pcur = _table[hashi];while (pcur){Node* next = pcur->_next;pcur->_next = newtable._table[hashi];newtable._table[hashi] = pcur;pcur = next;}}hashi++;}_table.swap(newtable._table);}}//插入bool insert(const pair<K, V>& kv){//扩容More();size_t hashi = kv.first % _table.size();Node* newnode = new Node(kv);//将数据头插到对应映射的位置newnode->_next = _table[hashi];_table[hashi] = newnode;_n++;return true;}//查找bool Find(const K& key){size_t hashi = key % _table.size();Node* pcur = _table[hashi];while (pcur){if (pcur->_kv.first == key){return true;}pcur = pcur->_next;}return false;}//删除bool Erase(const K& key){size_t hashi = key % _table.size();Node* pcur = _table[hashi];Node* parent = nullptr;while (pcur){if (pcur->_kv.first == key){if (parent == nullptr){delete pcur;pcur = nullptr;_table[hashi] = nullptr;}else{parent->_next = pcur->_next;delete pcur;}return true;}pcur = pcur->_next;}return false;}private:vector<Node*> _table;size_t _n;   //存储有效数据
};

---

哈希表封装

哈希表的封装与红黑树的封装异曲同工之妙，没看过红黑树封装的可以看看，此处贴链接：

set和map封装-CSDN博客文章浏览阅读1k次，点赞51次，收藏29次。本文对set和map的底层实现进行深度剖析，分析如何通过相同的底层逻辑红黑树来封装出不同的容器，对set和map的迭代器进行底层实现，对库中封装的逻辑进行详细分析，帮助读者理解两种容器的结构以及实现逻辑。https://blog.csdn.net/2401_87944878/article/details/146424819

修改哈希表参数

哈希表的模板参数就现在看来需要两个：1）确定查找数据的类型；2）用于存储数据的类型。

注意：关于哈希表的模板参数并不止这两种，在后面还需要添加。

对于unordered_set来说：查找数据的类型和存储数据的类型是一样的，都是T。

而对于unordered_map来说：查找数据的类型是key，而存储数据的类型是pair。

template<class T>
class set
{typedef HashTable<T, T> Hash;
public:private:Hash _hash;
};

template<class K, class V>
class map
{typedef HashTable<K, pair<K, V>> Hash;
public:private:Hash _hash;
};

---

修改哈希表成员

此时哈希表的成员不再是pair了，而要使用date来实现泛型编程。

template<class T>
struct HashNode
{//默认构造HashNode(const T& date = T()):_date(date), _next(nullptr){}T _date;HashNode* _next;
};

将哈希表中的pair全部用date取代。

---

修改%时使用的变量

当哈希表中存储的时string类型时，就不能取模。所以需要通过仿函数来实现对string类型的取模。

通过添加模板参数来决定%取模的方式。

对于string类型来说：采用将字符串的每一个字符相加作为其返回的整形；通过在每次相加前乘以131可以保证对于不同顺序的字符串可以返回不同的整形进而降低了哈希冲突 

template<class K>
struct HashFunc   //用于普通整形返回
{//对于普通整形进行返回size_t operator()(const K& key){return (size_t)key;   // 转化为size_t 类型后，还能保证负数也可以找到对应下标位置}
};struct HashString   //用于string返回整形
{size_t operator()(const string& st){//此处采用将字符串的每一个字符相加作为其返回的整形size_t hashi = 0;for (auto e : st){hashi *= 131;   //通过在相加前乘以131可以保证对于不同顺序的字符串可以返回不同的整形//进而降低了哈希冲突hashi += e;}return hashi;}
};

此处也可以使用模板特化来代替使用多个类型。

template<class K>
struct HashFunc   //用于普通整形返回
{//对于普通整形进行返回size_t operator()(const K& key){return (size_t)key;   // 转化为size_t 类型后，还能保证负数也可以找到对应下标位置}
};template<>
struct HashFunc<string>   
{size_t operator()(const string& st){size_t hashi = 0;for (auto e : st){hashi *= 131; hashi += e;}return hashi;}
};

template<class K, class T,class Func=HashFunc<K>>
class HashTable
{//....
}

将每次对K进行%取模前，使用仿函数获取整形，以下是部分处理方式。

Func func;
size_t hashi = func(date) % _table.size();

---

修改读取时获得的变量

在查找时要进行数据的比较，对于set来说只有T一种类型，可以直接进行比较。而对于map来说，其存储的是pair，比较时要用pair的第一个参数first进行比较。所以需要增加一个内部类来实现取出比较元素。

在set和map中分别实现内部类，来获取其比较是用的数据；对于set来说返回的就是T，而对于map来说返回的则是pair中存储的first。在RBTree添加一个模板参数用来保存内部类即可。

template<class T>
class set
{struct SetofK{const T& operator()(const T& key){return key;}};typedef HashTable<T, T,SetofK> Hash;private:Hash _hash;
};

template<class K, class V>
class map
{struct MapofK{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef HashTable<K, pair<K, V>,MapofK> Hash;
public:private:Hash _hash;
};

template<class K, class T,class TofK, class Func=HashFunc<K>>
class HashTable
{//....
}

在进行比较前使用仿函数获取进行处理的数据，如以下代码。

Func func;
TofK getkey;
size_t hashi = func(getkey(date)) % _table.size();

---

迭代器的实现

哈希表中存储的是节点，所以其迭代器底层是存储每一个节点的结构体。

其结构体成员有节点指针，还需要哈希表。因为在对迭代器进行++时，可能会出现从一个链表跳转到另一个链表。

迭代器的定义

template<class K, class T,class Ref,class Ptr ,class TofK>
struct HashIterator
{typedef HashTable<K, T, TofK> HashTable;typedef HashNode<T> Node;typedef HashIterator<K, T, Ref, Ptr, TofK> Self;//构造//构造HashIterator(Node* node,HashTable* hash):_node(node),_hash(hash){}Node* _node;HashTable* _hash;
};

迭代器++

迭代器++分为两种情况：1）当前节点有下一个节点，返回下一个节点即可；2）当前节点没有下一个节点，从当前节点对应的哈希表位置向后找，找到不为空的位置。

在迭代器中需要访问哈希表的vector，所以需要将迭代器置为HashTable的友元。 

//迭代器++
Self operator++()
{HashFunc<K> func;if (_node->_next){_node = _node->_next;return *this;}else{TofK getkey;size_t hashi = func(getkey(_node->_date));hashi = hashi % _hash->_table.size();++hashi;while (hashi < _hash->_table.size()){if (_hash->_table[hashi]){_node = _hash->_table[hashi];return *this;}else{++hashi;}}//结尾了_node = nullptr;return *this;}
}

迭代器*解引用

Ref operator*()
{return _node->_date;
}

迭代器->成员访问

Ptr operator->()
{return &(_node->_date);
}

迭代器重载==和!=

//等于
bool operator==(Self& it)
{return _node == it._node;
}//不等于
bool operator!=(Self& it)
{return _node != it._node;
}

封装迭代器

HashTable迭代器封装

非const版本

template<class K, class T,class TofK, class Func=HashFunc<K>>
class HashTable
{typedef HashNode<T> Node;
public:typedef HashIterator<K, T,  T&, T*, TofK> iterator;typedef HashIterator<K, T,  const T&, const T*, TofK> const_iterator;//beginiterator begin(){//找到哈希表中第一个不为空的位置size_t hashi = 0;while (hashi<_table.size()){if (_table[hashi]){return iterator(_table[hashi], this);}++hashi;}return iterator(nullptr, this);}//enditerator end(){return iterator(nullptr, this);}
}

const版本

//begin
const_iterator begin()const
{//找到哈希表中第一个不为空的位置size_t hashi = 0;while (hashi < _table.size()){if (_table[hashi]){return iterator(_table[hashi], this);}++hashi;}return iterator(nullptr, this);
}//end
const_iterator end()const
{return iterator(nullptr, this);
}

unordered_set迭代器封装

对于插入到哈希表中的数据来说，用于比较的数据是不能被修改的，所以对set来说其存储的key值不能进行修改，所以unordered_set的普通迭代器的实质还是const迭代器。

_hash.begin()返回的是普通迭代器，而set的普通迭代器实际上还是const迭代器，普通迭代器和const迭代器虽然是来自同一个模板，但是其是完全不同的两个类，所以此处需要用返回的普通迭代器中的数据来构造一个const迭代器。

template<class T>
class set
{typedef HashTable<T, T,SetofK> Hash;typedef typename Hash::iterator Iterator;   //普通迭代器
public:typedef typename Hash::const_iterator iterator;   //const迭代器typedef typename Hash::const_iterator const_iterator;		//const迭代器iterator begin(){Iterator ret = _hash.begin();return iterator(ret._node,&_hash);}iterator end(){Iterator ret = _hash.end();return iterator(ret._node,&_hash);}private:Hash _hash;
};

unordered_map迭代器封装

unordered_map的K也不能进行修改，但是T可以进行修改，所以map普通迭代器不变，但是还需要实现对Key值的不能修改，此处的实现就比较简单了，可以直接在pair的模板参数中使用const Key即可。

template<class K, class V>
class map
{typedef HashTable<K, pair<const K, V>,MapofK> Hash;
public:typedef typename Hash::iterator iterator;typedef typename Hash::const_iterator const_iterator;iterator begin(){return _hash.begin();}iterator end(){return _hash.end();}private:Hash _hash;
};

修改insert的返回值

可以看到在库中，insert的返回值是pair，所以此处对返回值进行修改。将原本的bool，改为pair类型即可。

将return true改为return make_pair(iterator(newnode,this), true);即可。

对于unordered_set的insert返回值还是需要先保留再转化。

pair<iterator, bool> insert(const T& val)
{pair<Iterator, bool> it = _hash.insert(val);return make_pair(iterator(it.first._node, &_hash), it.second);
}

unordered_map的[ ]解引用重载  

unordered_map的解引用重载的实现，底层还是insert，对没有的数据进行插入，对已经存在的数据返回T。

V& operator[](const K& key)
{pair<iterator, bool> it = _hash.insert(make_pair(key, V()));return it.first._node->_date.second;
}

---

代码汇总

<HashTable>

template<class T>
struct HashNode
{//默认构造HashNode(const T& date = T()):_date(date), _next(nullptr){}T _date;HashNode* _next;
};template<class K>
struct HashFunc   //用于普通整形返回
{//对于普通整形进行返回size_t operator()(const K& key){return (size_t)key;   // 转化为size_t 类型后，还能保证负数也可以找到对应下标位置}
};template<>
struct HashFunc<string>   
{size_t operator()(const string& st){size_t hashi = 0;for (auto e : st){hashi *= 131; hashi += e;}return hashi;}
};struct HashString   //用于string返回整形
{size_t operator()(const string& st){//此处采用将字符串的每一个字符相加作为其返回的整形size_t hashi = 0;for (auto e : st){hashi *= 131;   //通过在相加前乘以131可以保证对于不同顺序的字符串可以返回不同的整形//进而降低了哈希冲突hashi += e;}return hashi;}
};template<class K, class T, class Ref, class Ptr, class TofK>
struct HashIterator;template<class K, class T,class TofK, class Func=HashFunc<K>>
class HashTable
{typedef HashNode<T> Node;
public:typedef HashIterator<K, T,  T&, T*, TofK> iterator;typedef HashIterator<K, T,  const T&, const T*, TofK> const_iterator;//beginiterator begin(){//找到哈希表中第一个不为空的位置size_t hashi = 0;while (hashi<_table.size()){if (_table[hashi]){return iterator(_table[hashi], this);}++hashi;}return iterator(nullptr, this);}//enditerator end(){return iterator(nullptr, this);}//beginconst_iterator begin()const{//找到哈希表中第一个不为空的位置size_t hashi = 0;while (hashi < _table.size()){if (_table[hashi]){return iterator(_table[hashi], this);}++hashi;}return iterator(nullptr, this);}//endconst_iterator end()const{return iterator(nullptr, this);}//默认构造HashTable(){_table.resize(10);  //初始情况下数组有10个空间_n = 0;}//扩容void More(){if ((double)_n / _table.size() >= 1){//进行扩容HashTable newtable;size_t newsize = 2 * _table.size();newtable._table.resize(newsize);  //扩容两倍扩size_t hashi = 0;while (hashi < _table.size()){if (_table[hashi]){//将数据进行头插Node* pcur = _table[hashi];while (pcur){Node* next = pcur->_next;pcur->_next = newtable._table[hashi];newtable._table[hashi] = pcur;pcur = next;}}hashi++;}_table.swap(newtable._table);}}//插入pair<iterator ,bool> insert(const T& date){//扩容More();Func func;TofK getkey;size_t hashi = func(getkey(date)) % _table.size();Node* newnode = new Node(date);//将数据头插到对应映射的位置newnode->_next = _table[hashi];_table[hashi] = newnode;_n++;return make_pair(iterator(newnode,this), true);}//查找bool Find(const K& key){TofK getkey;Func func;size_t hashi = func(getkey(key)) % _table.size();Node* pcur = _table[hashi];while (pcur){if (pcur-> _date == key){return true;}pcur = pcur->_next;}return false;}//删除bool Erase(const K& key){Func func;TofK getkey;size_t hashi = func(key) % _table.size();Node* pcur = _table[hashi];Node* parent = nullptr;while (pcur){if (getkey(pcur->date) == key){if (parent == nullptr){delete pcur;pcur = nullptr;_table[hashi] = nullptr;}else{parent->_next = pcur->_next;delete pcur;}return true;}pcur = pcur->_next;}return false;}template<class K, class T, class Ref, class Ptr, class TofK>friend struct HashIterator;
private:vector<Node*> _table;size_t _n;   //存储有效数据
};template<class K, class T,class Ref,class Ptr ,class TofK>
struct HashIterator
{typedef HashTable<K, T, TofK> HashTable;typedef HashNode<T> Node;typedef HashIterator<K, T, Ref, Ptr, TofK> Self;//构造HashIterator(Node* node,HashTable* hash):_node(node),_hash(hash){}//迭代器++Self operator++(){HashFunc<K> func;  if (_node->_next){_node = _node->_next;return *this;}else{TofK getkey;size_t hashi = func(getkey(_node->_date));hashi = hashi % _hash->_table.size();++hashi;while (hashi < _hash->_table.size()){if (_hash->_table[hashi]){_node = _hash->_table[hashi];return *this;}else{++hashi;}}//结尾了_node = nullptr;return *this;}}Ref operator*(){return _node->_date;}Ptr operator->(){return &(_node->_date);}//等于bool operator==(Self& it){return _node == it._node;}//不等于bool operator!=(Self& it){return _node != it._node;}Node* _node;HashTable* _hash;
};

<unordered_set>

template<class T>
class set
{struct SetofK{const T& operator()(const T& key){return key;}};typedef HashTable<T, T,SetofK> Hash;typedef typename Hash::iterator Iterator;   //普通迭代器
public:typedef typename Hash::const_iterator iterator;   //const迭代器typedef typename Hash::const_iterator const_iterator;		//const迭代器iterator begin(){Iterator ret = _hash.begin();return iterator(ret._node,&_hash);}iterator end(){Iterator ret = _hash.end();return iterator(ret._node,&_hash);}pair<iterator, bool> insert(const T& val){pair<Iterator, bool> it = _hash.insert(val);return make_pair(iterator(it.first._node, &_hash), it.second);}private:Hash _hash;
};

<unordered_map>

template<class K, class V>
class map
{struct MapofK{const K& operator()(const pair<K, V>& kv){return kv.first;}};typedef HashTable<K, pair<const K, V>,MapofK> Hash;
public:typedef typename Hash::iterator iterator;typedef typename Hash::const_iterator const_iterator;iterator begin(){return _hash.begin();}iterator end(){return _hash.end();}pair<iterator,bool> insert(const pair<K, V> kv){pair<iterator,bool> it = _hash.insert(kv);return make_pair(iterator(it.first._node,&_hash), it.second);}V& operator[](const K& key){pair<iterator, bool> it = _hash.insert(make_pair(key, V()));return it.first._node->_date.second;}private:Hash _hash;
};