哈希表及模拟实现

目录

一、哈希表的概念 

二、模拟实现哈希表

1.开放地址法

(1)哈希表的数据加上状态标志

(2)哈希表扩容：载荷因子

(3)哈希函数：不同数据类型转换为整型

(4)完整代码

2.链地址法（哈希桶）

(1)哈希表扩容：载荷因子

(2)完整代码

---

一、哈希表的概念 

哈希表本质是一个数组（数组中的每个位置称为槽或桶），数据检索十分高效，它利用哈希函数将键值对映射到哈希表中的特定位置，哈希函数可以计算键的哈希值，从而确定该键值对在哈希表中的存储位置（理想的哈希函数要尽可能均匀地分布键值对）。

冲突：

例如存在键值对<1, 'A'>、<100001, 'B'>、<999, 'C'>、<345, 'D'>，哈希函数为h(key)=key%10，所以<1, 'A'>存储在1位置，<100001, 'B'>存储在1位置，<999, 'C'>存储在9位置，<345, 'D'>存储在5位置，<1, 'A'>和<100001, 'B'>发生冲突。

冲突处理：

冲突处理的方法有两种：开放地址法和链地址法

• 开放地址法：当发生冲突时，寻找哈希表的下一个空位置，将键值对存储进其中（寻找哈希表下一个空位置的常见方法又有三种：线性探测、二次探测、双哈希）。开放地址法会导致其他键值对原本的位置被占用，又需要重新寻找下一个空位置。
• 链地址法：哈希表中的每一个位置是一个链表（或者其他动态数据结构），发生冲突的键值对都会被存储到该链表中。如果要查找键值对，先要找到哈希表中链表的位置，再在链表中搜索

二、模拟实现哈希表

1.开放地址法

开放地址法在存储键值对时，首先会根据键值对的键计算哈希值，确定键值对所在槽，如果该槽已被其他数据所占，则向后遍历哈希寻找空槽，再将数据存储到空槽中。

(1)哈希表的数据加上状态标志

假设开放地址法使用的是线性探测解决冲突，当键值对原本的槽被占用时，会向后遍历寻找最近的一个空槽。这就说明当哈希表中未发生数据删除时，两个冲突数据之间一定是没有空槽的。所以开放地址法的查找函数结束条件是查找到空槽。

问题出现：当哈希表中数据被删除时，且恰巧删除的是某两个冲突数据位置之间的数据，那么此时的查找函数就会出问题，因为两个冲突数据之间存在了空槽，就会导致无法查找到后一个数据。

问题解决：哈希表的数据不仅存储的键值对，还要存储一个状态标志，表示该槽为空，还是数据被删除，还是不为空。使用结构体封装键值对和状态标志作为哈希表的存储元素。这样查找函数查找到空槽就分为两种：槽中数据被删除、槽为空，只有当槽为空时才为结束条件

//状态标志
enum State {EMPTY,//槽为空EXIST,//槽不为空DELETE//槽中数据被删除
};
//哈希表数据元素
template<class K,class V>
struct HashData {std::pair<K, V> _kv;//键值对State _state = EMPTY;//状态标志
};
//哈希表
template<class K,class V>
class HashTable {
private:std::vector<HashData<K, V>> _tables;//哈希表size_t _n = 0;//哈希表中已经存储的元素个数
};

(2)哈希表扩容：载荷因子

载荷因子=哈希表已存元素个数/哈希表总容量

哈希表中存储的元素越多，冲突率就越高，哈希表查找效率就越低

即载荷因子越大，冲突率越高，哈希表效率越低，空间利用率越高；

    载荷因子越小，冲突率越小，哈希表效率越高，空间利用率越低。

因此不能使哈希表满，而且必须在哈希表满之前就扩容。为此我们可以根据载荷因子设定一个界限，载荷因子既不能太大，也不能太小。例如当载荷因子大于0.7时就扩容。

扩容方法：

哈希表的扩容不仅要将哈希表长度变大，还要将哈希表中的数据重新映射

创建一个新对象，将新对象中的哈希表扩容为旧哈希表的二倍，再复用insert函数将数据重新映射到新对象的哈希表中，最后将新对象的哈希表赋值给旧对象。

（下述insert函数还未完善，没有防止数据冗余）

//构造函数
HashTable()
{_tables.resize(10);//哈希表容量初始化为10，避免计算载荷因子时除数为0
}
//插入函数
void insert(const std::pair<K, V>& kv)
{//扩容if (_n / (float)_tables.size() >= 0.7){HashTable<K, V> newHT;//新对象newsize = 2 * _tables.size();//新容量（2倍扩容）newHT._tables.resize(newsize);//重新映射for (int i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST)newHT.insert(_tables[i]._kv);}_tables = newHT._tables;}//计算哈希值int hashi = kv.first % _tables.size();//线性探测：寻找空槽while (_tables[hashi]._state == EXIST){++hashi;hashi = hashi % _tables.size();//哈希表的线性探测是循环的，查找到哈希表末尾后会跳转到哈希表头部继续查找}//插入数据_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;
}

