深入浅出C++ ——哈希

前言

    在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，unordered系列的关联式容器的底层结构采用哈希结构。
    map/set的遍历是有序的，而unordered系列容器遍历是无序的。map/set是双向迭代器，而unordered系列容器只支持单向迭代器。但是当对大量数据进行增删改查时，unordered系列容器的效率更高，尤其是查找的效率。

一、unordered系列关联式容器

1. unordered_map

构造

函数声明	功能介绍
unordered_map()	构造空的unordered_map对象

---

容量

函数声明	功能介绍
bool empty() const	检测unordered_map是否为空
size_t size() const	获取unordered_map的有效元素个数

---

迭代器

函数声明	功能介绍
begin	返回unordered_map第一个元素的迭代器
end	返回unordered_map最后一个元素下一个位置的迭代器
cbegin	返回unordered_map第一个元素的const迭代器
cend	返回unordered_map最后一个元素下一个位置的const迭代器

---

元素访问

函数声明	功能介绍
operator[]	返回与key对应的value，没有一个默认值

---

查询

函数声明	功能介绍
iterator find(const K& key)	返回key在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中关键码为key的键值对的个数

---

修改

函数声明	功能介绍
insert	向容器中插入键值对
erase	删除容器中的键值对
void clear()	清空容器中有效元素个数
void swap(unordered_map&)	交换两个容器中的元素

---

桶操作

函数声明	功能介绍
size_t bucket_count()const	返回哈希桶中桶的总个数
size_t bucket_size(size_t n)const	返回n号桶中有效元素的总个数
size_t bucket(const K& key)	返回元素key所在的桶号

---

2. unordered_set

    unordered_set的函数基本上与unordered_map类似，故不在说明。另外，在使用方面，unordered系列的容器与map/set容器也基本类似。可以说除了底层结构和unordered系列操作哈希桶外，两者没有区别。

二、哈希

1. 哈希概念

    顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O($lo{g}_{2}N$)，搜索的效率取决于搜索过程中元素的比较次数。理想的搜索方法是不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

---

哈希方法

    插入元素时，根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。搜索元素时，对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。

    该方式即为哈希/散列方法，哈希方法中使用的转换函数称为哈希/散列函数，构造出来的结构称为哈希表(Hash Table)/称散列表。

---

2. 哈希冲突

    对于两个数据元素的关键字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) ==Hash($k_j$)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。引起哈希冲突的一个原因可能是哈希函数设计不够合理。哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

---

3. 哈希函数

（1）直接定址法

     取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B ；该方法优点是简单、均匀，不存在哈希冲突，缺点是需要事先知道关键字的分布情况，适合查找比较小且连续的情况。

---

（2）除留余数法

     设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p (p<=m),将关键码转换成哈希地址。

---

（3）其他方法

     哈希函数还有采用平方取中法、折叠法、随机数法、数学分析法等等，但是不常用，常用的还是前两种方法。

---

4. 哈希冲突解决方法

     解决哈希冲突两种常见的方法是闭散列和开散列。

---

（1）闭散列

     闭散列也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。 寻找下一个空位置可以使用线性探测和二次探测。

---

线性探测

     线性探测是从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

     插入时，通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素。如图所示，44与4发生冲突，使用线性探测法，插入44到哈希表中位置为8的空位置。

    给定一个负载因子为填入表中的元素个数/散列表的长度，负载因子越大，冲突概率越大，效率越低，空间利用率越高；负载因子越小，冲突概率越小，效率越高，空间利用率越低。

     删除时，采用闭散列处理哈希冲突，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

---

二次探测

     线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：$H_i$ = ($H_0$ + $i^2$ )% m, 其中：i =1,2,3…， $H_0$是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。

---

代码实现

