哈希表 - YHT's Note Repo

%% # 纲要 > 主干纲要、Hint/线索/路标 - 哈希表结构 - 哈希冲突及解决办法 1. 链地址法 2. 开放地址法 - 扩容（Rehashing） - 负载因子 - 自定义哈希函数 # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 哈希表 | 散列表哈希表是一种存储 **键值对（Key-Value）** 的数据结构，简单来说 = **哈希函数** + **数组**。数组中每项称为一个**桶或槽**（bucket），可能实际对应一个链表（采用链地址法时），也可能就是只存单项元素（开放地址法时）。对于给定 key，通过**哈希函数**映射得到 **==桶的索引值==**，在该桶中存储元素 value，即 `index = hash(key) % table_size`，**时间开销为 $O(1)$**。 # 哈希冲突 **哈希冲突**——**不同的键**（Key）经**哈希函数计算的所得索引值**相同，即映射到了哈希表中的**同一个槽位**（同一个桶），也称之为 "**==碰撞==**"。 > [!example] 例如，以取模 `%5` 作为哈希函数，则 `key=7` 与 `key=12` 经哈希函数映射所得索引值均为 2，即为哈希冲突。两种主要的哈希冲突解决方法： 1. **链地址法**（Separate Chaining）：每个桶维护一个链表，冲突元素挂在链表中。 2. **开放地址法**（Open Addressing）：所有元素直接存储于哈希表数组中，冲突时按特定**探测策略**寻找下一个空槽。 > [!info] C++中 `unordered_set` 与 `unordered_map` 底层实现采用 "**==链地址法==**" 解决哈希冲突。 ## （1）链地址法链地址法：**每个桶** 用 **一个链表** 存放所有映射到这个位置的冲突键值对。 > [!note] 链地址法示意 > > 注：下图是逻辑示意 > ![[_attachment/00-数据结构与算法笔记/数据结构/哈希表.assets/IMG-哈希表-03D468B5D792B94FEBA063DC3E900A68.png|246]] #### 探测过程说明 1. 用哈希函数计算**初始索引位置**：`index = hash(key) % table_size` 2. 在该槽位对应的**链表上==线性查找==**。 #### 底层操作说明以 GCC libstdc++为例，`unordered_map` 的底层结构是 `_Hashtable`，其设计中： - **所有元素** 存储在一个 **全局==单向链表==** 中（从而支持 **==迭代器==** `begin()`、`end()` 遍历） - **哈希表** 底层数组实际上是一个 **==指针数组==**，**每个桶**（bucket）存储一个 **指针**，指向该桶 "**逻辑上对应的==链表的首节点==**" ； - **节点结构**为 `_Hash_node` ，其中 `_M_next` 成员指向的是该节点 "**逻辑上所在桶中的后一元素**" 。 **插入**元素时，实际过程为： 1. 新建节点，将其 "**插入到全局链表头部**" （头插法，`_M_before_begin` 之后） 2. 哈希映射计算得到 **桶索引**，同样采用**头插法**，**插入上述新节点** 伪代码示例： ```c++ __node_type* new_node = allocate_node(...); // 1. 插入到全局链表中（用于迭代器） insert_node_after(_M_before_begin, new_node); // 2. 插入到桶链表中(用于哈希) new_node->_M_next = _M_buckets[bucket_index]; _M_buckets[bucket_index] = new_node; ``` ## （2）开放地址法开放地址法：冲突时，**在表中寻找一个空位置存放**，常用 **==探测策略==** 包括三种： - **线性探测**——从冲突位置往后，**逐个位置**检查（步长为 1） - **二次探测**——**步长按平方增长**； - **双重哈希**——使用**第二个哈希函数**来决定 "**步长**"；该方法下，需要为每个槽增加一个 "**==状态标记==**"，通常是三种： - `EMPTY`：从未被使用 - `OCCUPIED`：正常放置了一个元素 - `DELETED`：曾经放过元素，但其已被删除（目的在于**维护探测路径的连续性**，查找过程中遇见该状态的槽时，**继续探测而不停止**） #### 探测过程说明 1. 首先，用哈希函数计算**初始索引位置**：`index = hash(key) % table_size` 2. 若位置非空，则采用上述策略**查找其他空位**： - **线性探测**：索引值为 `index = (hash(key) + i) % table_size`，其中 `i = 0, 1, 2, ...` ，即**步长为 1**，**往后的位置挨个检查是否为空**。 - **二次探测**：索引值为 `index = (hash(key) + c1*i + c2*i*i)) % table_size`，其中 `i = 0, 1, 2...`，即**步长随着 `i`按平方增长**。 - **双重哈希**：索引值为 `index = (hash1(key) + i * hash2(key)) % table_size`，即**步长为 `i*hash2(key)`，由第二个哈希函数根据 key 确定**。 > [!caution] 线性探测容易造成聚集效应，另外两种方法会更好，双重哈希开销会略大点 #### 底层操作说明 - 在**向表中插入元素** & **查找元素** 时，开放地址法**必须==按照插入时的探测序列==逐个查找下去**，直至命中元素，或者**找到一个 ==`EMPTY` 位置==**。 - 因此，如果**表已较满**（负载因子较高），会发生连续冲突，**最坏情况下可能会探测整张表**（例如线性探测）。 - 元素删除时，会**将其所在槽位标记为 `DELETED`** 状态（而不是 `EMPTY`），从而**维护探测序列的连续性**（防止切断其它元素的探测路径） - 插入新元素时，若在探测路径上遇到 `DELETED` 槽，即可**插入==复用==**。 # 扩容（Rehashing）随着哈希表内元素变多，冲突概率上升，哈希表性能会下降。此时，需要**扩大哈希表容量**，**让哈希表中元素分布更稀疏**，从而减少冲突保持性能，该过程称之为 "**==Rehashing==**" 扩容。哈希表通常通过 "**==负载因子==**" 来判断是否需要扩容，例如在**负载因子 > 0.75 时** 触发扩容。 > [!info] C++中 `unordered_map` 与 `unordered_set` 的负载因子默认阈值是 `1.0`，即平均每个桶里都装有一个 1 个元素时扩容 > > - 可通过 `.max_load_factor()` 函数手动修改； > - 可调用 `.rehash(新桶数量)` 函数手动扩容。 #### 扩容过程 1. 按 "**扩容因子**" 创建一个更大的新哈希表（例如扩容因子为 2，则是容量翻倍） 2. 遍历旧哈希表中所有元素，**重新经哈希函数计算得到 bucket索引值**，**插入新表**中； 3. 删除旧表，释放旧表内存。 ## 负载因子（Loader factor）负载因子用以衡量 **哈希表当前填充程度**，其值为哈希表中**当前元素数量** (`size`) 与**桶数量**（`bucket_count`）之比： $ \large \text{load factor}=\frac{元素数量}{\text{bucket}\,{数量} } $ 高负载因子下，意味着**哈希冲突**可能性增高。 > [!caution] 负载因子是一个全局平均值，并不能完全反映 "局部" 哈希冲突的程度。 > > 例如，在链地址法下，可能绝大部分是空桶，而某个桶的链表非常长（局部冲突很严重），但**反映到负载因子上可能并不高**。 # 自定义哈希函数 C++中有两种方式为 "**无序容器**" 提供自定义哈希函数： - （1）提供自定义 "**哈希函数对象**" - （2）提供**自定义的 `hash<MyClass>` 模版特化**；该方式下，**无需在 "==容器类型==" 中显式指出哈希函数对象类型**，也不用传入函数对象。 ### 方式一：提供自定义 "哈希函数对象" ```cpp #include <iostream> #include <unordered_set> #include <functional> #include <utility> using namespace std; // 自定义类型 struct Point { int x; int y; // 需要定义==, 供无序容器判断两个Pointer是否相等 bool operator==(const Point& other) const { return x == other.x && y == other.y; } }; // 自定义哈希函数 struct PointHash { size_t operator()(const Point& p) const { // 使用`std::hash<>`为int类型生成哈希值 // 利用异或、位移操作, 变换哈希值, 减少哈希冲突. return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1); } }; int main() { auto MyHash = [](const Point& p) -> size_t { return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1); }; // 以Point类型为键, string为值的哈希表 // 方式一: 接收函数对象 unordered_map<Point, string, PointHash> pointMap; // 方式二: 接收lambda unordered_map<Point, string, decltype(MyHash)> pointMap2(0, MyHash); // 初始化创建0个桶, 指定自定义哈希函数. // 插入元素 pointMap[{1, 2}] = "Point A"; // `[]`里用到了"聚合初始化". pointMap[{3, 4}] = "Point B"; pointMap[{1, 2}] = "Updated Point A"; // 遍历并输出 for (const auto& [key, value] : pointMap) { cout << "Point(" << key.x << ", " << key.y << "): " << value << endl; } // 查找特定键 Point searchKey {3, 4}; if (auto it = pointMap.find(searchKey); it != pointMap.end()) { cout << "Found: " << it->second << endl; } } ``` ### 方式二：提供自定义的 `hash<MyClass>` 模版特化版本为 STL 中的无序容器，**提供自定义的 `hash<MyClass>` ==模版特例化==版本**。 ```cpp #include <iostream> #include <unordered_set> #include <hash_fun.h> using namespace std; class Sales_data { friend class std::hash<Sales_data>; // 需要将hash<Sales_data>类声明为友元 public: Sales_data(string s, unsigned u, double re) : bookNo(s), units_sold(u), revenue(re) {} bool operator==(const Sales_data& rhs) const { return this->bookNo == rhs.bookNo && this->units_sold == rhs.units_sold && this->revenue == rhs.revenue; } private: string bookNo; unsigned units_sold; double revenue; }; // 必须在原模版所在的命名空间中进行特例化! namespace std { // 示例: 定义hash模版的一个特例化版本, 可供在无序容器中散列Sales_data对象. template <> struct hash<Sales_data> { // 用于在无序容器中进行散列时, 要求必须定义的两个类型成员: `result_type`与`argument_type` // 无序容器将使用`argument_type`作为其key_type, 并在key_type上执行相等运算符. typedef size_t result_type; typedef Sales_data argument_type; size_t operator()(const Sales_data&) const; }; // 类外, 为全特例化的类模版定义成员函数时, 不需要模版声明`template <...>` size_t hash<Sales_data>::operator()(const Sales_data& s) const { return hash<string>()(s.bookNo) ^ hash<unsigned>()(s.units_sold) ^ hash<double>()(s.revenue); } } // end namespace std // 当hash<>的特例化版本在作用域中时, 定义无序容器时将自动使用 // 将使用hash<Sales_data>特例化版本, 以及Sales_data类的operator==. unordered_set<Sales_data> SDset; int main() { Sales_data obj1("Hello", 2, 3.14); Sales_data obj2("Hello", 3, 1.7); SDset.insert(obj1); SDset.insert(obj2); cout << SDset.size() << endl; } ``` %% # 哈希表 trick ### 数组哈希例如，按值域开一个数组充当哈希表，以下标为 key，对应位置的元素值为 value。 %% # 参考资料 # Footnotes