个人主页:仍有未知等待探索-CSDN博客
专题分栏:C++
本文着重于模拟实现哈希表,并非是哈希表的使用。
实现的哈希表的底层用的是线性探测法,并非是哈希桶。
目录
一、标准库中的哈希表
1、unordered_map
2、unordered_set
二、模拟实现哈希表
1、结构
2、注解hashtable的模板参数:
3、重难点
1、二元“!=” 没有找到接收类型的右操作数的运算符编辑
2、迭代器的本质、const和非const的区别
3、类A在类B的上面,想要在类A中使用以类B为类型的变量,怎么办?
4、类A在类B的上面,想要在类A中使用类B的私有成员,怎么办?
三、代码
一、标准库中的哈希表
这两个是两种不同映射关系的哈希表。
unordered_map:是 Key - Value 的映射关系 (也就是 关键字和键值 之间的映射)
unordered_set:是 Value 的映射关系(也就是只有 键值 的映射)
这两种不同的映射关系从各自的模板参数就能看出来。
1、unordered_map
unordered_map又分为两种,一种是unordered_map,另一种是unordered_multimap。
这两种有什么区别呢?
以unordered_map为例:
这里面的模板参数 Key - T 就是这个容器存储的键值关系。
2、unordered_set
同样:unordered_set又分为两种,一种是unordered_set,另一种是unordered_multiset。
这两个的区别和unordered_map中两个的区别一样。
二、模拟实现哈希表
1、结构
在模拟实现哈希表前,我们要知道整个实现的结构,要有完整性的认识。
这个就是哈希表的大致底层结构。
2、注解hashtable的模板参数:
- Key:是上层结构(也就是unordered_set、unordered_map)的关键字。
- T:是存的关键字和键值的映射。
(也就是unordered_set:pair<Key, Key>;unordered_map:pair<Key, Vaule>)
- Ptr是T*。
- Ref是T&。
- KeyofT是一个仿函数,用来取T的Key。因为在这一层也不知道上一层是unordered_set、unordered_map,所以还需要传一个仿函数来进行取值。
- hashfunc是一个仿函数,用来计算hash映射值。
对于一个整数,怎么存储到哈希表里?需要对其进行hash计算,将这个整数取模于表的大小得到。
对于一个字符串,怎么存储到哈希表里?需要对其进行hash计算,将这个字符串转换成整数,然后将这个整数取模于表的大小得到下标。
如果得到的下标冲突了,就用哈希线性探测法解决冲突。
3、重难点
写完不算难,难的是找bug。
1、二元“!=” 没有找到接收类型的右操作数的运算符![](https://i-blog.csdnimg.cn/direct/4db52edee8514394a6977d4d8c874a59.png)
类型不匹配,你可以去你出错的位置看看该类型的模板参数的类型匹不匹配。
2、迭代器的本质、const和非const的区别
迭代器就是模拟的指针的行为。
const迭代器和非const迭代器的区别就是限制其*和->运算符的返回值。
3、类A在类B的上面,想要在类A中使用以类B为类型的变量,怎么办?
在类A的前面加上类B的前置声明即可。
4、类A在类B的上面,想要在类A中使用类B的私有成员,怎么办?
在类B中加上类A的友元。
三、代码
hash.h
#pragma once#include <iostream>
#include <vector>
#include <string>
using namespace std;
enum State
{Empty,Exist,Delete
};
// hash_func ---> 用来对任意类型进行编码
template<class T>
struct hash_func
{size_t operator()(const T& _val){return (size_t)_val;}
};
// 对string类型进行特化
template<>
struct hash_func<string>
{size_t operator()(const string& val){size_t hash = 0;for (auto e : val){hash *= 131;hash += e;}return hash;}
};// 闭散列 --- 线性探测
// 这里的 T 是 K or pair<K, V>
template <class T>
struct HashNode
{HashNode() {}HashNode(const HashNode&) = default;HashNode(const T& data, const State& state):_data(data),_state(state){}T _data;State _state = Empty;};template <class K, class V, class Ptr, class Ref, class KeyofT, class HashFunc>
class HashTable;template<class K, class T, class Ptr, class Ref, class KeyofT>
struct HashTable_iterator
{typedef HashNode<T> HashNode;typedef HashTable_iterator<K, T, Ptr, Ref, KeyofT> iterator;typedef HashTable<K, T, Ptr, Ref, KeyofT, hash_func<K>> hashtable;HashNode* _node;hashtable* _pht;KeyofT kot;hash_func<K> hs;HashTable_iterator(HashNode* node, hashtable* pht):_node(node), _pht(pht){}bool operator!=(const iterator s){return _node != s._node;}Ref operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}iterator& operator++(){int hashindex = 0;for (int i = 0; i < _pht->_tables.size(); i++){// 找到当前节点的位置,寻找下一个节点的位置if (_pht->_tables[i] == _node){hashindex = i;break;}}for (int i = hashindex + 1; i < _pht->_tables.size(); i++){if (_pht->_tables[i] && _pht->_tables[i]->_state == Exist){_node = _pht->_tables[i];return *this;}}_node = nullptr;return *this;}
};template <class K, class V, class Ptr, class Ref, class KeyofT, class HashFunc = hash_func<K>>
class HashTable
{typedef HashNode<V> hashnode;typedef HashTable<K, V, Ptr, Ref, KeyofT, hash_func<K>> hashtable;template<class K, class T, class Ptr, class Ref, class KeyofT>friend struct HashTable_iterator;typedef HashTable_iterator<K, V, Ptr, Ref, KeyofT> iterator;public:hash_func<K> hf;KeyofT kot;HashTable(size_t n = 10):_size(0){_tables.resize(n);}iterator begin(){for (int i = 0; i < _tables.size(); i++){hashnode* cur = _tables[i];if (cur && cur->_state == Exist){// this -> HashTable*return iterator(cur, this);}}return end();}iterator end(){return iterator(nullptr, this);}// V : V or pair<K, V>pair<iterator, bool> insert(const V& e){iterator it = find(kot(e));if (it != end()){return make_pair(it, false);}if (_size * 10 / _tables.size() >= 7){hashtable newt(_tables.size() * 2);for (int i = 0; i < _tables.size(); i ++ ){if (_tables[i]->_state == Exist){newt.insert(_tables[i]->_data);}}_tables.swap(newt._tables);}size_t hashindex = hf(kot(e)) % _tables.size();while (_tables[hashindex] && _tables[hashindex]->_state == Exist){hashindex++;hashindex %= _tables.size();}hashnode* newnode = new hashnode(e, Exist);swap(_tables[hashindex], newnode);delete newnode;_size++;return make_pair(iterator(_tables[hashindex], this), true);}iterator find(const K& key){size_t hashindex = hf(key)% _tables.size();while (_tables[hashindex] && _tables[hashindex]->_state != Empty){if (_tables[hashindex]->_state == Exist&& kot(_tables[hashindex]->_data) == key){return iterator(_tables[hashindex], this);}++hashindex;hashindex %= _tables.size();}return iterator(nullptr, this);}bool erase(const K& key){iterator t = find(key);if (t._node == nullptr) return false;else{t._node->_state = Delete;--_size;}return true;}
private:vector<hashnode*> _tables;size_t _size;
};
unordered_map.h
#pragma once#include "hash.h"template<class K, class V>
class unordered_map
{struct MapKeyofT{const K& operator()(const pair<const K, V>& key){return key.first;}};
public:typedef HashTable<K, pair<const K, V>, pair<const K, V>*, pair<const K, V>&, MapKeyofT, hash_func<K>> HashTable;typedef HashNode<pair<const K, V>> HashNode;typedef HashTable_iterator<K, pair<const K, V>, pair<const K, V>*, pair<const K, V>&, MapKeyofT> iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const pair<const K, V>& kv){return _ht.insert(kv);}iterator find(const K& key){return _ht.find(key);}bool erase(const K& key){return _ht.erase(key);}V& operator[](const K& key){pair<K, V> pkv = make_pair(key, V());pair<iterator, bool> ret = insert(pkv);return ret.first->second;}
private:HashTable _ht;
};//void map01()
//{
// unordered_map<int, int> s1;
// vector<int> v = { 1, 8, 34, 5, 3, 4, 8, 1111, 111, 11 };
//
// for (auto e : v)
// {
// s1.insert({e, e});
// }
//
// s1.erase(1111);
// s1.erase(8);
//}
//
//void map02()
//{
// unordered_map<string, int> s1;
// vector<string> v = { "1234", "233", "a", "b", "1234", "233", "a", "b" };
//
// for (auto e : v)
// {
// s1.insert({e, 1});
// }
//
// s1.erase("1234");
// s1.erase("8");
//}
unordered_set.h
#pragma once#include "hash.h"template<class K>
class unordered_set
{struct SetKeyofT{const K& operator()(const K& key){return key;}};
public:typedef HashTable<K, K, const K*, const K&, SetKeyofT, hash_func<K>> HashTable;typedef HashNode<K> HashNode;typedef HashTable_iterator<K, K, const K*, const K&, SetKeyofT> iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const K& val){return _ht.insert(val);}iterator find(const K& key){return _ht.find(key);}bool erase(const K& key){return _ht.erase(key);}
private:HashTable _ht;
};//void set01()
//{
// unordered_set<int> s1;
// vector<int> v = { 1, 8, 34, 5, 3, 4, 8, 1111, 11, 11};
//
// for (auto e : v)
// {
// s1.insert(e);
// }
//
// s1.erase(1111);
//}
//void set02()
//{
// unordered_set<string> s;
// vector<string> v = { "1234", "233", "a", "b" };
//
// for (auto e : v)
// {
// s.insert(e);
// }
//
// s.erase("1111");
// s.erase("1234");
//}
谢谢大家!