一、unordered_set系列的使用1.1 unordered_set和unordered_map参考文档unordered_set - C Reference1.2 unordered_set类的介绍unordered_set声明如下Key是底层关键字类型unordered_set默认要求Key支持转换为整型类型如果不支持或与需求不符可以自己实现仿函数传给第二个参数unordered_set默认要求Key支持相等比较如果不支持或与需求不符可以自己实现仿函数传给第三个参数unordered_set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第四个参数unordered_set底层用哈希桶实现增删查效率是O1迭代器遍历无序template class Key, // unordered_set::key_type/value_type class Hash hashKey, // unordered_set::hasher class Pred equal_toKey, // unordered_set::key_equal class Alloc allocatorKey // unordered_set::allocator_type class unordered_set;1.3 unordered_set和set的差异unordered_set和set的增删查使用一模一样unordered_set要求Key支持等于比较set要求Key支持小于比较而且unordered_set要求Key能转换为整型类型set的迭代器是双向迭代器unordered_set的迭代器是单向迭代器所以它不支持倒着遍历,set的底层是红黑树迭代器遍历是有序去重unordered_set的底层是哈希表迭代器遍历是无序去重大多数场景下unordered_set增删查改的效率更高set增删查改的效率是OlogN哈希表增删查改效率是O11.4 unordered_map和map的差异unordered_map和map的增删查使用一模一样unordered_map要求Key支持等于比较map要求Key支持小于比较而且unordered_map要求Key能转换为整型类型map的迭代器是双向迭代器unordered_map的迭代器是单向迭代器所以它不支持倒着遍历,map的底层是红黑树迭代器遍历是有序去重unordered_map的底层是哈希表迭代器遍历是无序去重大多数场景下unordered_map增删查改的效率更高map增删查改的效率是OlogN哈希表增删查改效率是O1mapped_type at ( const key_type k ); const mapped_type at ( const key_type k ) const;与[]不同at函数也可以通过键值访问value但是当键值不存在时不会进行插入而是会抛异常map在C11以后也增加了at函数template class Key, // unordered_map::key_type class T, // unordered_map::mapped_type class Hash hashKey, // unordered_map::hasher class Pred equal_toKey, // unordered_map::key_equal class Alloc allocator pairconst Key,T // unordered_map::allocator_type class unordered_map;二、哈希表实现2.1 哈希概念哈希又称散列是一种组织数据的方式。散列的核心思想是通过哈希函数将关键字映射到对应的存储位置从而实现高效的插入、查找和删除操作。2.2 直接定址法当关键字范围比较集中且是整型数据时直接定址法是非常高效的方法其核心思想是取关键字的某个线性函数值作为存储地址即地址 关键字 × a ba、b 为常数。这种方法简单直接不会产生冲突但要求关键字的取值范围较小且连续否则会造成大量空间浪费。以下这道题就是典型的使用直接定址法解决的字符串中的第一个唯一字符int firstUniqChar(string s) { //记录字符串中每个字符出现的次数 int cnt[26]{0}; for(int i0;is.size();i) cnt[s[i]-a]; //遍历字符串找第一个不重复的字母 for(int i0;is.size();i) { if(cnt[s[i]-a]1)return i; } return -1; }2.3 哈希冲突哈希冲突又称哈希碰撞是指两个不同的关键字经过哈希函数计算后得到了相同的存储地址。由于哈希函数通常将无限的关键字空间映射到有限的地址空间冲突是不可避免的。例如当关键字为 5 和 15哈希函数为取模运算关键字 % 10时两者都会映射到地址 5从而产生冲突。解决哈希冲突的常见方法主要有以下两种在实际使用中为了减少哈希冲突通常会选择合适的哈希函数并让哈希表的负载因子已存元素个数 / 桶的个数保持在一个合理范围内必要时进行扩容或重新哈希。2.4 负载因子假设哈希表中已经映射存储了N个值哈希表大小为M负载因子N/M。负载因子越大哈希冲突概率越高空间利用率越高负载因子越小哈希冲突概率越低空间利用率越低。2.5 将关键字转为整数我们将关键字映射到数组中一般是整数好做映射计算如果是非整数要想办法转换为整数这个细节将在后面的代码中展示2.6 哈希函数一个好的哈希函数应该让N个关键字等概率地均匀散列分布在哈希表的M个空间中2.6.1.1 除法散列法/除留余数法除留余数法又称除法散列法是最常用的一种哈希函数构造方法其核心思想是用关键字除以某个不大于哈希表长度的正整数取其余数作为存储地址即地址 关键字 % MM 为哈希表长度。例如当哈希表长度为 10关键字为 23 时23 % 10 3因此关键字 23 被映射到地址 3。除留余数法的优点是实现简单、计算速度快适用于大多数场景。但它的效果与哈希表长度 M 的选取密切相关如果 M 取得不合适例如 M 是偶数或含有较多小因子就容易导致关键字分布不均匀从而加剧哈希冲突。因此在实际应用中通常建议将 M 取为一个较大的质数素数不建议取2的幂、10的幂这样可以减少关键字之间的规律性关联使散列结果更加均匀。需要说明的是实践中也是八仙过海各显神通Java的HashMap采用除留余数法是表的大小就是2的幂它不是单纯的取模比如表的大小为2^16,本质直接取模就是取key值二进制数的后16位若用keykey16,然后把key与key‘异或的值作为哈希值。这样尽量让key的每一位都参与运算映射出的哈希值更均匀一些2.6.1.2 乘法散列法乘法散列法又称乘法取整法是另一种常用的哈希函数构造方法其核心思想是先用关键字乘以一个常数再取乘积的小数部分最后乘以哈希表长度并向下取整得到存储地址。具体步骤如下第一步选择一个合适的常数 A0 A 1通常取黄金分割比的无理数部分即 A (√5 - 1) / 2 ≈ 0.6180339887。这个值在数学上被证明能使散列结果分布得比较均匀。第二步计算关键字 key 与常数 A 的乘积即 key × A得到一个带有小数部分的实数。第三步取出该乘积的小数部分即 frac(key × A) key × A - ⌊key × A⌋其中 ⌊⌋ 表示向下取整。第四步将小数部分乘以哈希表长度 M再向下取整得到最终的存储地址即地址 ⌊M × frac(key × A)⌋。例如设哈希表长度 M 100常数 A ≈ 0.618关键字 key 23。先计算 23 × 0.618 14.214小数部分为 0.214再计算 100 × 0.214 21.4向下取整得到地址 21因此关键字 23 被映射到地址 21。乘法散列法的优点是哈希表长度 M 的选取比较灵活不要求 M 必须是质数即使 M 取 2 的幂也能获得较好的分布效果同时它的计算只涉及乘法和取整操作速度较快。不过乘法散列法的效果对常数 A 的选取比较敏感A 选得不好会导致散列结果不够均匀因此实际应用中通常采用黄金分割比作为 A 的取值。2.6.1.3 全域散列法全域散列法又称通用散列法是一种通过随机化手段来对抗恶意输入、降低哈希冲突概率的哈希函数构造方法。它的核心思想是在程序运行开始时从一个预先设计好的哈希函数族中随机选取一个哈希函数作为本次使用的哈希函数。由于攻击者无法预知具体选中的是哪一个函数因此很难构造出一组让所有关键字都映射到同一地址的恶意数据从而有效避免最坏情况的发生。具体来说全域散列法需要先构造一个哈希函数族 H该函数族中的每一个哈希函数都能将关键字空间映射到哈希表的 M 个地址上。函数族 H 满足全域性质对于任意两个不同的关键字 x 和 y从 H 中随机选取一个哈希函数 h使得 h(x) h(y) 的概率不超过 1 / M。也就是说任意两个不同关键字发生冲突的概率被控制在 1 / M 以内这与随机均匀散列的冲突概率一致因此称为全域散列。一个经典的全域散列函数族构造方法如下设哈希表长度为 MM 为质数关键字 key 可以表示成 r 1 位进制数即 key (k₀, k₁, ..., kᵣ)。从 0 到 M - 1 之间随机选取 r 1 个系数 a₀, a₁, ..., aᵣ则哈希函数定义为h(key) (a₀ * k₀ a₁ * k₁ ... aᵣ * kᵣ) mod M其中 a₀, a₁, ..., aᵣ 是随机选取的系数。可以证明这样构造出的函数族满足全域性质即任意两个不同关键字发生冲突的概率不超过 1 / M。需要注意的是每次初始化哈希表时随机选取全域散列函数组中的一个散列函数使用后续增删查改都固定用这个散列函数2.7处理哈希冲突实践中哈希表一般选择除法散列法作为哈希函数处理哈希冲突的方法一般有两种开放定址法、链地址法2.7.1 开放定址法在开放定址法中所有的元素都放到哈希表⾥当⼀个关键字key⽤哈希函数计算出的位置冲突了则按照某种规则找到⼀个没有存储数据的位置进⾏存储开放定址法中负载因⼦⼀定是⼩于1的。这⾥的规则有三种线性探测、⼆次探测、双重探测。线性探测从发生哈希冲突的位置依次线性向后探测直到寻到下一个未存储数据的位置走到哈希表尾就绕回到表头位置hash0key%M若hash0位置冲突则线性探测公式为hckeyihashihash0i%Mi{123...M-1}最多探测M-1次一定能找到存储key的位置线性探测的⽐较简单且容易实现线性探测的问题假设hash0位置连续冲突hash0hash1hash2位置已经存储数据了后续映射到hash0hash1hash2hash3的值都会争夺hash3位置这种现象叫做群集/堆积。下⾯的⼆次探测可以⼀定程度改善这个问题。二次探测从发⽣冲突的位置开始依次左右按⼆次⽅跳跃式探测直到寻找到下⼀个没有存储数据的位置为⽌如果往右⾛到哈希表尾则回绕到哈希表头的位置如果往左⾛到哈希表头则回绕到哈希表尾的位置hash0位置冲突二次探测公式为hckeyihashihash0/-i^2)%M,i{1,2,3...,M/2}当hashi0时需要hashiM双重散列第⼀个哈希函数计算出的值发⽣冲突使⽤第⼆个哈希函数计算出⼀个跟key相关的偏移量值不断往后探测直到寻找到下⼀个没有存储数据的位置为⽌。若hash0位置冲突则双重探测公式为hckeyihashihash0i*h2(key)%Mi{123...M-1}要求h2key)M,h2(key)与M互为质数有两种简单取值方法1.M为2的幂时h2key从[0,M-1]任选一个奇数2.当M为质数时h2keykey%M-112.7.2 开放定址法代码实现#pragma once #includeiostream #includecstring #includevector using namespace std; templateclass T struct HashCmp { size_t operator()(const T t) { return (size_t)t; } }; template struct HashCmpstring { size_t operator()(const string s) { size_t ret 0; for (const auto e : s) { ret * 131; ret e; } return ret; } }; enum Status { EXIST, EMPTY, DELETE }; templateclass K,class V struct HashData { pairK, V _kv; Status _s; HashData(const pairK,V kvpairK,V()) :_kv(kv) ,_s(EMPTY) { } }; templateclass K,class V,class Hash HashCmpK class HashMap { typedef HashDataK, V Data; public: HashMap(size_t sz11) { _map.resize(sz); } bool Insert(const pairK, V kv) { Hash hs; if (Find(kv.first)) return false; //扩容 if ((double)_n (double)_map.size()*0.7) { HashMap newmap(_map.size() * 2); for (int i 0; i _map.size(); i) { if (_map[i]._s EXIST) newmap.Insert(_map[i]._kv); } _map.swap(newmap._map); } size_t hash0 hs(kv.first) % _map.size(); size_t hashi hash0; int i 1; while (_map[hashi]._s EXIST) { hashi (hashi i) % _map.size(); i; } //找到空位置可插入 _map[hashi]._kv kv; _map[hashi]._s EXIST; _n; return true; } Data* Find(const K key) { Hash hs; size_t hashi hs(key) % _map.size(); while (_map[hashi]._s ! EMPTY) { if (_map[hashi]._kv.first key) return _map[hashi]; hashi(hashi1)%_map.size(); } return nullptr; } bool Erase(const K key) { Data* d Find(key); if (!d) return false; else { d-_s DELETE; --_n; return true; } } private: vectorData _map;//表 int _n;//有效数据个数 };2.7.3 链地址法链地址法中所有的数据不再直接存储在哈希表中哈希表存储一个指针没有数据映射这个位置时这个指针为空有多个数据映射时把这些冲突的数据连接为一个链表挂在哈希表这个位置下面也叫哈希桶#pragma once #includeiostream #includecstring #includevector using namespace std; templateclass T struct HashCmp { size_t operator()(const T t) { return (size_t)t; } }; template struct HashCmpstring { size_t operator()(const string s) { size_t ret 0; for (const auto e : s) { ret * 131; ret e; } return ret; } }; namespace Hash_bucket { templateclass K, class V struct HashNode { pairK, V _kv; HashNode* _next; HashNode(const pairK,V kvpairK,V()) :_kv(kv) ,_next(nullptr) { } }; templateclass K,class V,class HashHashCmpK class Hashmap { 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: Hashmap() { _map.resize(__stl_next_prime(0), nullptr); } ~Hashmap() { for (size_t i 0; i _map.size(); i) { Node* cur _map[i]; while (cur) { Node* next cur-_next; delete cur; cur next; } _map[i] nullptr; } } bool Insert(const pairK, V kv) { Hash hs; if (Find(kv.first)) return false; //扩容 if (_n _map.size()) { vectorNode* newmap(__stl_next_prime(_map.size() 1), nullptr); for (size_t i 0; i _map.size(); i) { Node* cur _map[i]; while (cur) { size_t hash0 hs(cur-_kv.first) % newmap.size(); Node* next cur-_next; cur-_next newmap[hash0]; newmap[hash0] cur; cur next; } _map[i] nullptr; } _map.swap(newmap); } size_t hash0 hs(kv.first) % _map.size(); Node* newnode new Node(kv); newnode-_next _map[hash0]; _map[hash0] newnode; _n; return true; } Node* Find(const K key) { Hash hs; size_t hash0 hs(key) % _map.size(); Node* cur _map[hash0]; while (cur) { if (cur-_kv.first key) return cur; else cur cur-_next; } return nullptr; } bool Erase(const K key) { Hash hs; size_t hash0 hs(key) % _map.size(); Node* cur _map[hash0]; Node* parent nullptr; while (cur) { if (cur-_kv.first key) { Node* next cur-_next; if (parent) parent- _next next; else _map[hash0] next; delete cur; _n--; return true; } parent cur; cur cur-_next; } return false; } private: vectorNode* _map; size_t _n; }; }