Cpp::哈希表的两种模拟实现方式(27)
文章目录
- 前言
- 一、闭散列
- 大思路
- 基本构架
- 插入数据
- 扩容逻辑
- 扩容换表
- 查找元素
- 删除数据
- 除留余数法出现类型问题
- 简单类型做key
- string类型做key
- 二、开散列
- 大思路
- 插入数据
- 析构函数
- 哈希扩容
- 删除数据
- 哈希查找
- 总结
前言
哈喽大家好！承接上文，今天我们再来模拟实现一下哈希表
它的实现方式一共有两种！
一、闭散列
大思路
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去
有点强盗逻辑，既然我的位置没了，那就去抢别人的位置！
基本构架
enum State
{
EXIST,
EMPTY,
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>> _tables;
size_t _n = 0;
};
_ size 一般用于序列式容器中表示有效元素个数，在关联式容器中命名约定一般规定 _n 作为记录有效元素个数
插入数据
在插入过程，元素需要通过除留余数法找到对应位置进行插入，期间可能会出现哈希冲突的问题，我们需要以该位置向后寻找状态标记为空的位置进行插入
在向后寻找位置途中可能存在越界情况，这里采用处理循环队列方式进行取模操作，保证数据在合法范围进行查找。这里存在一个大前提，空间是充足的，不然找半天都找不到位置
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))
return false;
// 扩容
if (_n * 10 / _tables.size() >= 7)
{
//vector<HashData<K, V>> newTables(_tables.size() * 2);
遍历旧表，将所有数据映射到新表
...
//_tables.swap(newTables);
HashTable<K, V, Hash> newHT;
newHT._tables.resize(_tables.size() * 2);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newHT.Insert(_tables[i]._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;
}
扩容逻辑
上点中我们代码中有个扩容模块
负载因子越小，冲突率越低，效率就越高，空间利用率就越低
当然，为了防止出现类型问题，我们采用乘个十的方法来解决这类问题
同时，我们可以思考一个问题，就是我们的 n 到底是除以 size() 还是 capacity() ，选择后者有可能会导致越界访问，所以我们可以先在构造函数中为 _tables 开辟空间，同时防止了 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]._state == EXIST
&& _tables[hashi]._kv.first == key)
{
return &_tables[hashi];
}
++hashi;
hashi %= _tables.size();
}
return nullptr;
}
其中我们需要注意的是，当删除某个元素时，查找过程中无法判断找到数据及其是否需要继续前进，这时候就需要DELETE标记
删除数据
bool Erase(const K& key)
{
HashData<K, V>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = DELETE;
return true;
}
}
哈希表删除数据是我们遇到最简单的删除逻辑，只需要改变位置状态就可以了
除留余数法出现类型问题
对于 key 进行取模查找，是建立在 key 属于无符号整型类型来考虑的，但是我们设计属于泛型编程，key 需要去适应不同种类型如 string类型、自定义类型、负数
简单类型做key
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
string类型做key
这时候我们可能会想，能不能把字母转成 ASCII 码值，但是事实上，这种方法可能会出错，且也可能会发生哈希冲突，因为不同字符组合可能具有相同的 ASCII 码总和
这个时候，我们就可以进行模板特化
template<>
struct HashFunc<string>
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (const auto& e : key)
{
hash *= 31;
hash += e;
}
return hash;
二、开散列
大思路
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中
开散列中每个桶中放的都是发生哈希冲突的元素，并没有顺序之分
插入数据
Node* newnode = new Node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
其实头插尾插都行，只不过是尾插有点麻烦，头插比较简单轻松
析构函数
这里涉及堆上空间资源的开辟，一般需要涉及析构函数进行资源处理
~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;
}
}
哈希扩容
到这里，我们可以复用闭散列的扩容方案，只是那种方案如果存在一万个节点，意味着需要复制一万个节点又要释放一万个节点，显得很浪费
这时候我们就可以采取一种新的方式了！
先保存 cur 的下一个节点 next，然后得到新表的位置，再把 cur 所指向的节点链到新的表上，这就是我们的思路
删除数据
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 == nullptr)
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
一种是删除第一个节点，另一种是删除其他节点prev->_next = cur->_next
哈希查找
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;
}
总结
本节其实没有什么特别难的地方，但是但是，下一篇的 unordered 封装就不尽然了，请继续加油！