您现在的位置是：首页 >其他 >【C++】“最强查找“哈希表的底层实现网站首页其他
【C++】“最强查找“哈希表的底层实现
哈希表的查找的时间复杂度是O（1）~
前言
哈希概念：
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快 。
一、哈希冲突和哈希函数
哈希冲突：
对于我们上面所插入的数，如果我们插入了44会发生什么呢？44%10==4，但是4这个位置已经被占了，这就是哈希冲突。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
哈希函数：
数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。
哈希冲突的解决：
线性探测优点：实现非常简单。
线性探测缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。如何缓解呢？用二次探测的方法：
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
开散列与闭散列比较：
二、哈希表底层实现
1.开放地址法
首先我们将代码放到一个命名空间内防止后面发生命名冲突，然后用一个结构体保存每个位置存储什么样的数据，这里我们就以kv结构为例：
enum State
{
EMPTY,
DELETE,
EXIST
};
template <class K, class V>
struct HashDate
{
pair<K, V> _kv;
State _state = EMPTY;
};我们定义的枚举类型有代表空，删除，存在3种状态，至于为什么要用状态表示而不是直接将哈希表中的数据删除想必大家是有答案的，因为我们的开放地址法解决冲突的时候，如果此位置已经有数就需要往后查找，如果我们将这个位置删除那么还怎么查找后面的数呢。我们在初始化HashDate的时候要将刚开始的每个位置置为EMPTY状态，因为我们后面都是根据状态来插入删除的。
template <class K, class V>
class HashTable
{
public:
private:
vector<HashDate<K, V>> _tables;
size_t _n = 0; //记录插入了多少个元素
};哈希表的主体我们就直接用vector了，因为vector的功能很完全如果我们自己实现会比较麻烦。每个向量中存放HashDate类型的数据（记得加模板参数），然后我们用一个变量来记录向表中插入了多少数据，这里可不能直接用向量的size()，因为我们是会有删除状态，如果用size()删除状态也会被记录。
bool insert(const pair<K, V>& kv)
{
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;
}上面是哈希表插入的代码，我们先不考虑扩容的问题，在这里我们计算插入元素映射的位置一定不能%capacity(),我们画个图为例：
我们要使用vector一定会使用到[]操作符的，但是这个操作符只能访问size()的值，超出size()就会触发报错，比如一个数组size() = 10,capacity() = 20,我们可以访问【5】但是不能访问【15】，所以我们计算映射的位置一定是%size().然后我们要判断映射的位置是否已经有元素了，如果有元素了就需要向后探测找空位置，我们用index的目的是以后改二次探测会非常简单，在向后寻找的过程中为了防止index越界所以每次都%哈希表的实际容量，找到位置后将键值对插入并且把状态改为存在，然后让计数器加加即可。下面我们考虑扩容的问题，扩容之前我们需要知道一个概念：
bool insert(const pair<K, V>& kv)
{
if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
{
//扩容
size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
HashTable<K, V> newtable;
newtable._tables.resize(newsize);
for (auto& e : _tables)
{
if (e._state == EXIST)
{
newtable.insert(e._kv);
}
}
_tables.swap(newtable._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;
}也就是说我们要看载荷因子是多少，载荷因子是表中实际插入的数除表的实际大小（要记住实际大小是size()）,但是由于计算机中两个整形怎么除都不会变成小数，所以两边乘10就解决了这个问题，当然也可以强转为double去除。为了防止除0问题所以我们判断哈希表是否为0或者载荷因子是否大于0.7.新空间每次按原来空间的两倍扩容，这里大家思考一下可以直接在原来的数组扩容吗？答案是不行的，因为原来映射的位置经过扩容会发生改变，比如原先size()为10，11这个数会放在1这个位置，但是扩容到size()=20后，11这个数因为放在11的位置才对。为了防止这个问题我们直接重新创建一个哈希表对象，给这个哈希表对象中的表扩容为新空间大小，要注意的是：只有resize()才会改变size()的大小，reserve只会改变capacity，我们实际用的size()所以必须要让size()改变。开好空间后我们遍历旧表的数据看每个位置是否有存在的元素，有的话就插入到新表（这里调用inser是不会扩容的，因为是新表调用的，新表的空间是开好的，只会重新映射位置进行插入），插入结束后直接让原来的向量和新表中的向量交换即可。
HashDate<K, V>* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
size_t hashi = key % _tables.size();
size_t index = hashi;
size_t i = 1;
while (_tables[index]._state != EMPTY)
{
if (_tables[index]._state == EXIST
&& _tables[index]._kv.first == key)
{
return &_tables[index];
}
index = hashi + i;
index %= _tables.size();
if (index == hashi)
{
break;
}
++i;
}
return nullptr;
}Find接口实现起来就比较简单了，当表为空我们就返回空即可。然后计算映射的位置直接去这个位置查找元素是否存在，要注意我们查找的时候只要这个位置不为空我们就进行查找，因为这个位置有可能是删除状态，删除状态的话需要向这个位置后面去寻找，所以条件是不为空，进入循环后我们要判断当前元素是否和我们查找的元素的key相等并且这个位置还必须是存在状态，只有满足这个条件我们才返回该位置的数据（这里我们用的引用，而返回值是指针类型，但是我们在将引用的时候说过，引用就是指针实现的，所以这里返回值没有问题），当我们查找一圈又回到一开始的映射位置的时候，这个时候肯定找不到了直接退出循环即可。
bool eraser(const K& key)
{
HashDate<K, V>* tmp = Find(key);
if (tmp)
{
tmp->_state = DELETE;
--_n;
return true;
}
else
{
return false;
}
}删除接口我们直接用Find函数去查找，如果找到了就将当前位置的状态置为删除，然后将计数器减减返回true。我们在insert的时候也可以用Find判断一下，如果要插入的值已经存在了我们就不插入了。
以上就是开放地址法的三个重要接口下面我们测试一下：
void TeshHashTable1()
{
int a[] = { 3,33,2,13,5,12,102 };
HashTable<int, int> ht;
for (auto& e : a)
{
ht.insert(make_pair(e, e));
}
ht.insert(make_pair(16, 16));
auto t = ht.Find(13);
if (t)
{
cout << "13在" << endl;
}
else
{
cout << "13不在" << endl;
}
ht.eraser(13);
t = ht.Find(13);
if (t)
{
cout << "13在" << endl;
}
else
{
cout << "13不在" << endl;
}
}
没问题，我们再看看扩容时是否成功映射：
运行结果没毛病，下面我们实现链地址法。
2.链地址法（哈希桶）
同样我们将代码放到命名空间中，然后我们要用struct实现节点，这个节点将来会挂在哈希表的某个位置。
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)
{
}
};节点中只需要有个next指针指向其他节点，然后一个键值对就搞定了，由于是节点我们肯定是需要通过开空间new出来的，所以我们就写个构造函数，通过pair来构造这个节点即可。
template <class K, class V>
class HashTable
{
typedef HashNode<K, V> Node;
public:
private:
vector<Node*> _tables;
size_t _n = 0;
};主体同样用vector，里面存放节点的指针即可，同样还需要有一个计数器记录插入了多少元素。
bool insert(const pair<K, V>& kv)
{
size_t hashi = kv.first % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}同样我们先不考虑扩容的问题，直接算出映射的位置，然后创建新节点，然后头插就可以了，让新节点的next链接原先表中的头结点，然后再让新节点变成映射位置的头结点这样就完成了头插，头插后让计数器++即可，下面来考虑扩容的问题：
bool insert(const pair<K, V>& kv)
{
if (_n == _tables.size())
{
//扩容
size_t newsize = _tables.size() == 0 ? 10 : 2 * _tables.size();
vector<Node*> newtable(newsize, nullptr);
for (auto& cur : _tables)
{
while (cur)
{
Node* next = cur->_next;
size_t hashi = cur->_kv.first % newtable.size();
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
}
_tables.swap(newtable);
}
size_t hashi = kv.first % _tables.size();
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}哈希桶的扩容只需要当每个桶都有元素了再扩容就好了，这样就能保证每个桶中的数据都是差不多的。当插入的元素除以实际元素也就是载荷因子为1时扩容，对于哈希桶的扩容我们也可以像上面开放地址法那样开一个新的哈希表，但是这样效率太低了，要知道哈希桶中链接的节点重新插入然后插入成功后还要一个个释放空间这样效率太低了，所以我们直接重新开一个vector，然后直接将旧的哈希表中的节点一个个重新映射到vector中，这样当映射完成后我们就不用释放节点的空间了，因为我们使用旧的节点重新映射的，没有新开节点。重新映射也很简单，就是遍历旧的哈希表，当此位置节点不为空时，我们就保存这个节点的下一个节点，然后计算这个节点的新的映射位置（这里计算一定是用新的size()空间去映射，这样才叫重新映射），然后让当前节点链接映射位置的头结点，然后再让当前节点变成映射位置的头结点就完成了头插。插入完成后交换vector即可。
Node* Find(const K& key)
{
if (_tables.size() == 0)
{
return nullptr;
}
size_t hashi = key % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}查找函数同样先看表是否为空，如果为空返回空指针即可。然后我们计算映射位置直接拿到这个位置的头结点，然后从头结点开始去遍历，如果找到要查找的元素就返回当前节点，如果到循环结束还没有找到就返回空指针即可。
bool eraser(const K& key)
{
size_t hashi = key % _tables.size();
Node* cur = _tables[hashi];
Node* prev = nullptr;
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
Node* next = cur->_next;
_tables[hashi] = next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}删除接口首先计算要映射的位置，然后拿到这个位置的头结点，用一个变量去保存前一个节点，当头结点不为空就进入循环，如果没有找到要删除的节点我们就继续遍历，遍历前把当前位置给prev节点去记录前面的位置，当找到要删除节点的时候我们需要判断当前节点是否是头结点，如果是头结点那么直接让头结点的next当头结点，把原先的头结点释放即可。如果要删除的不是头结点，就让前面节点的next链接要删除节点的next即可，然后释放节点即可。
下面我们测试一下代码：
void TeshHashTable2()
{
int a[] = { 3,33,2,13,5,12,1002 };
HashTable<int, int> ht;
for (auto& e : a)
{
ht.insert(make_pair(e, e));
}
ht.insert(make_pair(16, 16));
ht.insert(make_pair(14, 14));
ht.insert(make_pair(15, 15));
ht.insert(make_pair(17, 17));
auto t = ht.Find(13);
if (t)
{
cout << "13在" << endl;
}
else
{
cout << "13不在" << endl;
}
ht.eraser(13);
t = ht.Find(13);
if (t)
{
cout << "13在" << endl;
}
else
{
cout << "13不在" << endl;
}
}
接口没有问题，下面我们看看扩容的问题：
上面是没扩容时候的哈希表，下面我们再看看扩容后的样子：
我们可以看到扩容后所有的值都经过重新映射了，下面我们实现一下析构函数，因为当我们程序结束后vector只会是否释放自己的空间，对于每个位置链表的空间是不会释放的，所有需要我们手动释放：
~HashTable()
{
for (auto& cur : _tables)
{
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
cur = nullptr;
}
}析构的时候我们直接遍历，当这个位置的头结点不为空时我们就保存这个位置的下一个节点，然后将当前节点释放掉再让cur变成刚刚保存的节点重新执行delete操作。当一个桶的数据全部释放后我们就将当前桶的指针置为空即可。
总结
以上就是哈希表的底层实现了，下一篇文章我会将哈希桶进行封装然后变成unordered_map和unordered_set的底层，前面我们也进行了红黑树的封装，这次的封装还红黑树相差不大只不过会比红黑树麻烦一点。
站长推荐
- stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - 【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述
【云原生进阶之容器】第六章容器网络6.6.1--Cilium网络方案概述