(3)哈希函数：不同数据类型转换为整型

哈希函数为key值%哈希表大小，但是如果key是string等其他类型，无法做取模运算，就需要先将key转换为整型再取模。

key的可能类型有许多，因此需要进行泛型编程：设计仿函数，对于可以直接强转为整型的数据使用默认的仿函数，对于其他不能直接强转为整型的数据需要自己提供仿函数将数据转换为整型。

例如string类型，可以采用直接相加法（将所有的字符的ASCII码相加得到整数）、位运算法（将每个字符的ASCII码左移后再相加）。

此处介绍的是BKDRHash算法：遍历字符串，当前哈希值乘131再加上当前字符的ASCII码值。

对比unordered_set和unordered_set发现，这两个容器对于key为string类型时并没有需要自己提供哈希函数，这是因为unordered_set和unordered_set源码中对string类型进行了模板特化。所以我们在模拟实现时也是用模板特化：特化string，当key类型是int、float等可以直接强转为整型的数据就使用默认的哈希函数，如果是string类型就使用特化的哈希函数，如果是其他类型就需要我们自己提供哈希函数将key值转换为整型数据。

//默认哈希函数（仿函数），针对可以直接强转为整型的类型
template<class K>
struct HashFunc {size_t operator()(const K& key){return size_t(key);}
};
//默认哈希函数对string类型进行模板特化
template<>
struct HashFunc<std::string> {size_t operator()(const std::string& key){size_t hashi = 0;for (auto& ch : key){hashi *= 131;hashi += ch;}return hashi;}
};
//哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:std::vector<HashData<K, V>> _tables;//哈希表size_t _n = 0;//哈希表中已经存储的元素个数
......
......

(4)完整代码

#include <iostream>
#include <vector>
#include <string>
//状态标志
enum State {EMPTY,//槽为空EXIST,//槽不为空DELETE//槽中数据被删除
};
//哈希表数据元素
template<class K, class V>
struct HashData {std::pair<K, V> _kv;//键值对State _state = EMPTY;//状态标志
};
//默认哈希函数（仿函数），针对可以直接强转为整型的类型
template<class K>
struct HashFunc {size_t operator()(const K& key){return size_t(key);}
};
//默认哈希函数对string类型进行模板特化
template<>
struct HashFunc<std::string> {size_t operator()(const std::string& key){size_t hashi = 0;for (auto& ch : key){hashi *= 131;hashi += ch;}return hashi;}
};
//哈希表
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
private:std::vector<HashData<K, V>> _tables;//哈希表size_t _n = 0;//哈希表中已经存储的元素个数
public://构造函数HashTable(){_tables.resize(10);//哈希表容量初始化为10，避免计算载荷因子时除数为0}//插入函数bool Insert(const std::pair<K, V>& kv){//防止数据冗余if (Find(kv.first))return false;//扩容if (_n / (float)_tables.size() >= 0.7){HashTable<K, V> newHT;//新对象size_t newsize = 2 * _tables.size();//新容量（2倍扩容）newHT._tables.resize(newsize);//重新映射for (int i = 0; i < _tables.size(); ++i){if (_tables[i]._state == EXIST)newHT.Insert(_tables[i]._kv);}//新表赋值给旧表_tables = newHT._tables;}//计算哈希值Hash hs;size_t hashi = hs(kv.first) % _tables.size();//线性探测：寻找空槽（DELETE和EMPTY都行）while (_tables[hashi]._state == EXIST){++hashi;hashi = hashi % _tables.size();//哈希表的线性探测是循环的，查找到哈希表末尾后会跳转到哈希表头部继续查找}//插入数据_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;}//查找函数HashData<K, V>* Find(const K& key){//计算哈希值Hash hs;size_t hashi = hs(key) % _tables.size();//线性探测：找到空槽结束（只有EMPTY才行）while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._state != DELETE){if (_tables[hashi]._kv.first == key)return &_tables[hashi];//查找成功}++hashi;hashi = hashi % _tables.size();}//未查找到return nullptr;}//删除函数bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret == nullptr)return false;else{ret->_state = DELETE;--_n;return true;}}
};
void test()
{HashTable<std::string, std::string> ht;ht.Insert({ "5","5"}); ht.Insert({"10","10"}); ht.Insert({"8", "8"});std::cout << ht.Find("8") << std::endl;std::cout << ht.Find("5") << std::endl;std::cout << ht.Find("20") << std::endl;ht.Erase("8");std::cout << ht.Find("8") << std::endl;std::cout << ht.Find("5") << std::endl;std::cout << ht.Find("20") << std::endl;
}
int main()
{test();return 0;
}

2.链地址法（哈希桶）

链地址法存储键值对时，哈希表的每一个位置其实是一个链表，当键值对要存储的槽已经被其他数据所占时，会直接头插在该槽的链表中。

(1)哈希表扩容：载荷因子

链地址法中的哈希表也需要扩容，否则哈希表中的链表会很长，效率低。采用链地址法的哈希表也是需要根据载荷因子决定是否扩容，载荷因子的值通常设置为1（源码中就是1）。

