有做翻译英文网站,凡科做网站需要备案吗,网站开发主要语言,宜兴市建设局网站哈希节点状态
我们都很清楚数组里的每一个值无非三种状态#xff1a;
如果某下标没有值#xff0c;则代表空EMPTY。如果有值在代表存在EXIST。如果此位置的值被删掉了#xff0c;则表示为DELETE。
而这三种状态我们可以借助enum枚举来帮助我们表示数组里每个位置的状态。…哈希节点状态
我们都很清楚数组里的每一个值无非三种状态
如果某下标没有值则代表空EMPTY。如果有值在代表存在EXIST。如果此位置的值被删掉了则表示为DELETE。
而这三种状态我们可以借助enum枚举来帮助我们表示数组里每个位置的状态。这里我们专门封装一个类来记录每个位置的状态以此汇报给后续的哈希表。
enum State
{EMPTY,EXIST,DELETE
};//哈希节点
templateclass K, class V
struct HashData
{pairK, V _kv;State _state EMPTY;//记录每个位置的状态默认给空
};//哈希表
templateclass K, class V, class HashFunc DefaultHashK//添加仿函数便于把其他类型的数据转换为整型数据
class HashTable
{typedef HashDataK, V Data;
public://相关功能的实现……
private:vectorData _tables;size_t _n 0;//记录存放的有效数据的个数
};实现好了哈希节点的类就能够很好的帮助我们后续的查找示例 查找50
50%100下标0的值不是50继续下标往后查找直至下标3的下标为止。
查找60
60%100下标0不是往后下标继续查找找到下标4发现状态为EMPTY空此时停止查询因为往后就不可能出现了
删除10再查找50
50%100下标0的值不是下标到下标1发现状态为DELETE删除继续下标直至下标3的值为50找到了。
哈希表的扩容
散列表的载荷因子定义为α 填入表中的元素个数 / 散列表的长度。α是散列表装满程度的标志因子。由于表长是定值α与“填入表中的元素个数”成正比所以α越大表明填入表中的元素越多产生冲突的可能性就越大反之α越小表明填入表中的元素越少产生冲突的可能性就越小。实际上散列表的平均查找长度是载荷因子α的函数只是不同处理冲突的方法有不同的函数。对于开放定址法闭散列载荷因子是特别重要因素应严格限制在0.7 ~ 0.8以下。超过0.8查表时的CPU缓存不命中cache missing按照质数曲线上升。因此一些采用开放定址法的hash库如Java的系统库限制了载荷因子为0.75超过此值将resize散列表。
综上我们在后续的插入操作中必然要考虑到扩容的情况我们直接把负载因子控制在0.7超过了就扩容。具体操作见下文哈希表的插入操作。
构建仿函数把所有数据类型转换为整型并特化
在我们后续的插入操作中插入的数据类型如果是整数那么可以直接建立映射关系可若是字符串就没那么容易了因此我们需要套一层仿函数来帮助我们把字符串类型转换成整型的数据再建立映射关系。主要分为以下三类需要写仿函数的情况 key为整型为默认仿函数的情况。 此时的数据类型为整型直接强转size_t随后返回。 key为字符串单独写个字符串转整型的仿函数。 针对于字符串转整型我们推出下面两种方法不过都是会存在问题的 只用首字母的ascii码来映射此法不合理因为abc和axy本是俩不用字符串经过转换会引发冲突。字符串内所有字符ASCII码值之和此法也会产生冲突因为abcd和bcad在此情况就会冲突。
为了避免冲突几位大佬推出多种算法思想下面我取其中一种算法思想来讲解
BKDR哈希算法
hash hash * 131 ch; // 也可以乘以31、131、1313、13131、131313.. 为了能够让我们的哈希表能够自动识别传入数据的类型不用手动声明这里我们可以借助特化来解决仿函数特化总代码如下
//利用仿函数将数据类型转换为整型
templateclass K
struct DefaultHash
{size_t operator()(const K key){return (size_t)key;}
};
//模板的特化
template
struct DefaultHashstring
{size_t operator()(const string key){//BKDR哈希算法size_t hash 0;for (auto ch : key){hash hash * 131 ch;//把所有字符的ascii码值累计加起来}return hash;}
};哈希表的插入
哈希表的插入主要是三大步骤
去除冗余扩容操作插入操作
下面分开来演示。
1、去除冗余
复用Find查找函数去帮助我们查找插入的值是否存在 。若存在直接返回false 。不存在再进行后续的插入操作。
2、扩容操作
如果哈希表一开始就为空则要扩容。如果填入表中的元素个数*10 再 / 表的大小7就扩容*10是为了避免出现size_t的类型相除不会有小数的情况。扩容以后要重新建立映射关系。创建一个新的哈希对象扩容到先前旧表扩容的大小。遍历旧表把旧表每个存在的元素插入到新表此步骤让新表自动完成映射关系无序手动构建。利用swap函数把新表交换到旧表那此时的旧表就是已经扩好容且建立号映射关系的哈希表。
3、插入操作
借助仿函数把插入的数据类型转为整型并定义变量保存插入键值对的key。用此变量%哈希表的size()不能是capacity()因为[ ]运算符会判断下标是否小于size且对于哈希表应该尽量控制size和capacity一样大。遍历进行线性探测 / 二次探测如果这个位置的状态为EXIST存在说明还要往后遍历查找。遍历结束说明此位置的状态为空EMPTY或删除DELETE可以放值。把插入的值放进该位置更新状态为EXIST有效数据个数。
//插入
bool Insert(const pairK, V kv)
{//1、去除冗余if (Find(kv.first)){//说明此值已经有了直接返回falsereturn false;}//2、扩容//负载因子超过0.7就扩容if (_tables.size() 0 || _n * 10 / _tables.size() 7){size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;//扩容以后需要重新建立映射关系HashTableK, V, HashFunc newHT;newHT._tables.resize(newSize);//遍历旧表把旧表每个存在的元素插入newHTfor (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);//建立映射关系后交换}//3、插入HashFunc hf;size_t starti hf(kv.first);//取出键值对的key并且避免了负数的情况借用仿函数确保是整型数据starti % _tables.size();size_t hashi starti;size_t i 1;//线性探测/二次探测while (_tables[hashi]._state EXIST){hashi starti i;//二次探测改为 i^2i;hashi % _tables.size();//防止hashi超出数组}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;
}哈希表的查找
查找的核心逻辑就是找到key相同就返回此对象的地址找到空就返回nullptr具体细分规则如下
先去判断表的大小是否为0为0直接返回nullptr。按照线性探测 / 二次探测的方式去遍历遍历的条件是此位置的状态不为空EMPTY。如果遍历到某哈希表中的对象的值等于要查找的值前提是此位置的状态不为DELETE删除返回此对象的地址。当遍历结束后说明此位置的状态为空EMPTY哈希表没有我们要查找的值返回nullptr。
//查找
Data* Find(const K key)
{//判断表的size是否为0if (_tables.size() 0){return nullptr;}HashFunc hf;size_t starti hf(key);//通过仿函数把其它类型数据转为整型数据starti % _tables.size();size_t hashi starti;size_t i 1;//线性探测/二次探测while (_tables[hashi]._state ! EMPTY)//不为空就继续{if (_tables[hashi]._state ! DELETE _tables[hashi]._kv.first key){return _tables[hashi];//找到了就返回此对象的地址}hashi starti i;//二次探测改为 i^2i;hashi % _tables.size();//防止hashi超出数组}return nullptr;
}哈希表的删除
删除的逻辑很简单遵循下面的规则
复用Find函数去帮我们查找删除的位置是否存在。若存在把此位置的状态置为DELETE即可此时表中的有效数据个数_n需要减减最后返回true。若不存在直接返回false。
//删除
bool Erase(const K key)
{//复用Find函数去帮助我们查找删除的值是否存在Data* ret Find(key);if (ret){//若存在直接把此位置的状态置为DELETE即可ret-_state DELETE;return true;}else{return false;}
}完整代码
#pragma once
#includeiostream
#includestring
#includevector
using namespace std;//利用仿函数将数据类型转换为整型
templateclass K
struct DefaultHash
{size_t operator()(const K key){return (size_t)key;}
};
//模板的特化
template
struct DefaultHashstring
{size_t operator()(const string key){//BKDR哈希算法size_t hash 0;for (auto ch : key){hash hash * 131 ch;//把所有字符的ascii码值累计加起来}return hash;}
};//闭散列哈希表的模拟实现
namespace CloseHash
{enum State{EMPTY,EXIST,DELETE};//哈希节点状态的类templateclass K, class Vstruct HashData{pairK, V _kv;State _state EMPTY;//记录每个位置的状态默认给空};//哈希表的类templateclass K, class V, class HashFunc DefaultHashK//添加仿函数便于把其他类型的数据转换为整型数据class HashTable{typedef HashDataK, V Data;public://插入bool Insert(const pairK, V kv){//1、去除冗余if (Find(kv.first)){//说明此值已经有了直接返回falsereturn false;}//2、扩容//负载因子超过0.7就扩容if (_tables.size() 0 || _n * 10 / _tables.size() 7){size_t newSize _tables.size() 0 ? 10 : _tables.size() * 2;//扩容以后需要重新建立映射关系HashTableK, V, HashFunc newHT;newHT._tables.resize(newSize);//遍历旧表把旧表每个存在的元素插入newHTfor (auto e : _tables){if (e._state EXIST){newHT.Insert(e._kv);}}newHT._tables.swap(_tables);//建立映射关系后交换}//3、插入HashFunc hf;size_t starti hf(kv.first);//取出键值对的key并且避免了负数的情况借用仿函数确保是整型数据starti % _tables.size();size_t hashi starti;size_t i 1;//线性探测/二次探测while (_tables[hashi]._state EXIST){hashi starti i;//二次探测改为 i^2i;hashi % _tables.size();//防止hashi超出数组}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}//查找Data* Find(const K key){//判断表的size是否为0if (_tables.size() 0){return nullptr;}HashFunc hf;size_t starti hf(key);//通过仿函数把其它类型数据转为整型数据starti % _tables.size();size_t hashi starti;size_t i 1;//线性探测/二次探测while (_tables[hashi]._state ! EMPTY)//不为空就继续{if (_tables[hashi]._state ! DELETE _tables[hashi]._kv.first key){return _tables[hashi];//找到了就返回此对象的地址}hashi starti i;//二次探测改为 i^2i;hashi % _tables.size();//防止hashi超出数组}return nullptr;}//删除bool Erase(const K key){//复用Find函数去帮助我们查找删除的值是否存在Data* ret Find(key);if (ret){//若存在直接把此位置的状态置为DELETE即可ret-_state DELETE;return true;}else{return false;}}private:vectorData _tables;size_t _n 0;//记录存放的有效数据的个数};
}