namespace CloseHash
{//哈希表每个空间给个标记，EMPTY此位置空， EXIST此位置已经有元素， DELETE元素已经删除enum State{EMPTY,EXIST,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};//使用仿函数，将key转换为无符号的整形，方便插入时取模计算位置template<class K> struct HashFunc{size_t operator()(const K& key){return (size_t)key;  }};// 模板特化  支持string类型转换为无符号整形template<>struct HashFunc<string>{// BKDR算法size_t operator()(const string& key){size_t val = 0;for (auto ch : key){val *= 131;val += ch;}return val;}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 负载因子到了就扩容if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7) // 扩容{size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;HashTable<K, V, Hash> newHT; //这样可以复用insert函数newHT._tables.resize(newSize);// 旧表的数据映射到新表for (auto e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);}}_tables.swap(newHT._tables);}//使用仿函数，将key转换为无符号的整形Hash hash;size_t hashi = hash(kv.first) % _tables.size();// 线性探测while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_size; 二次探测//Hash hash;//size_t start = hash(kv.first) % _tables.size();//size_t i = 0;//size_t hashi = start;//while (_tables[hashi]._state == EXIST)//{//	++i;//	hashi = start + i*i;//	hashi %= _tables.size();//}//_tables[hashi]._kv = kv;//_tables[hashi]._state = EXIST;//++_size;return true;}HashData<K, V>* Find(const K& key){if (_tables.size() == 0){return nullptr;}Hash hash;size_t start = hash(key) % _tables.size();size_t hashi = start;while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;hashi %= _tables.size();if (hashi == start){break;}}return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_size;return true;}else{return false;}}void Print(){for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST){printf("[%d:%d] ", i, _tables[i]._kv.first);}else{printf("[%d:*] ", i);}}cout << endl;}private:vector<HashData<K, V>> _tables;size_t _size = 0; // 存储多少个有效数据};
}

---

（2）开散列

     开散列法又叫链地址法/开链法，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。 如图所示，开散列中每个桶中放的都是发生哈希冲突的元素。

---

开散列增容

     开散列最好的情况是每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。

---

哈希桶实现开散列

//使用仿函数，将key转换为无符号的整形，方便插入时取模计算位置
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{// BKDRsize_t operator()(const string& key){size_t val = 0;for (auto ch : key){val *= 131;val += ch;}return val;}
};namespace Bucket
{template<class K, class V>struct HashNode{pair<K, V> _kv;HashNode<K, V>* _next;HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;public:~HashTable(){for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}// 如果hash的size是素数，可以减少冲突inline size_t __stl_next_prime(size_t n){static const size_t __stl_num_primes = 28;static const size_t __stl_prime_list[__stl_num_primes] ={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 < __stl_num_primes; ++i){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return -1;}bool Insert(const pair<K, V>& kv){// 去重if (Find(kv.first)){return false;}Hash hash;// 负载因子到1就扩容if (_size == _tables.size()){//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newTables;//newTables.resize(newSize, nullptr);newTables.resize(__stl_next_prime(_tables.size()), nullptr); //扩容时，resize素数表中数据的大小// 旧表中节点移动映射新表for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hash(cur->_kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hash(kv.first) % _tables.size();// 头插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_size;return true;}Node* Find(const K& key){if (_tables.size() == 0){return nullptr;}Hash hash;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){if (_tables.size() == 0){return false;}Hash hash;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){// 1、头删// 2、中间删if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_size;return true;}prev = cur;cur = cur->_next;}return false;}size_t Size(){return _size;}// 表的长度size_t TablesSize(){return _tables.size();}// 桶的个数size_t BucketNum(){size_t num = 0;for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){++num;}}return num;}size_t MaxBucketLenth(){size_t maxLen = 0;for (size_t i = 0; i < _tables.size(); ++i){size_t len = 0;Node* cur = _tables[i];while (cur){++len;cur = cur->_next;}if (len > maxLen){maxLen = len;}}return maxLen;}private:vector<Node*> _tables;size_t _size = 0; // 存储有效数据个数};
}

---

开散列与闭散列比较

    由于闭散列法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子，而表项所占空间又比指针大的多，所以使用开散列法反而比闭散列法节省存储空间。

---

三、模拟实现unordered系列容器

1. 哈希表的改造

    哈希表的改造时，对模板参数列表的改造，增加迭代器操作

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 特化  
template<>
struct HashFunc<string>
{// BKDRsize_t operator()(const string& key){size_t val = 0;for (auto ch : key){val *= 131;val += ch;}return val;}
};namespace Bucket
{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};// 前置声明template<class K, class T, class Hash, class KeyOfT>class HashTable;//迭代器template<class K, class T, class Hash, class KeyOfT>struct __HashIterator{typedef HashNode<T> Node;typedef HashTable<K, T, Hash, KeyOfT> HT;typedef __HashIterator<K, T, Hash, KeyOfT> Self;Node* _node;HT* _pht;__HashIterator(Node* node, HT* pht):_node(node), _pht(pht){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){if (_node->_next){// 当前桶中迭代_node = _node->_next;}else{// 找下一个桶Hash hash;KeyOfT kot;size_t i = hash(kot(_node->_data)) % _pht->_tables.size();++i;for (; i < _pht->_tables.size(); ++i){if (_pht->_tables[i]){_node = _pht->_tables[i];break;}}// 说明后面没有有数据的桶了if (i == _pht->_tables.size()){_node = nullptr;}}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};template<class K, class T, class Hash, class KeyOfT>class HashTable{typedef HashNode<T> Node;template<class K, class T, class Hash, class KeyOfT>friend struct __HashIterator;public:typedef __HashIterator<K, T, Hash, KeyOfT> iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){return iterator(_tables[i], this);}}return end();}iterator end(){return iterator(nullptr, this);}~HashTable(){for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}inline size_t __stl_next_prime(size_t n){static const size_t __stl_num_primes = 28;static const size_t __stl_prime_list[__stl_num_primes] ={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 < __stl_num_primes; ++i){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return -1;}pair<iterator, bool> Insert(const T& data){Hash hash;KeyOfT kot;// 去重iterator ret = Find(kot(data));if (ret != end()){return make_pair(ret, false);}// 负载因子到1就扩容if (_size == _tables.size()){//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector<Node*> newTables;//newTables.resize(newSize, nullptr);newTables.resize(__stl_next_prime(_tables.size()), nullptr);// 旧表中节点移动映射新表for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hash(kot(data)) % _tables.size();// 头插Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_size;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){if (_tables.size() == 0){return end();}Hash hash;KeyOfT kot;size_t hashi = hash(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return end();}bool Erase(const K& key){if (_tables.size() == 0){return false;}Hash hash;KeyOfT kot;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){// 1、头删// 2、中间删if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_size;return true;}prev = cur;cur = cur->_next;}return false;}size_t Size(){return _size;}// 表的长度size_t TablesSize(){return _tables.size();}// 桶的个数size_t BucketNum(){size_t num = 0;for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){++num;}}return num;}size_t MaxBucketLenth(){size_t maxLen = 0;for (size_t i = 0; i < _tables.size(); ++i){size_t len = 0;Node* cur = _tables[i];while (cur){++len;cur = cur->_next;}//if (len > 0)//printf("[%d]号桶长度:%d\n", i, len);if (len > maxLen){maxLen = len;}}return maxLen;}private:vector<Node*> _tables;size_t _size = 0; // 存储有效数据个数};
}

---

2. 模拟实现 unordered_set

namespace Jared
{template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename Bucket::HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}private:Bucket::HashTable<K, K, Hash, SetKeyOfT> _ht;};
}

---

3. 模拟实现 unordered_map

namespace Jared
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> Insert(const pair<K, V>& kv){return _ht.Insert(kv);}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}private:Bucket::HashTable<K, pair<K, V>, Hash, MapKeyOfT> _ht;};
}