【C++】2.7 哈希表及其实现（附代码）

template<class K,class V> struct hashdata { std::pair<K, V> _kv; state _state=EMPTY; }; template<class K, class V> class hash { public: hash() :_tables(23) ,_n(0) { } private: std::vector<hashdata<K, V>> _tables; size_t _n; };

3. 插入

bool insert(const std::pair<K,V>& kv) { size_t hash0 = kv.first % _tables.size(); size_t hashi = hash0; size_t i = 1; int flag = 1; while (_tables[hashi]._state == EXIST) { hashi = (hash0 + i) % _tables.size(); ++i; } _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST; ++_n; return true; }

当位置存在时，就一直找，找到不为存在时就插入

(1) 二次探测：由于直接这么探测，要是数据堆积那么效率较低
因此，可以将+i改成+-i方，让数据更加分散
其它都一样，将hash0 + i改为hash+i*i即可

(2) 双重散列法
由于二次探测在冲突时+-的值时一样的，依旧不能解决堆积问题
因此，可以再用一个独立的函数去计算+-的值
要求：函数值<M且与M互质（否则就是在原地几个数中踏步）

4. 扩容

将原来的vector拷贝到新的更大的vector
但是由于size不一样，开放寻址的_tables.size()爷不一样，因此需要重新建立关系
并且，不是满了扩容，而是当负载超过一定数时就扩容

if (_n * 100 / _tables.size() >= 70) { hash<K, V> newhash; newhash._tables.resize(2 * _tables.size()); for (auto& e : _tables) { if (e._state == EXIST) { newhash.insert(e._kv); } } _tables.swap(newhash._tables); }

可以参考现代写法，建一个新的哈希表类，再复用插入逻辑，再交换两个vector

5. 质数处理

2 * _tables.size()由于新哈希表的大小为两倍以前的，因此一定不是质数
解决方案：弄一个质数数组，达到负载就取新的值

newhash._tables.resize(prim(_tables.size()+1));

写了个二分查找，找到最小的大于s的数

inline size_t prim(size_t s) { static const size_t prime_list[] = { 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 size_t n = sizeof(prime_list) / sizeof(prime_list[0]); size_t left = 0, right = n; while (left < right) { size_t mid = left + (right - left) / 2; if (prime_list[mid] < s) left = mid + 1; else right = mid; } if (left < n) return prime_list[left]; return prime_list[n - 1]; }

6. Find

hashdata<K, V>* Find(const K& key) { size_t hash0 = key % _tables.size(); size_t hashi = hash0; size_t i = 1; while (_tables[hashi]._state != EMPTY) { if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key) { return &_tables[hashi]; } hashi = (hash0 + i) % _tables.size(); ++i; } return nullptr; }

7. 转无符号整型

由于上面写的代码仅仅是针对于无符号整型的
但是其它的可以用仿函数的方式转

template<class K> struct hashfunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct hashfunc<std::string> { size_t operator()(const std::string& str) { size_t hash = 0; for (auto&e:str) { hash += e; hash *= 131; } return hash; } };

在内置类型，如double等可以直接强转
但是，string也可能出现在哈希表中，因此对模板进行特化，优先走特化函数
因此，哈希表要转2次，传值->无符号整型->哈希函数映射哈希值

BKDR哈希
String如何转无符号整型
如果将每一位简单相加，那么很容易冲突
因此，可以加一位再乘一个质数（选择131）以减少冲突

8. 自定义类和哈希函数

struct date { int _year; int _month; int _day; date(int year=1,int month=1,int day=1) :_year(year) ,_month(month) ,_day(day) { } bool operator == (const date & d) { return _year == d._year && _month == d._month && _day == d._day; } }; struct cmp { size_t operator()(const date& d) const { size_t has = 0; has += d._year; has *= 10000; has += d._month; has *= 100; has += d._day; return has; } };

因此，哈希表做key的要求：能转为整型，可以有不等于的比较

五、链地址法实现

由于开放寻址法无论怎么探测都无法解决过多数据堆积问题

因此，将哈希表数组中存放链表将冲突的值挂下来
这个放地址的东西就叫桶

1. 节点定义

struct hashnode { std::pair<K, V> _kv; hashnode* _next; hashnode(const std::pair<K,V>&kv) :_kv(kv) ,_next(nullptr) { } };

为什么单链表：单链表对于哈希表已经足够了，还可节省空间
为什么不用list或forward_list
因为在扩容时，用std的list会自动析构，但是我们其实可以回收利用原先的节点，节省开销

2. 插入加扩容

bool insert(const std::pair<K, V>& kv) { hash ha; if (_n * 100 / _tab.size() >= 70) { hashtab<K, V, hash> newhash; newhash._tab.resize(prim(_tab.size() + 1)); for (int i = 0; i < _tab.size(); i++) { node* cur = _tab[i]; while (cur) { node* next = cur->_next; size_t has = ha(cur->_kv.first) % newhash._tab.size(); cur->_next = _tab[has]; _tab[has] = cur; cur = next; } _tab[i] = nullptr; } _tab.swap(newhash._tab); } size_t has = ha(kv.first) % _tab.size(); node* newnode = new node(kv); newnode->_next = _tab[has]; _tab[has] = newnode; ++_n; return 1; }