和开放地址法一样，扩容时创建新哈希表，复用Insert函数，并且哈希表中的链表的所有元素都要重新映射。但是这个方法效率低下，因为复用Insert函数在遍历旧哈希表时，每次都需要创建新的节点数据插入新哈希表，之后还要再销毁该节点数据。

改进方法：遍历旧哈希表，直接使用旧哈希表中的节点数据存入新哈希表，不再复用Insert函数和创建新节点数据。

//插入函数
bool Insert(const std::pair<K, V>& kv)
{//防止数据冗余if (Find(kv.first))return false;//扩容if (_n / _tables.size() >= 1){//HashTable<K, V> newHT;//创建新哈希表//newHT._tables.resize(2 * _tables.size());//2倍扩容//创建新哈希表std::vector<Node*> newtables(2 * _tables.size());//数据重新映射到新表中（链表中的所有数据都要重新映射）for (int i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//计算哈希值Hash hs;size_t hashi = hs(cur->_kv.first) % newtables.size();//直接将旧哈希表中的数据存入新哈希表（头插）cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;//复用Insert函数方法（舍弃）//Node* cur = _tables[i];//while (cur)//{//	newHT.Insert(cur->_kv);//	cur = cur->_next;//}}_tables = newtables;}//计算哈希值Hash hs;size_t hashi = hs(kv.first) % _tables.size();//插入数据（头插）Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

(2)完整代码

namespace hash_bucket {//哈希表数据元素template<class K, class V>struct HashNode {std::pair<K, V> _kv;//键值对struct HashNode<K, V>* _next;//链表指针//构造函数HashNode(const std::pair<K, V> kv):_kv(kv),_next(nullptr){}};//默认哈希函数（仿函数），针对可以直接强转为整型的类型template<class K>struct HashFunc {size_t operator()(const K& key){return size_t(key);}};//默认哈希函数对string类型进行模板特化template<>struct HashFunc<std::string> {size_t operator()(const std::string& key){size_t hashi = 0;for (auto& ch : key){hashi *= 131;hashi += ch;}return hashi;}};//哈希表template<class K, class V, class Hash = HashFunc<K>>class HashTable{typedef HashNode<K, V> Node;private:std::vector<Node*> _tables;//哈希表size_t _n;//哈希表中已存元素个数public://构造函数HashTable(){_tables.resize(10);_n = 0;}//拷贝构造函数HashTable(const HashTable& ht){_tables = new std::vector<Node*>(ht._tables.size());_n = ht._n;}//析构函数（释放哈希表中每个槽中的链表）~HashTable(){for (int i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}//插入函数bool Insert(const std::pair<K, V>& kv){//防止数据冗余if (Find(kv.first))return false;//扩容if (_n / _tables.size() >= 1){//HashTable<K, V> newHT;//创建新哈希表//newHT._tables.resize(2 * _tables.size());//2倍扩容//创建新哈希表std::vector<Node*> newtables(2 * _tables.size());//数据重新映射到新表中（链表中的所有数据都要重新映射）for (int i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//计算哈希值Hash hs;size_t hashi = hs(cur->_kv.first) % newtables.size();//直接将旧哈希表中的数据存入新哈希表（头插）cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;//复用Insert函数方法（舍弃）//Node* cur = _tables[i];//while (cur)//{//	newHT.Insert(cur->_kv);//	cur = cur->_next;//}}_tables = newtables;}//计算哈希值Hash hs;size_t hashi = hs(kv.first) % _tables.size();//插入数据（头插）Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}//查找函数Node* Find(const K& key){//计算哈希值Hash hs;size_t hashi = hs(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){Node* ret = Find(key);if (ret == nullptr)return false;else{//计算哈希值，确认数据所在槽Hash hs;size_t hashi = hs(key) % _tables.size();if (_tables[hashi]->_kv.first == key)//key是所在槽中链表的的头节点{Node* cur = _tables[hashi];_tables[hashi] = cur->_next;delete(cur);}else//key是所在槽中链表的的中间节点{Node* cur = _tables[hashi];Node* prev = cur;while (cur->_kv.first != key){prev = cur;cur = cur->_next;}//删除数据Node* temp = cur;prev->_next = cur->_next;delete(temp);}--_n;return true;}}};
}
void test2()
{hash_bucket::HashTable<std::string, int> ht;ht.Insert({ "10",10 }); ht.Insert({ "8",8 }); ht.Insert({ "2",2 }); ht.Insert({ "9",9 }); ht.Insert({ "1",1 });ht.Insert({ "3",3 }); ht.Insert({ "4",4 }); ht.Insert({ "6",6 }); ht.Insert({ "7",7 }); ht.Insert({ "5",5 });ht.Insert({ "888",888 });std::cout << ht.Find("10") << std::endl;std::cout << ht.Find("8") << std::endl;std::cout << ht.Find("999") << std::endl;ht.Erase("10");std::cout << ht.Find("10") << std::endl;std::cout << ht.Find("8") << std::endl;std::cout << ht.Find("999") << std::endl;
}
int main()
{//test1();test2();return 0;
}