C++：哈希表

哈希表概念

哈希表可以简单理解为：把数据转化为数组的下标，然后用数组的下标对应的值来表示这个数据。如果我们想要搜索这个数据，直接计算出这个数据的下标，然后就可以直接访问数组对应的位置，所以可以用O(1)的复杂度直接找到数据。

其中，这个数据对应的数字叫做关键码(Key)，这个把关键码转化为下标的规则，叫做哈希函数(Hash)。

要注意的是，有一些数据并不是整型，比如字符串，对象等等。对于这种数据，我们要先用一套规则把它们转化为整数（关键码），然后再通过哈希函数映射为数组下标。

---

哈希函数

哈希函数原则：

1. 哈希函数转换后，生成的地址（下标）必须小于哈希表的最大地址（下标）
2. 哈希函数计算出来的地址（下标）必须均匀地分布
3. 哈希函数尽可能简单

直接定址法

取关键字的某个线性函数为哈希表的地址：

除留余数法

假设哈希表的地址数目为m，取Key对m取模后得到的值作为下标

---

闭散列 - 开放定址法

闭散列，也叫做开放定址法，当发生哈希冲突时，如果哈希表没有被装满，说明哈希表中还有空位置，那么我们可以把发生冲突的数据放到下一个空位置去。

基本结构

首先我们需要一个枚举，来标识哈希表的不同状态：

enum State
{EMPTY,EXIST,DELETE
};

EMPTY：空节点
EXIST：数值存在
DELETE：数值被删除 

哈希表的基本结构：

enum State
{EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;//标记状态
};template<class K, class V>
class HashTable
{
public:HashTable(size_t size = 10){_tables.resize(size);}private:vector<HashData<K, V>> _tables;//哈希表size_t _n = 0;//元素个数
};

HashTable构造函数：

HashTable(size_t size = 10)
{_tables.resize(size);
}

---

查找

想要在哈希表中查找数据，无非就遵顼以下规则：

通过哈希函数计算出数据对应的地址
去地址处查找，如果地址处不是目标值，往后继续查找
遇到EMPTY还没有找到，说明数据不存在哈希表中
遇到DELETE和EXIST，继续往后查找

代码如下：

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

但是当前的代码存在一个问题：哈希表作用于泛型，key % _tables.size()有可能是违法的行为，因为key可能不是一个数字。

对此我们可以在模板中多加一个仿函数的参数，用户可以在仿函数中自定义数据 -> 整型的转换规则，然后我们在对这个整型使用除留余数法获取地址。

在那之前，我们可以先写一个仿函数，用于处理整型 -> 整型的转化：

struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};

在STL中，整型-> 整型转化的函数，被写为了一个模板，而这个string -> 整型被写为了一个模板特化：

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto& e : s)//把字符串的每一个字符ASCII码值加起来{hash += e;hash *= 131; // 31, 131313(任意由1，3间断排列的数字)}return hash;}
};

我们将这个HashFunc<K>仿函数作为哈希表的第三个模板参数的默认值：

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{};

通过仿函数来统一获得整型，再进行除留余数操作：

Hash hs;
size_t hashi = hs(key) % _tables.size();

---

插入

插入的基本逻辑如下：

1. 先通过Find接口，查找目标值在不在哈希表中，如果目标值已经存在，返回flse，表示插入失败
2. 通过哈希函数计算出目标值对应的下标
3. 向下标中插入数据：如果下标对应的位置已经有数据，往后查找，直到某一个位置为EMPTY或者DELETE.如果下标对应的位置没有数据，直接插入
4. 插入后，把对应位置的状态转化为EXIST

代码如下：

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;Hash hs;//仿函数实例化出的对象size_t hashi = hs(kv.first) % _tables.size();//获得目标值对应的下标while (_tables[hashi]._state == EXIST)//往后查找合适的位置插入{hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;//插入_tables[hashi]._state = EXIST;//改变状态_n++;//哈希表中的元素个数+1return true;
}

当这个哈希表越满，我们查找数据的效率就越低，甚至说：如果查找一个不存在的数据，我们可能要用O(N)的复杂度遍历整个哈希表.因此我们因该把哈希表的负载率控制在一定值，当超过一定值，我们就要进行扩容操作。

if ((double)_n / _tables.size() >= 0.7)
{size_t newSize = _tables.size() * 2;HashTable<K, V, Hash> newHT(newSize);for (auto& e : _tables){if (e._state == EXIST)newHT.Insert(e._kv);}_tables.swap(newHT._tables);
}

插入总代码：

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;if ((double)_n / _tables.size() >= 0.7){size_t newSize = _tables.size() * 2;HashTable<K, V, Hash> newHT(newSize);for (auto& e : _tables){if (e._state == EXIST)newHT.Insert(e._kv);}_tables.swap(newHT._tables);}Hash hs;size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;
}

删除

先通过Find接口找到要删除的值

• 如果没找到，返回false，表示删除失败
• 如果找到，把对应节点的状态改为DELETE

最后再把哈希表的_n - 1，表示存在的节点数少了一个。

代码如下：

bool Erase(const K& key)
{HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;_n--;return true;}return false;
}

总代码展示

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto& e : s)//把字符串的每一个字符ASCII码值加起来{hash += e;hash *= 131; // 31, 131313(任意由1，3间断排列的数字)}return hash;}
};enum State
{EMPTY,EXIST,DELETE
};template<class K, class V>
struct HashData
{pair<K, V> _kv;State _state = EMPTY;//标记状态
};template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:HashTable(size_t size = 10){_tables.resize(size);}HashData<K, V>* Find(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (_tables[hashi]._kv.first == key&& _tables[hashi]._state == EXIST)return &_tables[hashi];hashi++;hashi %= _tables.size();}return nullptr;}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;if ((double)_n / _tables.size() >= 0.7){size_t newSize = _tables.size() * 2;HashTable<K, V, Hash> newHT(newSize);for (auto& e : _tables){if (e._state == EXIST)newHT.Insert(e._kv);}_tables.swap(newHT._tables);}Hash hs;size_t hashi = hs(kv.first) % _tables.size();while (_tables[hashi]._state == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;_n--;return true;}return false;}private:vector<HashData<K, V>> _tables;size_t _n = 0;//元素个数
};

---

开散列 - 哈希桶

在STL库中，采用的是更加优秀的开散列方案。

哈希表的数组vector中，不再直接存储数据，而是存储一个链表的指针。当一个数值映射到对应的下标后，就插入到这个链表中。其中每一个链表称为一个哈希桶，每个哈希桶中，存放着哈希冲突的元素.

基本结构

对于每一个节点，其要存储当前节点的值，也要存储下一个节点的指针，基本结构如下：

template<class K, class V>
struct HashNode
{HashNode<K, V>* _next;pair<K, V> _kv;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(size_t size = 10){_tables.resize(size);}private:vector<Node*> _tables; //链表指针数组size_t _n = 0;//元素个数
};

析构函数，防止内存泄漏：

~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;}
}

查找

查找的基本逻辑如下：

1. 先通过哈希函数计算出数据对应的下标
2. 通过下标找到对应的链表
3. 遍历链表，找数据:如果某个节点的数据匹配上了，返回该节点指针,如果遍历到了nullptr，返回空指针表示没找到

代码如下：

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;
}

插入

插入的基本逻辑如下：

1. 先通过Find接口，查找目标值在不在哈希表中，如果目标值已经存在，返回flse，表示插入失败
2. 通过哈希函数计算出目标值对应的下标
3. 向下标中插入数据

代码如下：

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;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;
}

关于扩容:如果我们单纯的进行插入，就要把原先的所有节点释放掉，再创建新的节点。这样会浪费很多时间。我们最好把原先创建的节点利用起来，因此我们要重写一个逻辑，把原先的节点进行迁移。 

if (_n == _tables.size())
{vector<Node*> newTables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hs(cur->_kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr; //防止移交的节点被析构}_tables.swap(newTables);
}

删除

删除逻辑：

1. 通过哈希函数计算出对应的下标
2. 到对应的哈希桶中查找目标值

• 如果找到，删除对应的节点
• 如果没找到，返回false表示删除失败
• _n - 1表示删除了一个元素

代码如下：

bool Erase(const K& key)
{Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev)prev->_next = cur->_next;else_tables[hashi] = cur->_next;delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;
}

代码展示

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto& e : s)//把字符串的每一个字符ASCII码值加起来{hash += e;hash *= 131; // 31, 131313(任意由1，3间断排列的数字)}return hash;}
};template<class K, class V>
struct HashNode
{HashNode<K, V>* _next;pair<K, V> _kv;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(size_t size = 10){_tables.resize(size);}~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;}}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 Insert(const pair<K, V>& kv){if (Find(kv.first))return false;Hash hs;//哈希桶情况下，负载因子到1才扩容if (_n == _tables.size()){vector<Node*> newTables(_tables.size() * 2, nullptr);for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hs(cur->_kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr; //防止移交的节点被析构}_tables.swap(newTables);}size_t hashi = hs(kv.first) % _tables.size();Node* newNode = new Node(kv);newNode->_next = _tables[hashi];_tables[hashi] = newNode;++_n;return true;}bool Erase(const K& key){Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (prev)prev->_next = cur->_next;else_tables[hashi] = cur->_next;delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables; //链表指针数组size_t _n = 0;//元素个数
};