前言
之前我们学习了红黑树，其虽然通过自平衡机制提供了高效的查找、插入和删除操作，但其操作仍依赖于树的高度，最坏情况下的时间复杂度为O(log n)。当我们希望能够实现常数时间复杂度的查找操作时，哈希表便成为了一个更优的选择。哈希表虽然不再像红黑树的元素一样默认有序，但其通过 “ 哈希 ” 将数据进行映射，从而在理想情况下实现O(1)时间复杂度的操作，在某些需要高效查找的场景非常实用。本篇文章，我们将深入学习哈希表的相关知识，并尝试实现。
一、哈希表的概念
哈希表（Hash Table），也叫做散列表，是一种特殊的数据结构。其通过一定的规则将数据进行 “ 散乱排列 ” ， 并通过该规则进行快速查找。这个规则叫做 “ 哈希函数 ” ，其可以将数据转化为一个固定的索引值，后续将该数据根据索引值存储在数组的某个位置。当进行查找时，直接通过 “ 哈希函数 ” 求出数据的索引值，理想状态下就能在常数时间内完成查找。
二、哈希函数的实现方法
在理想状态下，哈希函数会将数据均匀散列分布在哈希表当中。为了尽量逼近这个理想状态，先辈们发明了多种哈希函数的实现方法，如直接定址法、除留余数法、乘法散列法、全域散列法等。其中直接定址法和除留余数法最为常用，我们重点介绍一下。
1. 直接定址法
当数据的范围比较集中时，优先考虑使用直接定址法。例如有一组数据的范围在0~99之间，那么我们开一个大小为100的数组，然后将数据按照数组下标来存储。比如这组数据当中有3个“6”，那么数组下标为6处的值就是3。
那么当这组数据的下限非0呢？处理方法也很简单。例如这组数据的范围是26个小写英文字母，ascii值在97~122之间。我们开一个大小为26的数组，然后每一个字母对应存储位置的下标即为其ascii值减去'a'的ascii值，这样就可以进行存储了。
当然直接定址法的缺陷也很明显：当数据比较分散且范围很大时，会造成空间浪费。
2. 除留余数法
除留余数法（也叫做除法散列法），是哈希函数最常用的实现方式。它的核心思想是将数据对某个数（一般是表长）进行求余运算，将运算结果作为索引值，即表示该数据存放的下标位置。假设某个哈希表的大小为M，那么哈希函数为：hash(x) = x % M。
如图所示，各个元素通过除留余数法存储在哈希表当中：
注意以下两点：
1. 为了尽量减少哈希冲突出现的次数，建议M取不太接近2的整数次幂的一个素数。
2. 除留余数法中，为了方便数据转化为索引值，要求哈希表的数据元素支持转换为整数。
三、哈希冲突
当一个数据通过哈希函数产生了与另一个数据相同的哈希值，那么也就意味着它们需要存储在同一个位置，显然无法满足。此时的情况就叫做哈希冲突（哈希碰撞）。理想情况下，数据会均匀分布在哈希表中，但是实际场景当中，哈希冲突是无法避免的。所以我们要有适当的方案处理哈希冲突。
处理哈希冲突的方法主要有开放定址法、链地址法、再哈希法和位图法等，**这里只介绍最常用的前两种**。
1. 开放定址法（闭散列）
开放定址法是按照某种策略将冲突的数据放置在表中的另一个空位当中。常见的策略有三种：线性探测、二次探测和双重探测。
线性探测
线性探测指的是从冲突位置开始，依次向后一个一个查找，直到找到空位，再将冲突元素放置在当前空位。 当查找到表尾还没有找到空位，那么从表头位置开始重新查找。
线性探测的缺点是容易造成表中的冲突数据聚集，且会占用其他元素的原本位置，从而影响效率。
二次探测
二次探测对线性探测进行了优化。它的查找方式是依次左右按照二次方跳跃式探测。例如先探测冲突位置的右边 1^{2} 个位置，然后左边 1^{2} 个位置，右边 2^{2} 个位置，左边 2^{2} 个位置......依次类推。
二次探测有效地减少了数据聚集问题。
双重探测
双重探测指的是使用另一个哈希函数计算探测步长，使探测序列更加分散。
2. 链地址法（开散列）
链地址法，也叫做拉链法，它改变了传统的哈希表元素储存策略。在链地址法当中，所有数据不再直接存储在哈希表当中，而是将哈希表的每一个元素设置为指针，用于维护一个链表。此时哈希表的每一个元素就叫做哈希桶。当某个元素位置不存储元素时，该指针为空；若有元素需要存储在该位置，则在其维护的链表中添加该元素。因此，一条链表中存储的元素互相之间就是发生哈希冲突的。
链地址法在发生冲突时，就不会占用其他元素的原本位置，相比开放定址法效率较高。但当某个位置的冲突元素过多时，链表过长，会使查找效率接近O(N)，此时可以考虑将链表换为红黑树。
Java8以及之后的HashMap实现当中，就采用了如上优化：当某个哈希桶维护的链表长度超过8时，将该链表换成红黑树，提升总体性能。
四、装填因子
装填因子（负载因子）是一个数值，表示已存储元素与哈希表容量的比值。当装填因子过大时，哈希表的空间利用率就越高，发生哈希冲突的概率就越高，哈希表的总体性能就越低。
在实际实现当中，为了保证哈希表的高效，我们将装填因子作为哈希表是否需要扩容的标准。当装填因子到达一定阈值时，哈希表就需要扩容。若哈希表使用开放定址法处理冲突，那么该阈值通常在0.7~0.8之间；若使用链地址法，则该阈值通常为1。
五、哈希表的实现
接下来我们将选用除留余数法的哈希函数，并用线性探测和链地址法两种解决冲突的策略分别实现一个哈希表。至于其他方法，这里就不再一一实现。
与之前实现AVL树和红黑树相同，我们的实现当中将键值对作为数据元素，其哈希值由键Key来决定。
1. 线性探测法实现
整形转化的支持与字符串哈希
之前提到哈希表的数据元素要支持转化为整形，所以在这里我们需要实现一个仿函数模板，用仿函数对象将内置类型进行转化，并且对于不能转化为整形的类型，可以用特化来支持。
代码如下：
template<class K>
class ToInt
{
public:
size_t operator()(const K& key)
{
return (size_t)(key);
}
};
除了内置类型，字符串（string）作为键值存储在哈希表中的场景较多，我们实现一个特化版本支持字符串转换为整形。
传统的字符串转整形可以将所有字符的ASCII值相加，但这种方法转换出的整形值可能重复率较高（例如"abc"和"acb"），更容易导致冲突。所以这里我们使用BKDR哈希的思路：每一个字符累加之后，总累加值乘以一个素数（通常是131或31），这样就能对每个字符进行加权。最后的累加值即为转化后的整形值。
注意：当字符串过长时，多次相乘可能会导致溢出，但无需考虑溢出问题，因为我们只要确定能得到唯一的整形值即可。
代码如下：
template<>
class ToInt<string>
{
public:
size_t operator()(const string& s)
{
size_t ret = 0;
for (auto& c : s)
{
ret += c;
ret *= 131;
}
return ret;
}
};
初始大小与扩容策略
使用除留余数法时，为了降低哈希冲突的概率，哈希表的大小（也就是除数M）的选择十分重要，应取不太接近2的整数次幂的一个素数。那么应该如何设置哈希表的初始大小及其扩容后的大小呢？这里我们直接采用SGI STL哈希表源码中的大小设置策略：
inline size_t __stl_next_prime(size_t n)
{
static const int __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
};
const size_t* first = __stl_prime_list;
const size_t* last = __stl_prime_list + __stl_num_primes;
const size_t* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
可以看到，函数创建了一个大小为28的数组，其中的数据即是哈希表每次扩容的大小（53、97、193...以此类推）。函数接收一个参数n，并返回数组中第一个不小于n的元素。而第一个元素53就可以作为我们哈希表的初始大小，接下来实现构造函数时调用该函数即可。
哈希表结构定义
接下来是线性探测法哈希表及其数据元素的结构定义：
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 ToInteger = ToInt<K>>
class HashTable
{
public:
private:
vector<HashData<K, V>> _tables;
size_t _n = 0;
ToInteger _toi;
};
结构定义当中，我们使用了vector用于存储数据，其中元素是一个HashData，HashData包含一个键值对和状态表示（空、存在和已删除）。另外成员n和toi分别用于计算装填因子和整形转化。
构造函数
构造函数当中，我们只需要设置哈希表的初始大小。代码如下：
HashTable()
{
_tables.resize(__stl_next_prime(1));
}
传入参数1，则函数__stl_next_prime返回不小于1的第一个数组元素，也就是53，然后用它调整vector的大小。
析构函数
析构函数不需要我们显式实现，编译器默认生成的析构函数会调用vector的析构，进行数据销毁。
哈希表的插入
哈希表插入的大致过程如下：
1. 首先判断表中是否已有相同键值元素，若有则插入失败（不允许键值重复）。
2. 判断装填因子的值是否过大（这里我们判断是否超过0.7），若过大，哈希表需要扩容。
3. 根据哈希函数进行插入，并处理冲突。
需要注意的是：扩容之后，哈希表的大小（即除数M）会发生变化，之后进行插入或查找操作时，根据新的M进行插入/查找原有元素就会出现问题。所以当哈希表扩容之后，需要将其中的所有元素都拿出来重新根据哈希函数插入在哈希表当中，使其符合新哈希表的除数M。（数据重排）
代码实现：
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
if ((double)_n / (double)_tables.size() >= 0.7)
{
size_t newSize = __stl_next_prime(_tables.size() + 1);
HashTable<K, V, ToInteger> newHT;
newHT._tables.resize(newSize);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
size_t hash0 = _toi(kv.first) % _tables.size();
size_t i = 1;
size_t hashi = hash0;
while(_tables[hashi]._state == EXIST)
{
hashi = (hash0 + i) % _tables.size();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
_n++;
return true;
}
可以看到，在进行扩容时，我们巧妙地创建了一个新的哈希表，并调用Insert方法本身进行数据的重新插入，减少了代码冗余。
哈希表的查找
查找时的逻辑与插入过程大体相同，同样使用哈希函数求出索引值，然后用线性探测法进行查找（注意按键查找）。代码如下：
HashData<K, V>* Find(const K& key)
{
size_t hash0 = _toi(key) % _tables.size();
size_t i = 1;
size_t hashi = hash0;
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;
}
这里需要注意：由于线性探测法一定会使得冲突的数据在表中连续排列，所以我们查找时，如果在线性探测的过程中出现了空位，说明一定查找失败，就无需遍历整个哈希表了。
哈希表的删除
删除的大致过程也很简单（注意按键删除）：
如果表中不存在该元素，则删除失败。
如果存在该元素，直接将元素状态修改为DELETE，然后调整已有元素个数即可。
代码如下：
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = DELETE;
_n--;
return true;
}
}
总代码
哈希表线性探测版本的全部代码如下：
#include <iostream>
#include <utility>
#include <vector>
#include <string>
using namespace std;
template<class K>
class ToInt
{
public:
size_t operator()(const K& key)
{
return (size_t)(key);
}
};
template<>
class ToInt<string>
{
public:
size_t operator()(const string& s)
{
size_t ret = 0;
for (auto& c : s)
{
ret += c;
ret *= 131;
}
return ret;
}
};
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 ToInteger = ToInt<K>>
class HashTable
{
public:
HashTable()
{
_tables.resize(__stl_next_prime(1));
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
if ((double)_n / (double)_tables.size() >= 0.7)
{
size_t newSize = __stl_next_prime(_tables.size() + 1);
HashTable<K, V, ToInteger> newHT;
newHT._tables.resize(newSize);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHT.Insert(_tables[i]._kv);
}
}
_tables.swap(newHT._tables);
}
size_t hash0 = _toi(kv.first) % _tables.size();
size_t i = 1;
size_t hashi = hash0;
while(_tables[hashi]._state == EXIST)
{
hashi = (hash0 + i) % _tables.size();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = EXIST;
_n++;
return true;
}
HashData<K, V>* Find(const K& key)
{
size_t hash0 = _toi(key) % _tables.size();
size_t i = 1;
size_t hashi = hash0;
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;
}
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = DELETE;
_n--;
return true;
}
}
private:
inline size_t __stl_next_prime(size_t n)
{
static const int __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
};
const size_t* first = __stl_prime_list;
const size_t* last = __stl_prime_list + __stl_num_primes;
const size_t* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
vector<HashData<K, V>> _tables;
size_t _n = 0;
ToInteger _toi;
};
2. 链地址法实现
整形转化支持、大小设置
对于进行整形转化的仿函数和哈希表的初始大小设置，我们继续沿用之前线性探测法的实现。
template<class K>
class ToInt
{
public:
size_t operator()(const K& key)
{
return (size_t)(key);
}
};
template<>
class ToInt<string>
{
public:
size_t operator()(const string& s)
{
size_t ret = 0;
for (auto& c : s)
{
ret += c;
ret *= 131;
}
return ret;
}
};
inline size_t __stl_next_prime(size_t n)
{
static const int __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
};
const size_t* first = __stl_prime_list;
const size_t* last = __stl_prime_list + __stl_num_primes;
const size_t* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
哈希表结构定义
接下来是链地址法哈希表的结构定义：
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 ToInteger = ToInt<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
private:
vector<Node*> _tables;
size_t _n = 0;
ToInteger _toi;
};
这里我们创建了一个指针数组，每一个指针都用于维护一个链表。其次，成员n与toi的作用和线性探测实现中相同。由于链地址法中的数据都是通过链表存储，所以这里就无需对每个元素进行状态表示。
构造函数
构造函数的实现与线性探测法相同，注意初始化时将表中的所有指针制为空。
代码如下：
HashTable()
{
_tables.resize(__stl_next_prime(1), nullptr);
}
析构函数
与线性探测法实现不同，由于每个哈希桶都维护一个单链表，所以析构时需要我们手动释放这些链表所占内存。 遍历哈希表，逐个销毁即可。代码如下：
~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. 判断装填因子是否大于1，如果大于1就需要扩容。（扩容仍需注意数据重排）
3. 通过哈希函数找到对应的哈希桶，进行插入。
需要注意两点：
1. 这里的插入过程涉及单链表的插入，为了提高效率，我们将使用头插法。
2. 由于数据存储在链表节点当中，扩容之后，进行数据重排时释放节点再创建节点就过于麻烦，所以我们遍历所有链表，将节点连接到新的哈希表中对应位置即可。
代码实现：
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
if (_n >= _tables.size())
{
size_t newSize = __stl_next_prime(_tables.size() + 1);
vector<Node*> newV(newSize, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = _toi(cur->_kv.first) % newV.size();
cur->_next = newV[hashi];
newV[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newV);
}
size_t hashi = _toi(kv.first) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
_n++;
return true;
}
可以看到，与刚才的线性探测实现不同，这里我们在扩容时创建的是一个vector，相比直接创建HashTable再调用Insert方法，能够有效地控制数据重排时节点之间的连接。
对于不同的结构实现，同一种操作所使用的方法也会有所不同，因此在实际场景中，我们应抓住问题本质，灵活运用各种方法，而非死抓一种应对措施。
哈希表的查找
相比线性探测法，链地址法的查找中，我们只需要**确定索引值，然后顺着链表直接查找即可**，总体过程相对简洁。代码实现如下：
Node* Find(const K& key)
{
size_t hashi = _toi(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)
{
size_t hashi = _toi(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
_n--;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
总代码
链地址法实现哈希表的全部代码如下：
#include <iostream>
#include <utility>
#include <vector>
#include <string>
using namespace std;
template<class K>
class ToInt
{
public:
size_t operator()(const K& key)
{
return (size_t)(key);
}
};
template<>
class ToInt<string>
{
public:
size_t operator()(const string& s)
{
size_t ret = 0;
for (auto& c : s)
{
ret += c;
ret *= 131;
}
return ret;
}
};
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 ToInteger = ToInt<K>>
class HashTable
{
typedef HashNode<K, V> Node;
public:
HashTable()
{
_tables.resize(__stl_next_prime(1), nullptr);
}
~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;
}
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
if (_n >= _tables.size())
{
size_t newSize = __stl_next_prime(_tables.size() + 1);
vector<Node*> newV(newSize, nullptr);
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = _toi(cur->_kv.first) % newV.size();
cur->_next = newV[hashi];
newV[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newV);
}
size_t hashi = _toi(kv.first) % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
_n++;
return true;
}
Node* Find(const K& key)
{
size_t hashi = _toi(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)
{
size_t hashi = _toi(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
_n--;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
inline size_t __stl_next_prime(size_t n)
{
static const int __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
};
const size_t* first = __stl_prime_list;
const size_t* last = __stl_prime_list + __stl_num_primes;
const size_t* pos = lower_bound(first, last, n);
return pos == last ? *(last - 1) : *pos;
}
vector<Node*> _tables;
size_t _n = 0;
ToInteger _toi;
};
总结
哈希表是一种基于哈希函数的高效数据结构，其通过数据映射，支持 O(1) 级别的查找、插入和删除操作。哈希表有多种实现方法，我们实现了开放地址法（线性探测）和链地址法两种。开放地址法适用于低负载、节省空间，但处理冲突时可能导致探测成本增加；链地址法适用于高负载，扩展性更强，但需额外存储指针。合理选择哈希函数和冲突解决策略是优化哈希表性能的关键。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤
