【C++】哈希表的实现
哈希是什么
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位
搜索的效率取决于搜索过程中元素的比较次数，因此顺序结构中查找的时间复杂度为O ( N ) O(N)O(N)，平衡树中查找的时间复杂度为树的高度O ( l o g N ) O(logN)O(logN)。
而最理想的搜索方法是，可以不经过任何比较，一次直接从表中得到要搜索的元素，即查找的时间复杂度为O ( 1 ) O(1)O(1)。
如果构造一种存储结构，该结构能够通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时就能通过该函数很快找到该元素。
理解哈希
哈希函数是一将输入（通常是一个大的数据集）映射到固定大小的输出的函数。哈希函数的一个重要特性是，无论输入数据的大小如何，其输出长度都是固定的（如果哈希函数输出长度不固定，将会导致数据分布不均匀或桶的大小不明确，影响哈希表的性能），这使得哈希函数非常有用，因为它可以将大量的数据快速映射到一个较小的范围内。
哈希所用的容器
unordered_map和unordered_set都是C++标准库中的容器，用于存储一组元素。它们的底层实现都是基于哈希表。
unordered_map是一种关联容器，它存储一组键值对（key-value pairs）。每个键都唯一且与一个值相关联。unordered_map使用哈希函数将键映射到特定的存储桶（bucket），并且在桶中存储值。由于使用哈希表实现，unordered_map的插入、查找和删除操作都具有常数平均时间复杂度。
unordered_set是一种集合容器，它存储一组唯一的元素。unordered_set使用哈希函数将元素映射到特定的存储桶，并在桶中存储元素。与unordered_map类似，unordered_set的插入、查找和删除操作也具有常数平均时间复杂度。
unordered_map和unordered_set的区别在于unordered_map存储的是键值对，而unordered_set只存储值。因此，unordered_map可以用来解决需要根据键快速查找对应值的问题，而unordered_set则可以用来快速判断一个值是否存在于集合中。
优点：
- 查询速度快：由于使用哈希表实现，unordered_map和unordered_set的查询操作具有常数平均时间复杂度。
- 高效的插入和删除：插入和删除元素的操作也具有常数平均时间复杂度。
- 灵活性：可以存储不同类型的键和值。
缺点：
- 内存消耗较大：由于需要维护哈希表，unordered_map和unordered_set通常会消耗比较多的内存空间。
- 无序性：元素在容器中的存储位置是无序的，无法保证元素的顺序。
计算key值方法
哈希计算存储关键码的方法有以下几种：
- 直接定址法（常用）：
取关键字的某个线性函数为哈希地址：H a s h ( K e y ) = A ∗ K e y + B
- 思路：将关键码直接作为地址来存储，即 H(key) = key。适用于关键码分布比较均匀的情况。
- 区别：直接定址法不需要计算哈希值，直接使用关键码本身作为地址，因此查找效率很高。
- 优点：查找操作的平均时间复杂度为O(1)，即常数时间复杂度。
- 缺点：当关键码的分布不均匀时，会导致冲突（多个关键码映射到同一个地址），需要解决冲突的方法。
- 数字分析法：
- 思路：通过对关键码进行分析，选取其中具有代表性的数字作为哈希地址。例如，对身份证号码进行哈希存储时，可以选取其中的年份作为地址。
- 区别：数字分析法需要对关键码进行分析，并根据分析结果选择适合的数字作为地址，适用于某些特定的数据集。
- 优点：对于符合特定规律的数据集，数字分析法可以获得较好的哈希效果。
- 缺点：对于没有明显规律的数据集，数字分析法可能无法获得较好的哈希效果。
- 平方取中法：
- 思路：将关键码平方后，取中间的几位作为哈希地址。例如，对关键码 key 进行平方后，取中间的 m 位作为地址 H(key)。
- 区别：平方取中法通过平方运算对关键码进行转换，然后取中间的几位作为哈希地址。
- 优点：相对于直接定址法和数字分析法，平方取中法能够更加均匀地分布关键码，减少冲突的概率。
- 缺点：平方取中法需要进行额外的平方运算和位数操作，相比直接定址法和数字分析法，会增加一定的计算成本。
- 除留余数法（常用）：
- 思路：将关键码除以某个不大于哈希表大小的数，再取余数作为哈希地址。即 H(key) = key%p，其中 p 是一个不大于哈希表大小的素数。
- 区别：除留余数法通过除法和取余操作来计算哈希地址。
- 优点：除留余数法相对简单，计算速度快。
- 缺点：如果选取的素数 p 与关键码的特征相关，则可能导致冲突较多。
哈希的插入和查找
数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小
当我们在再次插入一个数值位
11的时候，这时发现，如果我们已同样的方法进行插入的时候，就会与 1 下标位置的元素起到冲突。这时我们就要解决冲突问题，冲突问题在下方解决
- 插入元素
根据待插入元的关键码（在下边将介绍），以此函数计算出该元素的存储位置并按此位置进行存放
//插入两种方法
//bool Insert(const T& data)
pair<iterator,bool> Insert(const T& data)
{
KeyOfT kot;//将不同对象进行提取
iterator it = Find(kot(data));
if (it != end())
{
return make_pair(it,false);
}
Hash hash;
//进行扩容
if (_n == _tables.size())
{
//不调用自定义析构的方法
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newtables(newsize, nullptr);
//for (Node*& cur : _tables)
for(auto& cur : _tables)
{
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.swap(newtables);
}
size_t hashi = hash(kot(data)) % _tables.size();
//头插
Node* newnode = new Node(data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
_n++;
return make_pair(iterator(newnode,this),true);
}
- 查找元素
对元素的关键码进行同样的计算，把求得的函数值当作元素的存储位置，在结构中按此位置去元素比较，若关键码相等，则搜索成功
//查找
iterator Find(const K& key)
{
if (_tables.size() == 0)
{
return end();
}
Hash hash;//根据类型不同来计算他的整体key值
KeyOfT kot;//将不同对象进行提取查找对应值
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur,this);
}
else
{
cur = cur->_next;
}
}
return end();
}
解决哈希冲突
数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小
当我们在再次插入一个数值位
11的时候，这时发现，如果我们已同样的方法进行插入的时候，就会与 1 下标位置的元素起到冲突。这时我们就要解决冲突问题
解决哈希冲突两种常见的方法是：闭散列和开散列
闭散列也叫开放寻址法
开放寻址法（Open Addressing）：在每个哈希桶中直接存储键值对，当发生冲突时，通过一定的探索规则找到下一个可用的桶。常见的探索规则有线性探测、二次探测。
当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有
空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
开放寻址法不需要额外的内存来存储指针，且具有较好的缓存友好性，但当负载因子较高时，可能会导致连续冲突的概率增加，进而影响到性能。
线性探测
删除元素问题
采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。
二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：
Hi=(H0+i ^2)%m ( i = 1 , 2 , 3 , . . . )
H0：通过哈希函数对元素的关键码进行计算得到的位置。
H i：冲突元素通过二次探测后得到的存放位置。
m：表的大小。
采用二次探测为产生哈希冲突的数据寻找下一个位置，相比线性探测而言，采用二次探测的哈希表中元素的分布会相对稀疏一些，不容易导致数据堆积。
和线性探测一样，采用二次探测也需要关注哈希表的负载因子，例如，采用二次探测将上述数据插入到表长为20的哈希表，产生冲突的次数也会有所减少：
开散列
在每个哈希桶中使用链表或其他数据结构存储冲突的键值对。当发生冲突时，新的键值对可以简单地添加到链表的末尾。这种方法简单易行，适用于频繁发生冲突的情况。链地址法的缺点是需要额外的内存来存储链表的指针，同时在处理大量冲突时，链表的遍历效率可能较低。
例如，我们用除留余数法将序列{1, 6, 15, 60, 88, 7, 40, 5, 10}插入到表长为10的哈希表中，当发生哈希冲突时我们采用开散列的形式，将哈希地址相同的元素都链接到同一个哈希桶下，插入过程如下：
闭散列解决哈希冲突，采用的是一种报复的方式，“我的位置被占用了我就去占用其他位置”。而开散列解决哈希冲突，采用的是一种乐观的方式，“虽然我的位置被占用了，但是没关系，我可以‘挂’在这个位置下面”。
与闭散列不同的是，这种将相同哈希地址的元素通过单链表链接起来，然后将链表的头结点存储在哈希表中的方式，不会影响与自己哈希地址不同的元素的增删查改的效率，因此开散列的负载因子相比闭散列而言，可以稍微大一点。
- 闭散列的开放定址法，负载因子不能超过1，一般建议控制在[0.0, 0.7]之间。
- 开散列的哈希桶，负载因子可以超过1，一般建议控制在[0.0, 1.0]之间。
在实际中，开散列的哈希桶结构比闭散列更实用，主要原因有两点
- 哈希桶的负载因子可以更大，空间利用率高。
- 哈希桶在极端情况下还有可用的解决方案。
哈希桶的极端情况就是，所有元素全部产生冲突，最终都放到了同一个哈希桶中，此时该哈希表增删查改的效率就退化成了O ( N )
哈希闭散列实现
闭散列结构
我们用枚举来表示它当前的状态
//枚举：标识每个位置的状态
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:
//...
private:
vector<HashData<K, V>> _table; //哈希表
size_t _n = 0; //哈希表中的有效元素个数
};
闭散列结构插入
当进行插入的时候，我们需要注意它的扩容问题，在这里我们的负载因子一般控制在 0 ~ 0.7 之间，如果超过了这个范围，就需要扩容。
当扩容时，我们不是原地扩，而是先设置一个新的容器，然后放大原先的两倍，再将所有数据挪过去，最后交换数组就可以了
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
// 负载因子超过0.7就扩容
//if ((double)_n / (double)_tables.size() >= 0.7)
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
HashTable<K, V> newht;
newht._tables.resize(newsize);
// 遍历旧表，重新映射到新表
for (auto& data : _tables)
{
if (data._state == EXIST)
{
newht.Insert(data._kv);
}
}
_tables.swap(newht._tables);
}
size_t hashi = kv.first % _tables.size();
// 线性探测
size_t i = 1;
size_t index = hashi;
while (_tables[index]._state == EXIST)
{
index = hashi + i;
index %= _tables.size();
++i;
}
_tables[index]._kv = kv;
_tables[index]._state = EXIST;
_n++;
return true;
}
闭散列查找
在进行查找时，首先需要用哈希函数算出对应key值，然后剩下我们的工作只是遍历元素，查找对应的元素值。
只需要看当前状态是否为存在或者删除，当遇到空时，说明所找元素不存在
HashData<K, V>* Find(const K& key)
{
if (_tables.size() == 0)
{
return false;
}
size_t hashi = key % _tables.size();
// 线性探测
size_t i = 1;
size_t index = hashi;
while (_tables[index]._state != EMPTY)
{
if (_tables[index]._state == EXIST
&& _tables[index]._kv.first == key)
{
return &_tables[index];
}
index = hashi + i;
index %= _tables.size();
++i;
// 如果已经查找一圈，那么说明全是存在+删除
if (index == hashi)
{
break;
}
}
return nullptr;
}
闭散列删除
删除哈希表中的元素非常简单，我们只需要进行伪删除即可，也就是将待删除元素所在位置的状态设置为DELETE。
在哈希表中删除数据的步骤如下：
- 查看哈希表中是否存在该键值的键值对，若不存在则删除失败。
- 若存在，则将该键值对所在位置的状态改为DELETE即可。
- 哈希表中的有效元素个数减一。
注意： 虽然删除元素时没有将该位置的数据清0，只是将该元素所在状态设为了DELETE，但是并不会造成空间的浪费，因为我们在插入数据时是可以将数据插入到状态为DELETE的位置的，此时插入的数据就会把该数据覆盖。
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
else
{
return false;
}
}
哈希开散列实现（链表式）
开散列结构
在开散列的哈希表中，哈希表的每个位置存储的实际上是某个单链表的头结点，即每个哈希桶中存储的数据实际上是一个结点类型，该结点类型除了存储所给数据之外，还需要存储一个结点指针用于指向下一个结点。
//每个哈希桶中存储数据的结构
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 HashTable
{
public:
//...
private:
//typedef HashNode<K, V> Node;
vector<Node*> _table; //哈希表
size_t _n = 0; //哈希表中的有效元素个数
};
开散列结构插入
- 若哈希表的负载因子已经等于1了，则先创建一个新的哈希表，该哈希表的大小为原哈希表的两倍，之后遍历原哈希表，将原哈希表中的数据插入到新哈希表，最后将原哈希表与新哈希表交换即可。
- 重点： 在将原哈希表的数据插入到新哈希表的过程中，不要通过复用插入函数将原哈希表中的数据插入到新哈希表，因为在这个过程中我们需要创建相同数据的结点插入到新哈希表，在插入完毕后还需要将原哈希表中的结点进行释放，多此一举。
实际上，我们只需要遍历原哈希表的每个哈希桶，通过哈希函数将每个哈希桶中的结点重新找到对应位置插入到新哈希表即可，不用进行结点的创建与释放。
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
{
return false;
}
Hash hash;
// 负载因因子==1时扩容
if (_n == _tables.size())
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
vector<Node*> newtables(newsize, nullptr);
//for (Node*& cur : _tables)
for (auto& cur : _tables)
{
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.swap(newtables);
}
size_t hashi = hash(kv.first) % _tables.size();
// 头插
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
开散列结构查找
在哈希表中查找数据的步骤如下：
- 先判断哈希表的大小是否为0，若为0则查找失败。
- 通过哈希函数计算出对应的哈希地址。
- 通过哈希地址找到对应的哈希桶中的单链表，遍历单链表进行查找即可。
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)
{
Hash hash;
size_t hashi = hash(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;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}