架设仿冒网站挂马,以网站域名做邮箱,丹阳网站推广,专注移动网站建设目录 一#xff0c;哈希概念
1.1#xff0c;直接定址法
1.2#xff0c;哈希冲突
1.3#xff0c;负载因子
二#xff0c;哈希函数
2.1#xff0c;除法散列法 /除留余数法
2.2#xff0c;乘法散列法
2.3#xff0c;全域散列法
三#xff0c;处理哈希冲突
3.1哈希概念
1.1直接定址法
1.2哈希冲突
1.3负载因子
二哈希函数
2.1除法散列法 /除留余数法
2.2乘法散列法
2.3全域散列法
三处理哈希冲突
3.1开放定址法
线性探测
二次探测
双重探测
3.2开放定址法代码实现
哈希表扩容问题
key不能取模的问题 完整代码实现
3.3链地址法
哈希表扩容问题
链地址法代码实现
小结 一哈希概念
哈希hash)又称散列是一种组织数据的方式。从译名看有散乱排列的意思。本质就是通过哈希函数把关键字key和存储位置建立一个映射关系查找时通过这个哈希函数计算出key存储的位置实现快速查找。
说白了hash函数就是根据key计算出应该存储地址的位置而哈希表是基于hash函数建立的一种查找表。
1.1直接定址法
当关键字的范围比较集中时直接定址法就是非常简单高效的方法。比如一组关键字的值在[0,99]之间那么我们开一个100大小的数组每个关键字的值直接就是存储位置的下标。再比如一组数据a~z的字符我们可以开一个大小为26的数组每个关键字的acsll值减去 a的ascll值就是对应的存储位置下标。也就是说直接定址法是用关键字计算出一个绝对位置或相对位置。
本题链接387. 字符串中的第一个唯一字符 - 力扣LeetCode class Solution { public: int firstUniqChar(string s) { int hash[26]{0}; //统计次数 for(auto ch:s) { hash[ch-a]; } for(int i0;is.size();i) { if(hash[s[i]-a]1) return i; } return -1; } }; 1.2哈希冲突
不同的key值产生相同的地址即Hkey1)Hkey2)。这种问题叫做哈希冲突或哈希碰撞。
1.3负载因子
假设哈希表已经存储N个值哈希表的大小为M那么负载因子N/M。负载因子越大代表哈希冲突的概率越高空间利用率越高负载因子越小代表哈希冲突的概率越低空间利用率越低。
二哈希函数
两个不同的key值可能 会映射到同一个位置这个问题叫做哈希冲突。理想情况是找一个哈希函数避免冲突但是实际场景中冲突不可避免所以我们尽可能设计出好的哈希函数来减少哈希冲突。
哈希函数的设计可能有很多讲究比如要考虑均匀性、确定性、高效性等等。不同的应用场景可能需要不同的哈希函数。比如非加密的哈希函数可能更注重速度而加密的哈希函数则需要更高的安全性防止被逆向或者找到碰撞。
2.1除法散列法 /除留余数法
除法散列法也叫除留余数法假设哈希表的大小为M那么通过key除以M的余数作为映射的下标。也就是哈希函数为H(key)key%M。当使用 除法散列法时应避免M的大小为某些值比如2的幂10的幂等。如果是2的x次方那么key%2^x相当于保留key的二进制前x位。那么前x位二进制相同的key值计算出的哈希值都是一样的就会加剧哈希冲突。原因key%2^x相当于key(2^x-1)其中 2^x-1的二进制表示中前x均为1其余为均为0所以最后按位与的结果取决于key的前x位。【见下图】 当使用除法散列 法时建议M取不太接近2的整数次幂的一个质数素数
2.2乘法散列法
乘法散列法对哈希表的大小M没有要求它的大思路第一步用关键字key乘上A(0A1)并抽取出key*A的小数部分。第二步再用M乘以key*A的小数部分再向下取整。H(key)floor(M*((A*key)%1.0))其中floor表示对表达式进行向下取整。0A1这里最重要的时A的值该如何设定。Knuth认为设为黄金分割点比较好
2.3全域散列法
如果存在一个对手他针对我们的哈希函数特意构造出一个发生严重冲突的数据集。比如让所有关键字落入同一个位置这种情况是可以存在的。只要哈希函数公开且时确定的就可以实现次攻击。解决此方法就是给哈希函数增加随机性攻击者就无法找出确定的导致冲突 加剧的数据。这种方法叫做全域散列。H[a][b](key)((a*keyb)%P)%M。P选择一个足够大的质数a可以任意选[1,P-1]之间的一个整数b可以选[0,P-1]之间的任意整数这些函数就构成了一个P*(P-1)组全域散列函数组。假设P17M6a3b4则H[3][4]8((3*84)17)%65。需要注意的是每次初始化哈希表时随机选取全域散列函数组中的一个散列哈希函数使用后序增删查改都固定使用这个散列函数。否则每次哈希都是随机选一个散列函数那么插入是一个散列函数查找又是另一个散列函数就会导致查找不到插入的key值。 总结实践中哈希表一般是选择除法散列法作为哈希函数。当然哈希表无论选择什么哈希函数都无法避免哈希冲突那么插入数据时如何解决哈希冲突呢主要有两种方法开放定址法和链地址法。
三处理哈希冲突
3.1开放定址法
开放定址法中所有元素都放到哈希表里。当一个关键字key用哈希函数计算出的位置冲突了则按照某种规则找到一个没有存储数据的位置存储。这里的规则有三种线性探测二次探测双重探测。
线性探测
从发生冲突的位置开始依次向后进行 线性探测直到寻找到一个没有存储数据的位置为止如果走到哈希表尾则回绕到哈希表头 的位置。H(key)key%Mhash0其中hash0代表映射的位置如果该位置没有数据则将key填入 。如果hash0位置已经存在数据也就是hash0位置冲突了则线性探测公式为Hc(key)(hash0i)%Mhashii0,1,2,3...,M-1。其中hashi就是经过线性探测找到没有存储数据的位置再将key填入。
下面演示{19,30,5,36,13,20,21,12} 等映射到M11的表中. 线性探测问题假设hash0位置连续冲突hash0,hash1,hash2已经存储数据了后序映射到hash0hash1hash2的值都会 争夺hash3位置这种现象叫做群集/堆积。下面的二次探测可以解决这个问题。
二次探测
从发生冲突的位置依次左右按二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止。如果 往右走到哈希表尾则回绕到哈希表头的位置如果往左走到哈希表头则会绕道哈希表尾的位置。H(key)key%Mhash0hash0位置冲突了则二次探测公式为Hc(key)(hash0/-i*i)%Mi1,2,3..,M/hashi.二次探测结果hashi可能为负数当hashi0时hashiM。
下面演示{19,30,52,63,11,22}映射到M11的表中 双重探测
第⼀个哈希函数计算出的值发生冲突使用第二个哈希函数计算出⼀个跟key相关的偏移量值不断往后探测直到寻找到下一个没有存储数据的位置为止。H(key)key%Mhash0hash0位置冲突了则双重探测公式为Hc(key)(hash0i*H2(key))%Mhashii1,2,3,...,M
3.2开放定址法代码实现
开放定址法在时间中不如下面的连地址法所以我们选择简单的线性探测实现即可。
结构 //当前位置的状态
//存在 空 已删除
enum State
{EXIT,EMPTY,DELETE
};template class k,class v
struct HashData
{pairk, v _kv;State _state EMPTY;
};template class k,class v
class HashTable
{
private:vectorHashdatak, v _tables; //哈希表size_t n 0; //表中存储数据的个数
};
要注意的是这⾥需要给每个存储值的位置加⼀个状态标识否则删除⼀些值以后会影响后⾯冲突的值的查找。如下图我们删除30会导致查找20失败当我们给每个位置加⼀个状态标识{EXIST,EMPTY,DELETE}删除30就可以不用删除值而是把状态改为DELETE那么查找20时遇到EMPTY才停就可以找到20。 哈希表扩容问题
这里我们哈希表负载因子控制在0.7当负载因子到0.7以后我们就需要扩容了我们如果还是按照2倍扩 容但是同时我们要保持哈希表大小是一个质数第一个是质数2倍后就不是质数了。所以我们可以按照sgi版本的哈希表使用的方法。给了⼀个近似2倍的质数表每次去质数表获取扩容后的大小。 inline unsigned long __stl_next_prime(unsigned long n) { static const int __stl_num_primes 28; static const unsigned long __stl_prime_list[__stl_num_primes] { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; const unsigned long* first __stl_prime_list; const unsigned long* last __stl_prime_list __stl_num_primes; const unsigned long* pos lower_bound(first, last, n); return pos last ? *(last - 1) : *pos; } 在需要扩容时调用__stl_next_prime(n在__stl_prime_list数组中查找第一个大于等于n的数组并返回。
key不能取模的问题
当key是string/Date等类型时key不能取模那么我们需要给HashTable增加⼀个仿函数这个仿函 数⽀持把key转换成⼀个可以取模的整形如果key可以转换为整形并且不容易冲突那么这个仿函数就用默认参数即可如果这个Key不能转换为整形我们就需要自己实现⼀个仿函数传给这个参数实 现这个仿函数的要求就是尽量key的每个值都参与到计算中让不同的key转换出的整形值不同。string做哈希表的key值很常见我们可以考虑把string特化一下。 template class k class HashFunc { size_t operator()(const k key) { return (size_t)key; } }; //特化 template struct HashFuncstring { // 字符串转换成整形可以把字符ascii码相加即可 // 但是直接相加的话类似abcd和bcad这样的字符串计算出是相同的 // 这⾥我们使⽤BKDR哈希的思路用上次的计算结果去乘以⼀个质数这个质数⼀般去31, 131等效果会比较好 size_t operator()(const string s) { size_t hash 0; for (auto ch : s) { hash ch; hash * 131; } return hash; } }; 完整代码实现
//当前位置的状态
//存在 空 已删除
enum State
{EXIT,EMPTY,DELETE
};template class k,class v
struct HashData
{pairk, v _kv;State _state EMPTY;
};template class k
class HashFunc
{size_t operator()(const k key){return (size_t)key;}
};
//特化
template
struct HashFuncstring
{// 字符串转换成整形可以把字符ascii码相加即可// 但是直接相加的话类似abcd和bcad这样的字符串计算出是相同的// 这⾥我们使⽤BKDR哈希的思路⽤上次的计算结果去乘以⼀个质数这个质数⼀般去31, 131等效果会比较好size_t operator()(const string s){size_t hash 0;for (auto ch : s){hash ch;hash * 131;}return hash;}
};templateclass k, class v, class Hash HashFunck
class HashTable
{
public:HashTable():_tables(__stl_next_prime(0)), _n(0){}inline unsigned long __stl_next_prime(unsigned long n){static const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first __stl_prime_list;const unsigned long* last __stl_prime_list __stl_num_primes;const unsigned long* pos lower_bound(first, last, n);return pos last ? *(last - 1) : *pos;}bool insert(const pairk, v kv){Hash hash;//负载因子0.7 扩容if (_n * 10 / _tables.size() 7){//创建一个新表HashTablek, v, Hash newht;//扩容newht._tables.resize(__stl_next_prime(_tables.size() 1));//旧表数据映射到新表for (auto data : _tables){if (data._state EXIST)newht.insert(data._kv);}//_tablesnewht._tables;_tables.swap(newht._tables);}size_t hash0 hash(kv.first) % _tables.size();size_t hashi hash0;int i 1;while (_tables[hashi]._state EXIST){//线性探测hashi (hash0 i) % _tables.size();//防止越界i;}_tables[hashi]._kv kv;_tables[hashi]._state EXIST;_n;return true;}HashDatak, v* find(const k key){Hash hash;size_t hash0 hash(key) % _tables.size();size_t hashi hash0;int i 1;while (_tables[hashi]._state ! EMPTY){if (_tables[hashi]._kv.first key _tables[hashi]._state EXIST){return _tables[hashi];}//线性探测hashi (hash0 i) % _tables.size();//防止越界i;}return nullptr;}bool erase(const k key){HashDatak, v* ret find(key);if (ret){ret-_state DELETE;return true;}else{return false;}}
private:vectorHashDatak, v _tables;size_t _n;
};3.3链地址法
开放定址法中所有的元素都放到哈希表里链地址法中所有的数据不再直接存储在哈希表中。哈希表 中存储一个指针没有数据映射这个位置时这个指针为空有多个数据映射到这个位置时我们把这些冲突的数据链接成⼀个链表挂在哈希表这个位置下面链地址法也叫做拉链法或者哈希桶。
下面演示{19,30,5,36,13,20,21,12,24,96} 等这一组值映射到M11的表中 哈希表扩容问题
开放定址法负载因子必须小于1链地址法的负载因子就没有限制了可以大于1。负载因子越大哈 希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低STL中的unordered_map和unordered_set最大复杂因子进本控制在1大于1就开始扩容。
链地址法代码实现
//链地址法
//哈希桶
templateclass k, class v
struct HashNode
{pairk, v _kv;HashNodek, v* _next;HashNode(const pairk, v kv):_kv(kv), _next(nullptr){}
};
templateclass k, class v
class Hash_bucket
{
public:typedef HashNodek, v Node;Hash_bucket():_tables(__stl_next_prime(0)), _n(0){}~Hash_bucket(){for (int i 0; i _tables.size(); i){Node* cur _tables[i];while (cur){Node* next cur-_next;delete cur;cur next;}_tables[i] nullptr;}}inline unsigned long __stl_next_prime(unsigned long n){static const int __stl_num_primes 28;static const unsigned long __stl_prime_list[__stl_num_primes] {53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};const unsigned long* first __stl_prime_list;const unsigned long* last __stl_prime_list __stl_num_primes;const unsigned long* pos lower_bound(first, last, n);return pos last ? *(last - 1) : *pos;}bool insert(const pairk, v kv){//防止键值冗余if (find(kv.first))return false;//负载因子1时扩容if (_n / _tables.size() 1){//创建新表vectorNode* newtables(__stl_next_prime(_tables.size() 1));for (int i 0; i _tables.size(); i){Node* cur _tables[i];//直接将旧表中的节点插入到新表中 所映射的位置while (cur){Node* next cur-_next;//直接插入到新表size_t hashi cur-_kv.first % newtables.size();cur-_next newtables[hashi];newtables[hashi] cur;cur next;}}_tables.swap(newtables);}size_t hashi kv.first % _tables.size();Node* newnode new Node(kv);//头插到新表newnode-_next _tables[hashi];_tables[hashi] newnode;_n;return true;}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;}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;
};小结
哈希表这种数据结构是利用哈希函数来快速定位数据的位置然后存储到数组中的相应位置。
这样在查找的时候时间复杂度可以接近O(1)非常高效。不过如果多个键被哈希到同一个位置就会发生冲突这时候需要解决冲突的方法比如链地址法或者开放寻址法。 那哈希表的实现原理大概是怎样的呢当插入一个键值对时首先用哈希函数计算键的哈希值然后根据哈希值找到对应的数组下标如果该位置已经有元素了就用链表或者其他方式处理冲突然后存储进去。查找的时候同样计算哈希值找到位置后如果该位置有多个元素需要遍历链表进行查找。好的哈希函数应该尽量均匀分布减少冲突这样哈希表的效率才会高。
