今天《新闻联播》回放,建设网站优化,seo招聘要求,网络服务器异常是怎么回事文章目录 1.开放地址法1.1key不能取模的问题1.1.1将字符串转为整型1.1.2将日期类转为整型 2.哈希函数2.1乘法散列法#xff08;了解#xff09;2.2全域散列法#xff08;了解#xff09; 3.处理哈希冲突3.1线性探测#xff08;挨着找#xff09;3.2二次探测#xff08;跳… 文章目录 1.开放地址法1.1key不能取模的问题1.1.1将字符串转为整型1.1.2将日期类转为整型 2.哈希函数2.1乘法散列法了解2.2全域散列法了解 3.处理哈希冲突3.1线性探测挨着找3.2二次探测跳跃着找3.3双重散列了解 4.链地址法4.1扩容4.2基本的框架4.3插入4.4查找4.5删除 5.代码 1.开放地址法
1.1key不能取模的问题 当key是string/Date等类型时key不能取模那么我们需要给HashTable增加一个仿函数这个仿函数支持把key转换成一个可以取模的整形如果key可以转换为整形并且不容易冲突那么这个仿函数就用默认参数即可如果这个Key不能转换为整形我们就需要自己实现一个仿函数传给这个参数实现这个仿函数的要求就是尽量key的每个值都参与到计算中让不同的key转换出的整形值不同。string做哈希表的key非常常见所以我们可以考虑把string特化一下。 1.1.1将字符串转为整型 key如果是字符串转为整形需要仿函数 // key / M , M哈希表的空间大小
size_t hash0 hash(kv.first) % _tables.size();// 将key转为无符号的整形因为key可能是负数
templateclass K
struct HashFunc
{size_t operator()(const K key){return (size_t)key;}
};// 特化
template
struct HashFuncstring
{size_t operator()(const string s){size_t sum 0;for (auto ch : s){sum ch;sum * 131;// *131为了避免哈希冲突,每次的key都不一样}return sum;}
};int main()
{const char* a[] { abcd,def,gca };HashTablestring, string ha;// 类型()是匿名对象// 哈希冲突了cout HashFuncstring()(abcd) endl;cout HashFuncstring()(aadd) endl;cout HashFuncstring()(acbd) endl;for (auto ch : a){ha.Insert({ ch,ch });}return 0;
}1.1.2将日期类转为整型
struct Date
{int _year;int _month;int _day;Date(int year 1,int month 1,int day 1):_year(year),_month(month),_day(day){}bool operator(const Date d){return _year d._year_month d._month_day d._day;}
};struct DateHashFunc
{size_t operator()(const Date d){size_t hash 0;hash d._year;hash * 131;hash d._month;hash * 131;hash d._day;hash * 131;return hash;}
};int main()
{// 将日期类转化为整型HashTableDate, int, DateHashFunc ht;ht.Insert({ { 2024,12,10 }, 1 });ht.Insert({ { 2024,10,12 }, 1 });return 0;
}2.哈希函数 设计哈希函数为了减少冲突让更多的位参与运算不管使用%不太接近2的幂次方的质数还是用位运算计算都是可以的 2.1乘法散列法了解 乘法散列法对哈希表大小M没有要求他的大思路第一步用关键字 Key 乘上常数 A (0A1)并抽 取出 key * A 的小数部分。第二步后再用M乘以key*A 的小数部分再向下取整。h(key) floor(M × ((A × key)%1.0)) 其中floor表示对表达式进行下取整A∈(0,1)这里最重要的是A的值应该如何设定Knuth认为 A ( 5 − 1)/2 0.6180339887… (黄金分割点])比较好。乘法散列法对哈希表大小M是没有要求的假设M为1024key为1234A 0.6180339887, A * key 762.6539420558取小数部分为0.6539420558, M×((A×key)%1.0) 0.6539420558*1024 669.6366651392那么h(1234) 669。 2.2全域散列法了解 如果存在一个恶意的对手他针对我们提供的散列函数特意构造出一个发生严重冲突的数据集比如让所有关键字全部落入同一个位置中。这种情况是可以存在的只要散列函数是公开且确定的就可以实现此攻击。解决方法自然是见招拆招给散列函数增加随机性攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。hab (key) ((a × key b)%P)%M P需要选⼀个足够大的质数a可以随机选[1,P-1]之间的任意整数b可以随机选[0,P-1]之间的任意整数这些函数构成了一个P*(P-1)组全域散列函数组。假设P17M6a 3 b 4, 则 h34 (8) ((3 × 8 4)%17)%6 5 。需要注意的是每次初始化哈希表时随机选取全域散列函数组中的⼀个散列函数使用后续增删查改都固定使用这个散列函数否则每次哈希都是随机选一个散列函数那么插入是一个散列函数查找又是另一个散列函数就会导致找不到插入的key了。 3.处理哈希冲突
3.1线性探测挨着找
缺点堆积
3.2二次探测跳跃着找
缺点无法充分利用位置 3.1和3.2上一篇博客详细说明了
3.3双重散列了解
缺点虽然可以充分利用位置但是还是要解决冲突的问题
h1 (key) hash0 key % M , hash0位置冲突了则双重探测公式为hc(key, i) hashi (hash0 i ∗ h2 (key)) % M i {1, 2, 3, …, M}要求 h2 (key) M 且 h2 (key) 和M互为质数有两种简单的取值方法 1、当M为2整数幂时h2 (key) 从[0M-1]任选一个奇数 2、当M为质数时 h2 (key) key % (M − 1) 1反例保证 h2 (key) 与M互质是因为根据固定的偏移量所寻址的所有位置将形成一个群若最大公约数说无法充分利用整个散列表。举例来说若初始探查位置为1偏移量为3整个散列表大小为12那么所能寻址的位置为{1, 4, 7, 10}寻址个数为p gcd(M, h1 (key)) 1 那么所能寻址的位置的个数为 M/P M 使得对于一个关键字来 12/gcd(12, 3) 4下面演示 {19,30,52,74} 等这一组值映射到M11的表中设 h2 (key) key%10 1本质是跳跃探测减少冲突堆积双重散列就是让数据更加地分散不容易产生哈希冲突 4.链地址法 开放地址法的问题是你占别人位置别人来了又占其他人的位置链地址法就不用占别人的位置自己位置可以存多个位置用了链表挂了多个数据 4.1扩容
开放地址法的负载因子必须小于1链地址法的负载因子没有这种规定可以大于1但是unordered_xxx中最大负载因子基本控制在1大于1就会扩容。
4.2基本的框架
namespace hash_bucket
{templateclass K,class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK,V kv):_kv(kv),_next(nullptr){}};templateclass K,class V,class Hash HashFuncKclass HashTable{typedef HashTableK, V Node;public:// 构造HashTable():_tables(__stl_next_prime(0)),_n(0){}private:vectorNode* _tables;// 指针数组size_t _n;// 表示存了多少个数据};
}4.3插入
头插尾插都可以这里用了头插
// 插入
bool Insert(const pairK,V kv)
{// 负载因子 1时扩容if (_n _tables.size()){// 这种方法每个节点都要拷贝,影响效率// 并且原数组释放完后,不会自动析构每个节点,因为是内置类型// 还要自己写析构函数,比较麻烦//HashTableK, V newht;//newht._tables.resize(_stl_next_prime(tables.size() 1));////for(size_t i 0;i _tables.size();i)//{// // 旧表的数据扩容后可能不冲突,必须一个一个取// Node* cur _tables[i];// while (cur)// {// newht.Insert(cur-_kv);// cur cur-_next;// }//}//_tables.swap(newht._tables);vectorNode* newTable(_tables.size() * 2);for(size_t i 0;i _tables.size();i){// 表旧表中的数据插入到新表中Node* cur _tables[i];while (cur){Node* next cur-_next;// 算cur在新表中的位置size_t hashi cur-_kv.first % newTable.size();cur-_next newTable[hashi];newTable[hashi] cur;cur next;}_tables[i] nullptr;}_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;
}int main()
{int a2[] { 19,30,5,36,13,20,21,12,24,96 };hash_bucket::HashTableint, int ht;for (auto e : a2){ht.Insert({ e,e });}ht.Insert({ 100,100 });ht.Insert({ 200,200 });return 0;
}4.4查找
// 查找
Node* Find(const K key)
{size_t hashi key % _tables.size();Node* cur _tables[hashi];while (cur){if (cur-_kv.first key){return cur;}cur cur-_next;}return nullptr;
}4.5删除
删除分为三种情况
头删让下一个节点变为头节点删除中间的节点保留前一个节点的指针指向后一个节点的指针尾删让最后一个节点的前一个节点的指针指向空2和3可以归为一类删除中间的节点可以是前一个节点指向空
// 删除
bool Erase(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){// 头删_tables[hashi] cur-_next;}else{// 删除中间的节点prev-_next cur-_next;}delete cur;--_n;return true;}else{prev cur;cur cur-_next;}}return false;
}5.代码
namespace hash_bucket
{templateclass K,class Vstruct HashNode{pairK, V _kv;HashNodeK, V* _next;HashNode(const pairK,V kv):_kv(kv),_next(nullptr){}};templateclass K,class V,class Hash HashFuncKclass HashTable{typedef HashNodeK, V Node;public:// 构造HashTable():_tables(__stl_next_prime(0)),_n(0){}// 析构~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;}}// 插入bool Insert(const pairK,V kv){Hash hash;// 如果插入的值存在冗余了返回falseif (Find(kv.first)){return false;}// 负载因子 1时扩容if (_n _tables.size()){// 这种方法每个节点都要拷贝,影响效率// 并且原数组释放完后,不会自动析构每个节点,因为是内置类型// 还要自己写析构函数,比较麻烦//HashTableK, V newht;//newht._tables.resize(_stl_next_prime(tables.size() 1));////for(size_t i 0;i _tables.size();i)//{// // 旧表的数据扩容后可能不冲突,必须一个一个取// Node* cur _tables[i];// while (cur)// {// newht.Insert(cur-_kv);// cur cur-_next;// }//}//_tables.swap(newht._tables);vectorNode* newTable(__stl_next_prime(_tables.size() 1));for(size_t i 0;i _tables.size();i){// 表旧表中的数据插入到新表中Node* cur _tables[i];while (cur){Node* next cur-_next;// 算cur在新表中的位置size_t hashi hash(cur-_kv.first) % newTable.size();cur-_next newTable[hashi];newTable[hashi] cur;cur next;}_tables[i] nullptr;}_tables.swap(newTable);}size_t hashi hash(kv.first) % _tables.size();// 头插Node* newnode new Node(kv);newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}// 查找Node* Find(const K key){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){size_t hashi key % _tables.size();Node* cur _tables[hashi];Node* prev nullptr;while (cur){if (cur-_kv.first key){if (prev nullptr){// 头删_tables[hashi] cur-_next;}else{// 删除中间的节点prev-_next cur-_next;}delete cur;--_n;return true;}else{prev cur;cur cur-_next;}}return false;}private:vectorNode* _tables;// 指针数组size_t _n;// 表示存了多少个数据};
}
