1.哈希的介绍哈希(hash)⼜称散列是⼀种组织数据的⽅式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系查找时通过这个哈希函数计算出Key存储的位置进⾏快速查找。(1)直接定址法当关键字的范围⽐较集中时直接定址法就是⾮常简单⾼效的⽅法⽐如⼀组关键字都在[0,99]之间那么我们开⼀个100个数的数组每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在[a,z]的⼩写字⺟那么我们开⼀个26个数的数组每个关键字acsii码-a ascii码就是存储位置的下标。也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。计数排序也用的题目class Solution { public: int firstUniqChar(string s) { // 每个字⺟的ascii码-a的ascii码作为下标映射到count数组数组中存储出现的次数 int count[26] {0}; // 统计次数 for(auto ch : s) { count[ch-a]; } for(size_t i 0; i s.size(); i) { if(count[s[i]-a] 1) return i; } return -1; } }另一个题目class Solution { public: vectorstring uncommonFromSentences(string s1, string s2) { stringstream ss1(s1),ss2(s2); unordered_mapstring,int cnt; string word; while(ss1word) { cnt[word]; } while(ss2word) { cnt[word]; } vectorstring result; for(auto x:cnt) { if(x.second1) { result.push_back(x.first); } } return result; } };(2)哈希冲突直接定址法的缺点也⾮常明显当关键字的范围⽐较分散时就很浪费内存甚⾄内存不够⽤。假设我们只有数据范围是[0, 9999]的N个值我们要映射到⼀个M个空间的数组中(⼀般情况下M N)那么就要借助哈希函数(hash function)hf关键字key被放到数组的h(key)位置这⾥要注意的是h(key)计算出的值必须在[0, M)之间。这⾥存在的⼀个问题就是两个不同的key可能会映射到同⼀个位置去这种问题我们叫做哈希冲突或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突但是实际场景中冲突是不可避免的所以我们尽可能设计出优秀的哈希函数减少冲突的次数同时也要去设计出解决冲突的⽅案。(3)负载因子假设哈希表中已经映射存储了N个值哈希表的⼤⼩为M那么负载因子N/M 负载因⼦有些地⽅也翻译为载荷因⼦/装载因⼦等他的英⽂为load factor。负载因⼦越⼤哈希冲突的概率越⾼空间利⽤率越⾼负载因⼦越⼩哈希冲突的概率越低空间利⽤率越低(4)将关键字转换成整数我们将关键字映射到数组中位置⼀般是整数好做映射计算如果不是整数我们要想办法转换成整数这个细节我们后⾯代码实现中再进⾏细节展⽰。下⾯哈希函数部分我们讨论时如果关键字不是整数那么我们讨论的Key是关键字转换成的整数。(5)哈希函数⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中却很难做到但是我们要尽量往这个⽅向去考量设计。(5)1.除法散列法/除留余数法除法散列法也叫做除留余数法顾名思义假设哈希表的⼤⼩为M那么通过key除以M的余数作映射位置的下标也就是哈希函数为h(key) key % M。当使⽤除法散列法时要尽量避免M为某些值如2的幂10的幂等。如果是 2^x那么key %本质相当于保留key的后X位那么后x位相同的值计算出的哈希值都是⼀样的就冲突了。如 {63 , 31}看起来没有关联的值如果M是16也就是2^4 那么计算出的哈希值都是15因为63的⼆进制后8位是 0011111131的⼆进制后8位是 00011111。如果是10^x就更明显了保留的都是10进值的后x位如{112, 12312}如果M是100也就是10^2 那么计算出的哈希值都是12。当使⽤除法散列法时建议M取不太接近2的整数次幂的⼀个质数(素数)。需要说明的是实践中也是⼋仙过海各显神通Java的HashMap采⽤除法散列法时就是2的整数次幂做哈希表的⼤⼩M这样玩的话就不⽤取模⽽可以直接位运算相对⽽⾔位运算⽐模更⾼效⼀些。但是他不是单纯的去取模⽐如M是2^16次⽅本质是取后16位那么⽤key’ key16然后把key和key 异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围内但是尽量让key所有的位都参与计算这样映射出的哈希值更均匀⼀些即可。所以我们上⾯建议M取不太接近2的整数次幂的⼀个质数的理论是⼤多数数据结构书籍中写的理论吗但是实践中灵活运⽤抓住本质⽽不能死读书。(5)2.乘法散列法乘法散列法对哈希表⼤⼩M没有要求他的⼤思路第⼀步⽤关键字 K 乘上常数 A (0A1)并抽取出 k*A 的⼩数部分。第⼆步后再⽤M乘以k*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。(5)3.全域散列法如果存在⼀个恶意的对⼿他针对我们提供的散列函数特意构造出⼀个发⽣严重冲突的数据集⽐如让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的只要散列函数是公开且确定的就可以实现此攻击。解决⽅法⾃然是⻅招拆招给散列函数增加随机性攻击者就⽆法找出定可以导致最坏情况的数据。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了。还有其他方法比如平⽅取中法、折叠法、随机数法、数学分析法等2.处理哈希冲突实践中哈希表⼀般还是选择除法散列法作为哈希函数当然哈希表⽆论选择什么哈希函数也避免不了冲突那么插⼊数据时如何解决冲突呢主要有两种两种⽅法开放定址法和链地址法。(1)开放定址法在开放定址法中所有的元素都放到哈希表⾥当⼀个关键字key⽤哈希函数计算出的位置冲突了则按照某种规则找到⼀个没有存储数据的位置进⾏存储开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种线性探测、⼆次探测、双重探测。线性探测从发⽣冲突的位置开始依次线性向后探测直到寻找到下⼀个没有存储数据的位置为⽌如果⾛到哈希表尾则回绕到哈希表头的位置。h(key) hash0 key % Mhash0位置冲突了则线性探测公式为hc(key, i) hashi (hash0 i) % M i {1, 2, 3, ..., M - 1}因为负载因⼦⼩于1则最多探测M-1次⼀定能找到⼀个存储key的位置。线性探测的⽐较简单且容易实现线性探测的问题假设hash0位置连续冲突hash0hash1hash2位置已经存储数据了后续映射到hash0hash1hash2hash3的值都会争夺hash3位置这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题。下⾯演⽰ {19,30,5,36,13,20,21,12} 等这⼀组值映射到M11的表中。二次探测从发⽣冲突的位置开始依次左右按⼆次⽅跳跃式探测直到寻找到下⼀个没有存储数据的位置为⽌如果往右⾛到哈希表尾则回绕到哈希表头的位置如果往左⾛到哈希表头则回绕到哈希表尾的位置h(key) hash0 key % M hash0位置冲突了则⼆次探测公式为hc(key, i) hashi (hash0 ± i^2) % M i {1, 2, 3, ...,M/2 }⼆次探测当 hashi (hash0 - i^2)%M 时当hashi0时需要hashi M下⾯演⽰ {19,30,52,63,11,22} 等这⼀组值映射到M11的表中。双重散列第⼀个哈希函数计算出的值发⽣冲突使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值不断往后探测直到寻找到下⼀个没有存储数据的位置为⽌。h1(key) hash0 key % Mhash0位置冲突了则双重探测公式为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互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群若最⼤公约数p gcd(M, h1(key)) 1 那么所能寻址的位置的个数为M/P M 使得对于⼀个关键字来说⽆法充分利⽤整个散列表。举例来说若初始探查位置为1偏移量为3整个散列表⼤⼩为12那么所能寻址的位置为{1, 4, 7, 10}寻址个数为12/gcd(12, 3) 4下⾯演⽰ {19,30,52,74} 等这⼀组值映射到M11的表中设 h2(key) key%10 1//开方定址法的哈希表结构 enum State { EXIST, EMPTY, DELETE }; templateclass K, class V struct HashData { pairK, V _kv; State _state EMPTY; }; templateclass K, class V class HashTable { private: vectorHashDataK, V _tables; size_t _n 0; // 表中存储数据个数 };要注意的是这⾥需要给每个存储值的位置加⼀个状态标识否则删除⼀些值以后会影响后⾯冲突的值的查找。如下图我们删除30会导致查找20失败当我们给每个位置加⼀个状态标识{EXIST,DELETE,EMPTY}删除30就不用删除值而是把状态改成DELETE,那么查找20时遇到EMPTY才能就找到20.扩容这⾥我们哈希表负载因⼦控制在0.7当负载因⼦到0.7以后我们就需要扩容了我们还是按照2倍扩容但是同时我们要保持哈希表⼤⼩是⼀个质数第⼀个是质数2倍后就不是质数了。那么如何解决了⼀种⽅案就是上⾯1.4.1除法散列中我们讲的Java HashMap的使⽤2的整数幂但是计算时不能直接取模的改进⽅法。另外⼀种⽅案是sgi版本的哈希表使⽤的⽅法给了⼀个近似2倍的质数表每次去质数表获取扩容后的⼤⼩。inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. 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; }key不能取模的问题当key是string/Date等类型时key不能取模那么我们需要给HashTable增加⼀个仿函数这个仿函数⽀持把key转换成⼀个可以取模的整形如果key可以转换为整形并且不容易冲突那么这个仿函数就⽤默认参数即可如果这个Key不能转换为整形我们就需要⾃⼰实现⼀个仿函数传给这个参数实现这个仿函数的要求就是尽量key的每值都参与到计算中让不同的key转换出的整形值不同。string做哈希表的key⾮常常⻅所以我们可以考虑把string特化⼀下。templateclass K struct 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 key) { size_t hash 0; for (auto e : key) { hash * 131; hash e; } return hash; } }; templateclass K, class V, class Hash HashFuncK class HashTable { public: private: vectorHashDataK, V _tables; size_t _n 0; // 表中存储数据个数 }整体代码namespace open_address { enum State { EXIST, EMPTY, DELETE }; templateclass K, class V struct HashData { pairK, V _kv; State _state EMPTY; }; templateclass K, class V, class Hash HashFuncK class HashTable { public: inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. 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; } HashTable() { _tables.resize(__stl_next_prime(0)); } bool Insert(const pairK, V kv) { if (Find(kv.first)) return false; // 负载因⼦⼤于0.7就扩容 if (_n * 10 / _tables.size() 7) { // 这⾥利⽤类似深拷⻉现代写法的思想插⼊后交换解决 HashTableK, V, Hash newHT; newHT._tables.resize(__stl_next_prime(_tables.size()1)); for (size_t i 0; i _tables.size(); i) { if (_tables[i]._state EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } Hash hash; size_t hash0 hash(kv.first) % _tables.size(); size_t hashi hash0; size_t i 1; while (_tables[hashi]._state EXIST) { // 线性探测 hashi (hash0 i) % _tables.size(); // ⼆次探测就变成 - i^2 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; 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; } bool Erase(const K key) { HashDataK, V* ret Find(key); if (ret nullptr) { return false; } else{ ret-_state DELETE; --_n; return true; } } private: vectorHashDataK, V _tables; size_t _n 0; // 表中存储数据个数 }; }(2)链地址法扩容开放定址法负载因⼦必须⼩于1链地址法的负载因⼦就没有限制了可以⼤于1。负载因⼦越⼤哈希冲突的概率越⾼空间利⽤率越⾼负载因⼦越⼩哈希冲突的概率越低空间利⽤率越低stl中unordered_xxx的最⼤负载因⼦基本控制在1⼤于1就扩容我们下⾯实现也使⽤这个⽅式。极端场景如果极端场景下某个桶特别⻓怎么办其实我们可以考虑使⽤全域散列法这样就不容易被针对了。但是假设不是被针对了⽤了全域散列法但是偶然情况下某个桶很⻓查找效率很低怎么办这⾥在Java8的HashMap中当桶的⻓度超过⼀定阀值(8)时就把链表转换成红⿊树。⼀般情况下不断扩容单个桶很⻓的场景还是⽐较少的下⾯我们实现就不搞这么复杂了这个解决极端场景的思路⼤家了解⼀下。namespace hash_bucket { 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 HashFuncK class HashTable { typedef HashNodeK, V Node; 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; } public: HashTable() { _tables.resize(__stl_next_prime(0), nullptr); } / / 拷⻉构造和赋值拷⻉需要实现深拷⻉有兴趣的同学可以⾃⾏实现 ~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 hs; size_t hashi hs(kv.first) % _tables.size(); // 负载因⼦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* newtables(__stl_next_prime(_tables.size()1), nullptr); for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; // 旧表中节点挪动新表重新映射的位置 size_t hashi hs(cur-_kv.first) % newtables.size(); // 头插到新表 cur-_next newtables[hashi]; newtables[hashi] cur; cur next; } _tables[i] nullptr; } _tables.swap(newtables); } // 头插 Node* newnode new Node(kv); newnode-_next _tables[hashi]; _tables[hashi] newnode; _n; return true; } 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; } 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; } private: vectorNode* _tables; // 指针数组 size_t _n 0; // 表中存储数据个数 }; }
哈希表，咕咕咕!
1.哈希的介绍哈希(hash)⼜称散列是⼀种组织数据的⽅式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字Key跟存储位置建⽴⼀个映射关系查找时通过这个哈希函数计算出Key存储的位置进⾏快速查找。(1)直接定址法当关键字的范围⽐较集中时直接定址法就是⾮常简单⾼效的⽅法⽐如⼀组关键字都在[0,99]之间那么我们开⼀个100个数的数组每个关键字的值直接就是存储位置的下标。再⽐如⼀组关键字值都在[a,z]的⼩写字⺟那么我们开⼀个26个数的数组每个关键字acsii码-a ascii码就是存储位置的下标。也就是说直接定址法本质就是⽤关键字计算出⼀个绝对位置或者相对位置。计数排序也用的题目class Solution { public: int firstUniqChar(string s) { // 每个字⺟的ascii码-a的ascii码作为下标映射到count数组数组中存储出现的次数 int count[26] {0}; // 统计次数 for(auto ch : s) { count[ch-a]; } for(size_t i 0; i s.size(); i) { if(count[s[i]-a] 1) return i; } return -1; } }另一个题目class Solution { public: vectorstring uncommonFromSentences(string s1, string s2) { stringstream ss1(s1),ss2(s2); unordered_mapstring,int cnt; string word; while(ss1word) { cnt[word]; } while(ss2word) { cnt[word]; } vectorstring result; for(auto x:cnt) { if(x.second1) { result.push_back(x.first); } } return result; } };(2)哈希冲突直接定址法的缺点也⾮常明显当关键字的范围⽐较分散时就很浪费内存甚⾄内存不够⽤。假设我们只有数据范围是[0, 9999]的N个值我们要映射到⼀个M个空间的数组中(⼀般情况下M N)那么就要借助哈希函数(hash function)hf关键字key被放到数组的h(key)位置这⾥要注意的是h(key)计算出的值必须在[0, M)之间。这⾥存在的⼀个问题就是两个不同的key可能会映射到同⼀个位置去这种问题我们叫做哈希冲突或者哈希碰撞。理想情况是找出⼀个好的哈希函数避免冲突但是实际场景中冲突是不可避免的所以我们尽可能设计出优秀的哈希函数减少冲突的次数同时也要去设计出解决冲突的⽅案。(3)负载因子假设哈希表中已经映射存储了N个值哈希表的⼤⼩为M那么负载因子N/M 负载因⼦有些地⽅也翻译为载荷因⼦/装载因⼦等他的英⽂为load factor。负载因⼦越⼤哈希冲突的概率越⾼空间利⽤率越⾼负载因⼦越⼩哈希冲突的概率越低空间利⽤率越低(4)将关键字转换成整数我们将关键字映射到数组中位置⼀般是整数好做映射计算如果不是整数我们要想办法转换成整数这个细节我们后⾯代码实现中再进⾏细节展⽰。下⾯哈希函数部分我们讨论时如果关键字不是整数那么我们讨论的Key是关键字转换成的整数。(5)哈希函数⼀个好的哈希函数应该让N个关键字被等概率的均匀的散列分布到哈希表的M个空间中但是实际中却很难做到但是我们要尽量往这个⽅向去考量设计。(5)1.除法散列法/除留余数法除法散列法也叫做除留余数法顾名思义假设哈希表的⼤⼩为M那么通过key除以M的余数作映射位置的下标也就是哈希函数为h(key) key % M。当使⽤除法散列法时要尽量避免M为某些值如2的幂10的幂等。如果是 2^x那么key %本质相当于保留key的后X位那么后x位相同的值计算出的哈希值都是⼀样的就冲突了。如 {63 , 31}看起来没有关联的值如果M是16也就是2^4 那么计算出的哈希值都是15因为63的⼆进制后8位是 0011111131的⼆进制后8位是 00011111。如果是10^x就更明显了保留的都是10进值的后x位如{112, 12312}如果M是100也就是10^2 那么计算出的哈希值都是12。当使⽤除法散列法时建议M取不太接近2的整数次幂的⼀个质数(素数)。需要说明的是实践中也是⼋仙过海各显神通Java的HashMap采⽤除法散列法时就是2的整数次幂做哈希表的⼤⼩M这样玩的话就不⽤取模⽽可以直接位运算相对⽽⾔位运算⽐模更⾼效⼀些。但是他不是单纯的去取模⽐如M是2^16次⽅本质是取后16位那么⽤key’ key16然后把key和key 异或的结果作为哈希值。也就是说我们映射出的值还是在[0,M)范围内但是尽量让key所有的位都参与计算这样映射出的哈希值更均匀⼀些即可。所以我们上⾯建议M取不太接近2的整数次幂的⼀个质数的理论是⼤多数数据结构书籍中写的理论吗但是实践中灵活运⽤抓住本质⽽不能死读书。(5)2.乘法散列法乘法散列法对哈希表⼤⼩M没有要求他的⼤思路第⼀步⽤关键字 K 乘上常数 A (0A1)并抽取出 k*A 的⼩数部分。第⼆步后再⽤M乘以k*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。(5)3.全域散列法如果存在⼀个恶意的对⼿他针对我们提供的散列函数特意构造出⼀个发⽣严重冲突的数据集⽐如让所有关键字全部落⼊同⼀个位置中。这种情况是可以存在的只要散列函数是公开且确定的就可以实现此攻击。解决⽅法⾃然是⻅招拆招给散列函数增加随机性攻击者就⽆法找出定可以导致最坏情况的数据。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了。还有其他方法比如平⽅取中法、折叠法、随机数法、数学分析法等2.处理哈希冲突实践中哈希表⼀般还是选择除法散列法作为哈希函数当然哈希表⽆论选择什么哈希函数也避免不了冲突那么插⼊数据时如何解决冲突呢主要有两种两种⽅法开放定址法和链地址法。(1)开放定址法在开放定址法中所有的元素都放到哈希表⾥当⼀个关键字key⽤哈希函数计算出的位置冲突了则按照某种规则找到⼀个没有存储数据的位置进⾏存储开放定址法中负载因⼦⼀定是⼩于的。这⾥的规则有三种线性探测、⼆次探测、双重探测。线性探测从发⽣冲突的位置开始依次线性向后探测直到寻找到下⼀个没有存储数据的位置为⽌如果⾛到哈希表尾则回绕到哈希表头的位置。h(key) hash0 key % Mhash0位置冲突了则线性探测公式为hc(key, i) hashi (hash0 i) % M i {1, 2, 3, ..., M - 1}因为负载因⼦⼩于1则最多探测M-1次⼀定能找到⼀个存储key的位置。线性探测的⽐较简单且容易实现线性探测的问题假设hash0位置连续冲突hash0hash1hash2位置已经存储数据了后续映射到hash0hash1hash2hash3的值都会争夺hash3位置这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题。下⾯演⽰ {19,30,5,36,13,20,21,12} 等这⼀组值映射到M11的表中。二次探测从发⽣冲突的位置开始依次左右按⼆次⽅跳跃式探测直到寻找到下⼀个没有存储数据的位置为⽌如果往右⾛到哈希表尾则回绕到哈希表头的位置如果往左⾛到哈希表头则回绕到哈希表尾的位置h(key) hash0 key % M hash0位置冲突了则⼆次探测公式为hc(key, i) hashi (hash0 ± i^2) % M i {1, 2, 3, ...,M/2 }⼆次探测当 hashi (hash0 - i^2)%M 时当hashi0时需要hashi M下⾯演⽰ {19,30,52,63,11,22} 等这⼀组值映射到M11的表中。双重散列第⼀个哈希函数计算出的值发⽣冲突使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值不断往后探测直到寻找到下⼀个没有存储数据的位置为⽌。h1(key) hash0 key % Mhash0位置冲突了则双重探测公式为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互质是因为根据固定的偏移量所寻址的所有位置将形成⼀个群若最⼤公约数p gcd(M, h1(key)) 1 那么所能寻址的位置的个数为M/P M 使得对于⼀个关键字来说⽆法充分利⽤整个散列表。举例来说若初始探查位置为1偏移量为3整个散列表⼤⼩为12那么所能寻址的位置为{1, 4, 7, 10}寻址个数为12/gcd(12, 3) 4下⾯演⽰ {19,30,52,74} 等这⼀组值映射到M11的表中设 h2(key) key%10 1//开方定址法的哈希表结构 enum State { EXIST, EMPTY, DELETE }; templateclass K, class V struct HashData { pairK, V _kv; State _state EMPTY; }; templateclass K, class V class HashTable { private: vectorHashDataK, V _tables; size_t _n 0; // 表中存储数据个数 };要注意的是这⾥需要给每个存储值的位置加⼀个状态标识否则删除⼀些值以后会影响后⾯冲突的值的查找。如下图我们删除30会导致查找20失败当我们给每个位置加⼀个状态标识{EXIST,DELETE,EMPTY}删除30就不用删除值而是把状态改成DELETE,那么查找20时遇到EMPTY才能就找到20.扩容这⾥我们哈希表负载因⼦控制在0.7当负载因⼦到0.7以后我们就需要扩容了我们还是按照2倍扩容但是同时我们要保持哈希表⼤⼩是⼀个质数第⼀个是质数2倍后就不是质数了。那么如何解决了⼀种⽅案就是上⾯1.4.1除法散列中我们讲的Java HashMap的使⽤2的整数幂但是计算时不能直接取模的改进⽅法。另外⼀种⽅案是sgi版本的哈希表使⽤的⽅法给了⼀个近似2倍的质数表每次去质数表获取扩容后的⼤⼩。inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. 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; }key不能取模的问题当key是string/Date等类型时key不能取模那么我们需要给HashTable增加⼀个仿函数这个仿函数⽀持把key转换成⼀个可以取模的整形如果key可以转换为整形并且不容易冲突那么这个仿函数就⽤默认参数即可如果这个Key不能转换为整形我们就需要⾃⼰实现⼀个仿函数传给这个参数实现这个仿函数的要求就是尽量key的每值都参与到计算中让不同的key转换出的整形值不同。string做哈希表的key⾮常常⻅所以我们可以考虑把string特化⼀下。templateclass K struct 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 key) { size_t hash 0; for (auto e : key) { hash * 131; hash e; } return hash; } }; templateclass K, class V, class Hash HashFuncK class HashTable { public: private: vectorHashDataK, V _tables; size_t _n 0; // 表中存储数据个数 }整体代码namespace open_address { enum State { EXIST, EMPTY, DELETE }; templateclass K, class V struct HashData { pairK, V _kv; State _state EMPTY; }; templateclass K, class V, class Hash HashFuncK class HashTable { public: inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. 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; } HashTable() { _tables.resize(__stl_next_prime(0)); } bool Insert(const pairK, V kv) { if (Find(kv.first)) return false; // 负载因⼦⼤于0.7就扩容 if (_n * 10 / _tables.size() 7) { // 这⾥利⽤类似深拷⻉现代写法的思想插⼊后交换解决 HashTableK, V, Hash newHT; newHT._tables.resize(__stl_next_prime(_tables.size()1)); for (size_t i 0; i _tables.size(); i) { if (_tables[i]._state EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } Hash hash; size_t hash0 hash(kv.first) % _tables.size(); size_t hashi hash0; size_t i 1; while (_tables[hashi]._state EXIST) { // 线性探测 hashi (hash0 i) % _tables.size(); // ⼆次探测就变成 - i^2 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; 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; } bool Erase(const K key) { HashDataK, V* ret Find(key); if (ret nullptr) { return false; } else{ ret-_state DELETE; --_n; return true; } } private: vectorHashDataK, V _tables; size_t _n 0; // 表中存储数据个数 }; }(2)链地址法扩容开放定址法负载因⼦必须⼩于1链地址法的负载因⼦就没有限制了可以⼤于1。负载因⼦越⼤哈希冲突的概率越⾼空间利⽤率越⾼负载因⼦越⼩哈希冲突的概率越低空间利⽤率越低stl中unordered_xxx的最⼤负载因⼦基本控制在1⼤于1就扩容我们下⾯实现也使⽤这个⽅式。极端场景如果极端场景下某个桶特别⻓怎么办其实我们可以考虑使⽤全域散列法这样就不容易被针对了。但是假设不是被针对了⽤了全域散列法但是偶然情况下某个桶很⻓查找效率很低怎么办这⾥在Java8的HashMap中当桶的⻓度超过⼀定阀值(8)时就把链表转换成红⿊树。⼀般情况下不断扩容单个桶很⻓的场景还是⽐较少的下⾯我们实现就不搞这么复杂了这个解决极端场景的思路⼤家了解⼀下。namespace hash_bucket { 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 HashFuncK class HashTable { typedef HashNodeK, V Node; 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; } public: HashTable() { _tables.resize(__stl_next_prime(0), nullptr); } / / 拷⻉构造和赋值拷⻉需要实现深拷⻉有兴趣的同学可以⾃⾏实现 ~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 hs; size_t hashi hs(kv.first) % _tables.size(); // 负载因⼦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* newtables(__stl_next_prime(_tables.size()1), nullptr); for (size_t i 0; i _tables.size(); i) { Node* cur _tables[i]; while (cur) { Node* next cur-_next; // 旧表中节点挪动新表重新映射的位置 size_t hashi hs(cur-_kv.first) % newtables.size(); // 头插到新表 cur-_next newtables[hashi]; newtables[hashi] cur; cur next; } _tables[i] nullptr; } _tables.swap(newtables); } // 头插 Node* newnode new Node(kv); newnode-_next _tables[hashi]; _tables[hashi] newnode; _n; return true; } 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; } 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; } private: vectorNode* _tables; // 指针数组 size_t _n 0; // 表中存储数据个数 }; }
