一、哈希表相关概念与特性总结1. 什么是哈希表哈希表散列表通过哈希函数把关键字 key 映射到数组下标位置直接访问元素理想情况下查找、插入、删除时间复杂度接近 \(O(1)\)。数组叫做哈希桶数组数组每个位置叫桶 (bucket)。 公式hash(key) 下标2. 哈希冲突不同的 key 经过哈希函数计算得到同一个数组下标就是哈希冲突。 不可能设计完美哈希函数冲突不可避免。常见解决冲突方案开放定址法冲突就找下一个空位置线性探测、二次探测。缺点删除麻烦容易堆积冲突。链地址法 (哈希桶)STLunordered_xx使用的方案。 每个桶里面挂一条链表冲突的元素直接链在同一个桶的链表上。3. 负载因子 load_factor\(负载因子 \frac{有效元素个数}{桶数组总大小}\)负载因子越大冲突概率越高链表越长效率下降。STL 中unordered容器负载因子阈值默认是1超过阈值就要扩容rehash。rehash 扩容做两件事1. 开辟更大的桶数组一般找下一个质数质数降低冲突 2. 遍历旧表全部元素重新计算哈希值搬迁到新数组释放旧空间。注意rehash 之后元素迭代器会失效。4. 哈希函数与仿函数C 内置类型int、stringSTL 提供默认哈希仿函数hashT。 自定义类型必须自己提供哈希仿函数把对象转成 size_t 整数。5.unordered_set 与 unordered_map 对比表格容器存储内容key 是否唯一key 是否可修改unordered_set只存 keykey 唯一key 不能修改unordered_map存 pairKey,Tkey 唯一key 不能修改value 可修改unordered_set相当于unordered_map只使用 keyvalue 无意义。所以 STL 内部unordered_set和unordered_map共用同一套哈希表底层只是传入的数据类型不同。6. 特性总结无序元素不排序遍历顺序和插入顺序无关key 不允许重复底层链地址哈希桶平均\(O(1)\)增删查最坏退化\(O(n)\)全部冲突挂一条链表迭代器不是双向迭代器不支持/--的有序遍历不支持lower_boundrehash 会导致迭代器失效二、模拟实现整体思路STL 源码思路封装一个通用哈希表HashTable。unordered_setK底层哈希表存Kvalue 就是 keyunordered_mapK,V底层哈希表存pairconst K,V核心组件哈希节点链表节点存数据 next 指针哈希桶数组vectorNode*仿函数 1取 key 仿函数 —— 从存储的元素中取出 keyset 取本身map 取 pair.first仿函数 2哈希函数仿函数 —— key 转 size_t 下标仿函数 3相等比较仿函数 —— 判断两个 key 是否相等哈希值相等不代表 key 相等必须判等核心接口insert、find、erase、rehash、operator []map 独有1. 哈希节点定义链地址templateclass T struct HashNode { T _data; HashNode* _next; HashNode(const T data) :_data(data), _next(nullptr) {} };T对于 set 就是K对于 map 就是pairconst K,V。2. 三个关键仿函数模拟实现重点① 获取 key 仿函数GetKey同一个 HashTable 要同时给 set 和 map 用存储的数据类型不一样需要从存储对象拿到 key。// unordered_set数据就是key直接返回 templateclass K struct SetGetKey { const K operator()(const K key) { return key; } }; // unordered_map存储pair返回pair.first templateclass K,class V struct MapGetKey { const K operator()(const pairconst K,V kv) { return kv.first; } };② HashFunc 哈希仿函数key 转 size_t 下标内置类型直接强转字符串需要特殊处理。// 针对int templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; // string特化哈希 template struct HashFuncstring { size_t operator()(const string s) { size_t hash 0; for(auto ch : s) { hash hash * 131 ch; } return hash; } };自定义类型使用者需要自己写 HashFunc 仿函数。③ equal 相等比较哈希值相同 ≠ key 相同。同一个桶链表遍历的时候必须用 key 判断是否相等不能只对比哈希值。3. 通用哈希表模板设计templateclass T, class KeyOfT, class Hash class HashTable { public: typedef HashNodeT Node; private: vectorNode* _buckets; //哈希桶数组 size_t _size; //有效元素个数 //...接口 };T容器存储元素set 为 Kmap 为 pairconst K,VKeyOfT仿函数从 T 取出 keyHash哈希仿函数key→size_t4. 核心接口要点分析(1) insert 插入步骤先调用find(key)key 已经存在直接返回key 唯一判断负载因子_size / _buckets.size() 1执行 rehash 扩容使用哈希函数算出哈希值对桶数组大小取模得到桶下标size_t idx Hash()(key) % _buckets.size();new 新节点头插法插入该桶的链表STL 旧版本头插新版本有些改动_size注意扩容要处理空桶桶数组不能为 0初始给一个最小容量。(2) rehash 扩容要点开辟新的 vector 桶数组容量选质数减少冲突遍历旧桶数组每一个桶遍历桶内整条链表每个旧节点用新桶大小重新计算下标摘节点头插到新桶旧 vector 生命周期结束自动释放不要重新 new 节点直接搬迁节点不拷贝对象移动节点指针效率高。❗坑不要重新 new 节点搬迁原有节点否则拷贝代价巨大。(3) find 查找key 计算下标找到对应的桶遍历该桶下链表调用KeyOfT()拿到节点数据的 key和目标 key 比较找到返回节点指针找不到返回 nullptr只在同一个桶内遍历不用遍历整个哈希表。(4) erase 删除find 找到节点同时保存前驱节点链表删除节点释放节点_size--链地址法删除简单不需要像开放定址法做标记。(5) operator [] 仅 unordered_map 拥有map[key]语义key 存在返回 value 引用不存在就插入默认构造的 pair。 底层调用insert拿到迭代器返回it-second引用。 set 不需要operator[]因为没有 value。5. 模拟实现 unordered_set包装层内部聚合 HashTable把参数传递给底层哈希表。templateclass K, class Hash HashFuncK class MyUnorderedSet { public: //底层哈希表存储类型TK取key仿函数SetGetKey bool insert(const K k) { return _ht.Insert(k); } bool find(const K k) { return _ht.Find(k) ! nullptr; } bool erase(const K k) { return _ht.Erase(k); } private: HashTableK, SetGetKeyK, Hash _ht; };6. 模拟实现 unordered_maptemplateclass K, class V, class Hash HashFuncK class MyUnorderedMap { public: bool insert(const pairconst K,V kv) { return _ht.Insert(kv); } V operator[](const K key) { pairdecltype(_ht.begin()),bool ret _ht.Insert({key,V()}); return ret.first-_data.second; } bool erase(const K key) { return _ht.Erase(key); } private: HashTablepairconst K,V, MapGetKeyK,V, Hash _ht; };关键点map 存储pairconst K,Vkey 是 const防止用户修改 key一旦修改 key 哈希值失效整个哈希表结构错乱。三、重点难点梳理博客重点1. 为什么 unordered_set 和 unordered_map 可以复用同一个 HashTable存储的数据类型 T 不同set 存 Kmap 存 pair。通过仿函数 KeyOfT 做解耦统一从存储对象拿到 key不需要写两份哈希表代码。这是 STL 泛型编程精髓。2. 哈希冲突处理链地址法优缺点✅优点删除简单没有堆积问题rehash 直接搬迁节点不需要拷贝数据。 ❌缺点需要额外开辟节点有指针开销极端冲突退化成链表查找\(O(n)\)。3. 仿函数三处用途总结KeyOfT从存储的 T 类型提取 key隔离 set/map 存储差异。Hash把任意 key 转成 size_t 哈希整数自定义类型必须提供。equal 比较哈希值相同不等于 key 相同链表遍历必须真实 key 判等。4.rehash 容易踩坑不是简单扩大两倍STL 选用质数做桶大小降低冲突概率。rehash 是移动节点不是拷贝数据避免拷贝大对象。rehash 后迭代器全部失效因为节点被搬到不同桶。5.key 不能修改的原因哈希表所有位置依靠 key 的哈希值定位。 一旦 key 被修改节点实际存储位置和计算出的下标不匹配find 永远找不到元素。 所以unordered_map的 pair 的 first 是const Kset 的 key 也是不可修改。四、完整可运行简易代码汇总#includeiostream #includevector #includestring using namespace std; //哈希节点 templateclass T struct HashNode { T _data; HashNode* _next; HashNode(const T data):_data(data),_next(nullptr){} }; //set取key仿函数 templateclass K struct SetGetKey { const K operator()(const K k){return k;} }; //map取key仿函数 templateclass K,class V struct MapGetKey { const K operator()(const pairconst K,V kv){return kv.first;} }; //哈希仿函数 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 hash0; for(auto c:s) hashhash*131c; return hash; } }; //通用哈希表 templateclass T,class KeyOfT,class Hash class HashTable { public: typedef HashNodeT Node; HashTable():_size(0) { _buckets.resize(10,nullptr); } Node* Find(const KeyOfT key) { Hash hf; KeyOfT getkey; size_t idxhf(key)%_buckets.size(); Node* cur_buckets[idx]; while(cur) { if(getkey(cur-_data)key) return cur; curcur-_next; } return nullptr; } bool Insert(const T data) { KeyOfT getkey; auto keygetkey(data); if(Find(key)) return false; //负载因子1就扩容 if(_size _buckets.size()) { size_t newCap _buckets.size()*2; vectorNode* newBuckets(newCap,nullptr); for(size_t i0;i_buckets.size();i) { Node* cur_buckets[i]; while(cur) { Node* nextcur-_next; size_t idxHash()(getkey(cur-_data))%newCap; cur-_nextnewBuckets[idx]; newBuckets[idx]cur; curnext; } } _buckets.swap(newBuckets); } size_t idxHash()(key)%_buckets.size(); Node* newNodenew Node(data); newNode-_next_buckets[idx]; _buckets[idx]newNode; _size; return true; } bool Erase(const KeyOfT key) { Hash hf; KeyOfT getkey; size_t idxhf(key)%_buckets.size(); Node* cur_buckets[idx]; Node* prevnullptr; while(cur) { if(getkey(cur-_data)key) { if(prevnullptr) { _buckets[idx]cur-_next; } else { prev-_nextcur-_next; } delete cur; _size--; return true; } prevcur; curcur-_next; } return false; } private: vectorNode* _buckets; size_t _size; }; //模拟unordered_set templateclass K,class HashHashFuncK class MyUnorderedSet { public: bool insert(const K k) { return _ht.Insert(k); } bool find(const K k) { return _ht.Find(k)!nullptr; } bool erase(const K k) { return _ht.Erase(k); } private: HashTableK,SetGetKeyK,Hash _ht; }; //模拟unordered_map templateclass K,class V,class HashHashFuncK class MyUnorderedMap { public: bool insert(const pairconst K,V kv) { return _ht.Insert(kv); } V operator[](const K key) { _ht.Insert({key,V()}); Node* node_ht.Find(key); return node-_data.second; } bool erase(const K key) { return _ht.Erase(key); } private: typedef HashNodepairconst K,V Node; HashTablepairconst K,V,MapGetKeyK,V,Hash _ht; }; //测试 int main() { MyUnorderedSetint s; s.insert(1); s.insert(3); couts.find(3)endl; s.erase(3); couts.find(3)endl; MyUnorderedMapstring,int mp; mp[apple]100; coutmp[apple]endl; return 0; }五、博客小结unordered_set、unordered_map底层是链地址法哈希表核心解决哈希冲突。STL 使用泛型 仿函数实现代码复用同一个 HashTable 支撑 set 与 map。三个仿函数分工提取 key、哈希转换、key 判等是模拟实现的核心难点。rehash 扩容、负载因子、key 禁止修改都是高频考点。
一、哈希表相关概念与特性总结1. 什么是哈希表哈希表散列表通过哈希函数把关键字 key 映射到数组下标位置直接访问元素理想情况下查找、插入、删除时间复杂度接近 \(O(1)\)。数组叫做哈希桶数组数组每个位置叫桶 (bucket)。 公式hash(key) 下标2. 哈希冲突不同的 key 经过哈希函数计算得到同一个数组下标就是哈希冲突。 不可能设计完美哈希函数冲突不可避免。常见解决冲突方案开放定址法冲突就找下一个空位置线性探测、二次探测。缺点删除麻烦容易堆积冲突。链地址法 (哈希桶)STLunordered_xx使用的方案。 每个桶里面挂一条链表冲突的元素直接链在同一个桶的链表上。3. 负载因子 load_factor\(负载因子 \frac{有效元素个数}{桶数组总大小}\)负载因子越大冲突概率越高链表越长效率下降。STL 中unordered容器负载因子阈值默认是1超过阈值就要扩容rehash。rehash 扩容做两件事1. 开辟更大的桶数组一般找下一个质数质数降低冲突 2. 遍历旧表全部元素重新计算哈希值搬迁到新数组释放旧空间。注意rehash 之后元素迭代器会失效。4. 哈希函数与仿函数C 内置类型int、stringSTL 提供默认哈希仿函数hashT。 自定义类型必须自己提供哈希仿函数把对象转成 size_t 整数。5.unordered_set 与 unordered_map 对比表格容器存储内容key 是否唯一key 是否可修改unordered_set只存 keykey 唯一key 不能修改unordered_map存 pairKey,Tkey 唯一key 不能修改value 可修改unordered_set相当于unordered_map只使用 keyvalue 无意义。所以 STL 内部unordered_set和unordered_map共用同一套哈希表底层只是传入的数据类型不同。6. 特性总结无序元素不排序遍历顺序和插入顺序无关key 不允许重复底层链地址哈希桶平均\(O(1)\)增删查最坏退化\(O(n)\)全部冲突挂一条链表迭代器不是双向迭代器不支持/--的有序遍历不支持lower_boundrehash 会导致迭代器失效二、模拟实现整体思路STL 源码思路封装一个通用哈希表HashTable。unordered_setK底层哈希表存Kvalue 就是 keyunordered_mapK,V底层哈希表存pairconst K,V核心组件哈希节点链表节点存数据 next 指针哈希桶数组vectorNode*仿函数 1取 key 仿函数 —— 从存储的元素中取出 keyset 取本身map 取 pair.first仿函数 2哈希函数仿函数 —— key 转 size_t 下标仿函数 3相等比较仿函数 —— 判断两个 key 是否相等哈希值相等不代表 key 相等必须判等核心接口insert、find、erase、rehash、operator []map 独有1. 哈希节点定义链地址templateclass T struct HashNode { T _data; HashNode* _next; HashNode(const T data) :_data(data), _next(nullptr) {} };T对于 set 就是K对于 map 就是pairconst K,V。2. 三个关键仿函数模拟实现重点① 获取 key 仿函数GetKey同一个 HashTable 要同时给 set 和 map 用存储的数据类型不一样需要从存储对象拿到 key。// unordered_set数据就是key直接返回 templateclass K struct SetGetKey { const K operator()(const K key) { return key; } }; // unordered_map存储pair返回pair.first templateclass K,class V struct MapGetKey { const K operator()(const pairconst K,V kv) { return kv.first; } };② HashFunc 哈希仿函数key 转 size_t 下标内置类型直接强转字符串需要特殊处理。// 针对int templateclass K struct HashFunc { size_t operator()(const K key) { return (size_t)key; } }; // string特化哈希 template struct HashFuncstring { size_t operator()(const string s) { size_t hash 0; for(auto ch : s) { hash hash * 131 ch; } return hash; } };自定义类型使用者需要自己写 HashFunc 仿函数。③ equal 相等比较哈希值相同 ≠ key 相同。同一个桶链表遍历的时候必须用 key 判断是否相等不能只对比哈希值。3. 通用哈希表模板设计templateclass T, class KeyOfT, class Hash class HashTable { public: typedef HashNodeT Node; private: vectorNode* _buckets; //哈希桶数组 size_t _size; //有效元素个数 //...接口 };T容器存储元素set 为 Kmap 为 pairconst K,VKeyOfT仿函数从 T 取出 keyHash哈希仿函数key→size_t4. 核心接口要点分析(1) insert 插入步骤先调用find(key)key 已经存在直接返回key 唯一判断负载因子_size / _buckets.size() 1执行 rehash 扩容使用哈希函数算出哈希值对桶数组大小取模得到桶下标size_t idx Hash()(key) % _buckets.size();new 新节点头插法插入该桶的链表STL 旧版本头插新版本有些改动_size注意扩容要处理空桶桶数组不能为 0初始给一个最小容量。(2) rehash 扩容要点开辟新的 vector 桶数组容量选质数减少冲突遍历旧桶数组每一个桶遍历桶内整条链表每个旧节点用新桶大小重新计算下标摘节点头插到新桶旧 vector 生命周期结束自动释放不要重新 new 节点直接搬迁节点不拷贝对象移动节点指针效率高。❗坑不要重新 new 节点搬迁原有节点否则拷贝代价巨大。(3) find 查找key 计算下标找到对应的桶遍历该桶下链表调用KeyOfT()拿到节点数据的 key和目标 key 比较找到返回节点指针找不到返回 nullptr只在同一个桶内遍历不用遍历整个哈希表。(4) erase 删除find 找到节点同时保存前驱节点链表删除节点释放节点_size--链地址法删除简单不需要像开放定址法做标记。(5) operator [] 仅 unordered_map 拥有map[key]语义key 存在返回 value 引用不存在就插入默认构造的 pair。 底层调用insert拿到迭代器返回it-second引用。 set 不需要operator[]因为没有 value。5. 模拟实现 unordered_set包装层内部聚合 HashTable把参数传递给底层哈希表。templateclass K, class Hash HashFuncK class MyUnorderedSet { public: //底层哈希表存储类型TK取key仿函数SetGetKey bool insert(const K k) { return _ht.Insert(k); } bool find(const K k) { return _ht.Find(k) ! nullptr; } bool erase(const K k) { return _ht.Erase(k); } private: HashTableK, SetGetKeyK, Hash _ht; };6. 模拟实现 unordered_maptemplateclass K, class V, class Hash HashFuncK class MyUnorderedMap { public: bool insert(const pairconst K,V kv) { return _ht.Insert(kv); } V operator[](const K key) { pairdecltype(_ht.begin()),bool ret _ht.Insert({key,V()}); return ret.first-_data.second; } bool erase(const K key) { return _ht.Erase(key); } private: HashTablepairconst K,V, MapGetKeyK,V, Hash _ht; };关键点map 存储pairconst K,Vkey 是 const防止用户修改 key一旦修改 key 哈希值失效整个哈希表结构错乱。三、重点难点梳理博客重点1. 为什么 unordered_set 和 unordered_map 可以复用同一个 HashTable存储的数据类型 T 不同set 存 Kmap 存 pair。通过仿函数 KeyOfT 做解耦统一从存储对象拿到 key不需要写两份哈希表代码。这是 STL 泛型编程精髓。2. 哈希冲突处理链地址法优缺点✅优点删除简单没有堆积问题rehash 直接搬迁节点不需要拷贝数据。 ❌缺点需要额外开辟节点有指针开销极端冲突退化成链表查找\(O(n)\)。3. 仿函数三处用途总结KeyOfT从存储的 T 类型提取 key隔离 set/map 存储差异。Hash把任意 key 转成 size_t 哈希整数自定义类型必须提供。equal 比较哈希值相同不等于 key 相同链表遍历必须真实 key 判等。4.rehash 容易踩坑不是简单扩大两倍STL 选用质数做桶大小降低冲突概率。rehash 是移动节点不是拷贝数据避免拷贝大对象。rehash 后迭代器全部失效因为节点被搬到不同桶。5.key 不能修改的原因哈希表所有位置依靠 key 的哈希值定位。 一旦 key 被修改节点实际存储位置和计算出的下标不匹配find 永远找不到元素。 所以unordered_map的 pair 的 first 是const Kset 的 key 也是不可修改。四、完整可运行简易代码汇总#includeiostream #includevector #includestring using namespace std; //哈希节点 templateclass T struct HashNode { T _data; HashNode* _next; HashNode(const T data):_data(data),_next(nullptr){} }; //set取key仿函数 templateclass K struct SetGetKey { const K operator()(const K k){return k;} }; //map取key仿函数 templateclass K,class V struct MapGetKey { const K operator()(const pairconst K,V kv){return kv.first;} }; //哈希仿函数 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 hash0; for(auto c:s) hashhash*131c; return hash; } }; //通用哈希表 templateclass T,class KeyOfT,class Hash class HashTable { public: typedef HashNodeT Node; HashTable():_size(0) { _buckets.resize(10,nullptr); } Node* Find(const KeyOfT key) { Hash hf; KeyOfT getkey; size_t idxhf(key)%_buckets.size(); Node* cur_buckets[idx]; while(cur) { if(getkey(cur-_data)key) return cur; curcur-_next; } return nullptr; } bool Insert(const T data) { KeyOfT getkey; auto keygetkey(data); if(Find(key)) return false; //负载因子1就扩容 if(_size _buckets.size()) { size_t newCap _buckets.size()*2; vectorNode* newBuckets(newCap,nullptr); for(size_t i0;i_buckets.size();i) { Node* cur_buckets[i]; while(cur) { Node* nextcur-_next; size_t idxHash()(getkey(cur-_data))%newCap; cur-_nextnewBuckets[idx]; newBuckets[idx]cur; curnext; } } _buckets.swap(newBuckets); } size_t idxHash()(key)%_buckets.size(); Node* newNodenew Node(data); newNode-_next_buckets[idx]; _buckets[idx]newNode; _size; return true; } bool Erase(const KeyOfT key) { Hash hf; KeyOfT getkey; size_t idxhf(key)%_buckets.size(); Node* cur_buckets[idx]; Node* prevnullptr; while(cur) { if(getkey(cur-_data)key) { if(prevnullptr) { _buckets[idx]cur-_next; } else { prev-_nextcur-_next; } delete cur; _size--; return true; } prevcur; curcur-_next; } return false; } private: vectorNode* _buckets; size_t _size; }; //模拟unordered_set templateclass K,class HashHashFuncK class MyUnorderedSet { public: bool insert(const K k) { return _ht.Insert(k); } bool find(const K k) { return _ht.Find(k)!nullptr; } bool erase(const K k) { return _ht.Erase(k); } private: HashTableK,SetGetKeyK,Hash _ht; }; //模拟unordered_map templateclass K,class V,class HashHashFuncK class MyUnorderedMap { public: bool insert(const pairconst K,V kv) { return _ht.Insert(kv); } V operator[](const K key) { _ht.Insert({key,V()}); Node* node_ht.Find(key); return node-_data.second; } bool erase(const K key) { return _ht.Erase(key); } private: typedef HashNodepairconst K,V Node; HashTablepairconst K,V,MapGetKeyK,V,Hash _ht; }; //测试 int main() { MyUnorderedSetint s; s.insert(1); s.insert(3); couts.find(3)endl; s.erase(3); couts.find(3)endl; MyUnorderedMapstring,int mp; mp[apple]100; coutmp[apple]endl; return 0; }五、博客小结unordered_set、unordered_map底层是链地址法哈希表核心解决哈希冲突。STL 使用泛型 仿函数实现代码复用同一个 HashTable 支撑 set 与 map。三个仿函数分工提取 key、哈希转换、key 判等是模拟实现的核心难点。rehash 扩容、负载因子、key 禁止修改都是高频考点。
