目录
前言
Part1. unordered_map和set
Part1.1. 有序性差异
Part1.2. 迭代器特性
Part1.3. Key约束
Part2. 哈希表核心原理
Part2.1. 两种基础映射方案
Part2.1.1. 直接定址法
Part2.1.2. 哈希函数映射法
Part2.2. 哈希冲突定义
Part2.3. 负载因子
Part2.4. 哈希冲突解决方案
Part2.4.1. 开放寻址法
Part2.4.2. 线性探测
Part2.4.3. 二次探测
Part2.4.4. Java哈希表
Part2.4.5. 上述缺陷与修正
Part2.4.6. 哈希桶
Part2.5. 哈希表扩容机制
Part2.5.1. 扩容触发条件
Part3. 哈希表实现
Part3.1. 基础结构定义
Part3.2. 插入逻辑
Part3.3. 查找
Part3.4. 删除
Part4. 结语
前言
哈希表无论是在应用还是在算法中都有非常多的体现，接下来，跟随小编的视角来了解一下哈希表和他的实现吧。
let's go!!!!!!!!
Part1. unordered_map和set
C++ STL中，std::map/std::set依托红黑树实现，元素有序，增删查时间复杂度稳定为O(logN)。unordered_map与unordered_set以哈希表（散列表）为底层结构，理想情况下读写效率可达O(1)。（虽然两者时间复杂度为量级差距，但是实际两者相差不大。）
Part1.1. 有序性差异
<1> map/set：元素自动按照Key排序，底层红黑树；
<2> unordered系列：元素无序存储，依靠哈希映射确定存储位置，查询速度更快。
Part1.2. 迭代器特性
unordered容器的迭代器为单向迭代器，仅支持++自增，不支持--反向遍历。
Part1.3. Key约束
哈希key只支持整形，自定义类型、字符串等类型需要手动提供哈希函数，完成类型到整数的转换。
Part2. 哈希表核心原理
哈希表本质：建立关键字Key与数组存储下标之间的映射关系，通过哈希函数直接定位存储位置，跳过遍历查找步骤。
Part2.1. 两种基础映射方案
Part2.1.1. 直接定址法
直接将Key作为数组下标，构建连续内存映射。适用于Key取值范围集中、区间很小的数据集，范围过大将造成数组空间严重浪费。
Part2.1.2. 哈希函数映射法
<1> 开辟长度为M的数组，通过哈希函数将任意Key映射到[0, M-1]的下标区间，用有限空间承载大范围的Key。
<2> 经典基础哈希函数：除留余数法。 <3> 公式：hash(key) = key% M。
Part2.2. 哈希冲突定义
<1> 不同的Key经过哈希计算后，映射到同一个数组下标，该现象称为哈希冲突。
<2> 示例：3\%200 与 203\%200 结果均为3，两个键会争夺同一个位置。
Part2.3. 负载因子
<1> 负载因子为 N/M。（N为有效元素个数，M为哈希表容量）
<2> 负载因子代表哈希表空间占用率；
<3> 负载因子数值越大，哈希冲突概率急剧升高；
<4> 负载因子越小，空间利用率越低。
Part2.4. 哈希冲突解决方案
Part2.4.1. 开放寻址法
核心思路：下标已被占用时，按照固定规则向后顺延寻找空位完成插入。
Part2.4.2. 线性探测
<1> 冲突后依次探查：（hash(key)+1）%M、(hash(key)+2)%M……，逐个向后寻找空位。
<2> 缺陷：极易产生数据堆积，连续冲突会让查找效率快速退化。
Part2.4.3. 二次探测
<1> 采用平方偏移规则进行探查，标准公式：
hash(key)=(hash(key)+i*i*q）%M（i=1,2,3······，q在1.-1之间交替）
<2> 这样会使数据的分布更加散，不易发生堆积
Part2.4.4. Java哈希表
hash0=key&(1<<(n-1)) <1>，hash(key)=hash0^(key>>(32-n)) <2>，2的n次方为M。
<1> 由于%运算效率不高，于是用这个来。
<2> 将Key高32-n位右移后与原Key异或，让高位数据参与哈希运算，降低低位重复带来的冲突概率。
Part2.4.5. 上述缺陷与修正
解决方案：为每个哈希节点设置三种状态标记：
<1> exist：节点存在有效数据。
<2> empty：节点为空，从未使用。
<3> delete：数据已删除，节点保留占位。
查找规则：哈希下标命中后，持续向后遍历，直到遇到empty节点才终止查找；delete节点仅跳过、不终止遍历。
Part2.4.6. 哈希桶
开放寻址法依然存在空间浪费、探测效率低下问题，C++ STL采用哈希桶结构：
<1> 哈希表每个下标位置不再是单一节点，而是挂载一条链表。
<2> 冲突元素直接挂载到对应下标的链表尾部。
<3> 查找时先哈希定位桶下标，再遍历桶内链表完成精准匹配。
Part2.5. 哈希表扩容机制
Part2.5.1. 扩容触发条件
设定阈值负载因子（STL标准阈值为0.7），当 N/M>0.7 时触发扩容。
Part2.5.2. 扩容执行流程
if (_n*10 / _tables.size()>=7)
{
HashTable<k, v> newht;
newht._tables.resize(2 * _tables.size());
for (auto& e : _tables)
{
if (e._state == Exist)
{
newht.Insert(e._kv);//代码复用
}
}
_tables.swap(newht._tables);
}
用码道免费领 1 个月 Token
cpp
运行
Part2.5.3. 扩容容量细节问题
如果扩容2倍后数值并非2的整数次幂，STL内部内置素数/2次幂对照表，自动选取距离目标值最近的合法容量数值。
Part3. 哈希表实现
Part3.1. 基础结构定义
<1> HashDate：存储键值对pair<K,V>，附带节点状态标识；
<2> HashTables：内部维护HashDate类型数组，记录当前有效数据个数_n。
Part3.2. 插入逻辑
bool Insert(const pair<k, v>& kv)
{
if (Find(kv.first) != nullptr)
{
return false;
}
if (_n*10 / _tables.size()>=7)
{
HashTable<k, v> newht;
newht._tables.resize(2 * _tables.size());
for (auto& e : _tables)
{
if (e._state == Exist)
{
newht.Insert(e._kv);
}
}
_tables.swap(newht._tables);
}
size_t hash0 = kv.first % _tables.size();
size_t hashi = hash0;
size_t i = 1;
int flag = 1;
while (_tables[hashi]._state ==Exist)
{
/*hashi=(hash0+i*i*flag+ _tables.size())% _tables.size();
if (flag == 1)
{
flag = -1;
}
else
{
++i;
flag = 1;
}
++i;*/
hashi = (hash0 + i) % _tables.size();
i++;
}
_tables[hashi]._kv = kv;
_tables[hashi]._state = Exist;
_n++;
return true;
}
用码道免费领 1 个月 Token
cpp
运行
Part3.3. 查找
HashData<k, v>* Find(const k& key)
{
size_t hash0 = key % _tables.size();
size_t hashi = hash0;
size_t i = 1;
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;
}
用码道免费领 1 个月 Token
cpp
运行
Part3.4. 删除
bool Erase(const k& key)
{
HashData<k, v >* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
ret->_state = Delete;
return true;
}
}
用码道免费领 1 个月 Token
cpp
运行
Part4. 结语
这篇文章我们认识到了哈希表的实现，接下来，小编还会带来哈希表的的更多知识，敬请期待~
最后，祝大家可以：春风得意马蹄疾，一日看尽长安花！
最后的最后，要是觉得本文还可以的话，可以点点赞，关注小编一波，谢谢大家！~