由于链地址法没有那么害怕哈希冲突，因此可以忍受较高的负载因子
甚至可以满了再扩容
但是，由于需要回收利用原先的节点，因此就不能让扩容直接复用插入了，否则会浪费
插入节点选择头插

3. 查询和删除

Iterator Find(const K& key) { KofT kot; hash _hash; size_t hashi = _hash(key) % _tab.size(); node* cur = _tab[hashi]; while (cur) { if (kot(cur->_data) == key) { return Iterator(cur, this); } cur = cur->_next; } return End(); } bool Erase(const K& key) { KofT kot; size_t hashi = key % _tab.size(); node* prev = nullptr; node* cur = _tab[hashi]; while (cur) { if (kot(cur->_data) == key) { if (prev == nullptr) { // 头结点 _tab[hashi] = cur->_next; } else { // 中间节点 prev->_next = cur->_next; } delete cur; --_n; return true; } else { prev = cur; cur = cur->_next; } } return false; }

用哈希函数找到桶的地址，再头插到对应地点
查询返回迭代器和bool类型的pair值

六、哈希表其它接口

rehash
由于哈希表扩容的代价非常大，因此在开始前先预留好桶的大小
Reserve也是同理
但是reserve会预留冗余值
bucket_count和bucket_size
bucket_count:桶的数量
bucket_size：第n个桶有多少个元素
load_factor
当前负载因子大小
max_load_factor
修改最大负载因子

七、封装和模拟实现

1. 迭代器成员声明

template<class K,class T,class ref,class ptr,class KofT,class hash> struct uniterator { typedef hashtab<K, T, KofT, hash> utb; typedef uniterator<K, T, ref, ptr, KofT, hash> self; typedef unordered_node<T> node; node* _node; const utb* _utb; uniterator(node* __node, const utb* __utb) :_node(__node) ,_utb(__utb) { } };

(1) 模板的作用
由于需要普通迭代器和const迭代器
因此模板需要ref和ptr参数，并且由于需要算哈希函数，因此需要仿函数KofT取出class T的T中的key
此外，在遍历时需要计算出从哪里开始，需要哈希函数
需要桶的指针，因此需要K和T

(2) 通指针要用const
因为调用const迭代器时为了值不被修改，因此这么声明

ConstIterator Begin() const

Const表示this指针指向对象为const，因此构造函数传也需要为const，否则权限放大

2. 迭代器成员函数

ref operator*() { return _node->_data; } ptr operator->() { return &(_node->_data); } bool operator!=(const self& s) { return _node != s._node; }

3. 迭代器++

self& operator++() { if (_node->_next) { _node = _node->_next; } else { KofT kot; hash ha; size_t hashi = ha(kot(_node->_data)) % _utb->_tab.size(); ++hashi; while (hashi < _utb->_tab.size()) { _node = _utb->_tab[hashi]; if (_node) break; else ++hashi; } // 所有桶都走完了，end()给的空标识的_node if (hashi == _utb->_tab.size()) { _node = nullptr; } } return *this; }

当前链表后一位依旧有数：到下一个节点
后一位没有数：到桶的下一位有链表节点的地方

4. 封装

Map:

template<class K,class V,class hash= hashfunc<K>> class unorderedmap { struct KofT { const K& operator()(const std::pair<K, V>& kv) { return kv.first; } }; typedef typename hashtab<K, std::pair<const K, V>, KofT, hash>::Iterator iterator; typedef typename hashtab<K, std::pair<const K, V>, KofT, hash>::ConstIterator const_iterator; public: iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } std::pair<iterator, bool> insert(const std::pair<K, V>& kv) { return _ht.Insert(kv); } V& operator[](const K& k) { std::pair<iterator, bool> ret = insert({ k,V() }); return ret.first->second; } iterator Find(const K& key) { return _ht.Find(key); } bool Erase(const K& key) { return _ht.Erase(key); } private: hashtab<K, std::pair<const K, V>, KofT, hash> _ht; };

Set:

template<class K, class hash = hashfunc<K>> class unorderedset { struct KofT { const K& operator()(const K& k) const { return k; } }; typedef typename hashtab<K, K, KofT, hash>::Iterator iterator; typedef typename hashtab<K, K, KofT, hash>::ConstIterator const_iterator; public: iterator begin() { return _ht.Begin(); } iterator end() { return _ht.End(); } const_iterator begin() const { return _ht.Begin(); } const_iterator end() const { return _ht.End(); } std::pair<iterator, bool> insert(const K& k) { return _ht.Insert(k); } K& operator[](const K& k) { std::pair<iterator, bool> ret = insert(k); return ret.first; } iterator Find(const K& key) { return _ht.Find(key); } bool Erase(const K& key) { return _ht.Erase(key); } private: hashtab<K, K, KofT, hash> _ht; };

和map，set类似，需要key，data（map为<K,V>,set为K）
同样需要传keyoft用来取出key值

【C++】2.7 哈希表及其实现（附代码）

Ne0inhk

一. 哈希表的使用

二、基本概念

三、哈希函数

1. 除法散列法（除留余数法）

2. 乘法散列法

3. 全域散列法

四、开放寻址法哈希表

1. 枚举状态

2. 成员，初始化