哈希表数据结构学习

哈希表

这里不区分 hashmap 和 hash table，（个人理解）一般hashmap指哈希表这种数据结构，而hash table指通过这种数据结构建立所得的结果。

哈希表，又称散列表，它通过建立键 key 与值 value 之间的映射，实现高效（O(1) ）的元素查询。

为什么哈希又叫散列——其实一个是音译一个是意译。
散列（hash）英文原意是“混杂”、“拼凑”、“重新表述”的意思。

在哈希表中进行增删查改的时间复杂度都是 O(1) 。
查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较，而通过 哈希 计算，可以大大减少比较次数。

基本概念

若键key或k，其值value或v存放在f(k)对应的桶bucket中。映射关系f为哈希函数或散列函数，所得的表成为哈希表或散列表。

哈希映射由一个桶数组组成，其中每个桶可以包含一个或多个键值对。要在映射中插入新的对，将向键应用哈希函数以生成哈希值。然后使用该哈希值选择其中一个桶。如果存储桶可用，则该对存储在该存储桶中。

例如，要插入键值对 (Alice, 408-555-0148) ，对键,进行散列以获取其散列值（ hash(Alice)=4），并选择位置 4 处的存储桶来存储值（408-555-0148）。稍后，要检索与 Alice 关联的值，可以使用相同的哈希函数 hash(Alice), 再次选择位置 4 处的存储桶并检索先前存储的值。

哈希方法

• 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即hash(k)=k或hash(k)=ak+b（a,b为常数），（这种散列函数叫做自身函数）。

在LeetCode中常用一维数组

• 数字分析法：假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
• 平方取中法：取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
  折- 叠法：将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
• 除留余数法：取关键字 key 对某个不大于哈希表长度的质数 p 取余数作为哈希地址，即 hash(key) = key % p。选择质数可以减少哈希冲突。
• 位运算法：通过对关键字进行位移、异或、与或等位运算来生成哈希值。这种方法速度快且实现简单，尤其适合于二进制数据。
• 混合哈希法等等

密码学中常见的哈希算法

• MD5 (Message-Digest Algorithm 5)
  特点：MD5 是一种广泛使用的哈希函数，它将任意长度的输入数据映射为 128 位的散列值（通常表示为 32 位的十六进制数）。
  应用：MD5 常用于数据完整性校验。但是，由于存在碰撞攻击（即不同的输入会生成相同的哈希值），MD5 在加密应用中已被逐步淘汰。

• SHA-2 (Secure Hash Algorithm 2)
  特点：SHA-2 是 SHA-1 的改进版，具有更强的安全性。SHA-2 包括多个不同的变种，如 SHA-224、SHA-256、SHA-384、SHA-512 等，分别生成 224 位、256 位、384 位和 512 位的散列值。
  应用：SHA-2 广泛应用于数字签名、TLS/SSL 证书和区块链技术中。

单值哈希与多值哈希

讨论哈希表时的一个重要区别是是否允许重复键。

• 单值哈希表或哈希映射要求键是唯一的（例如 std::unordered_map），单键对单值。
• 多值哈希表和哈希多映射允许重复键（如 std::unordered_multimap），单键对多值。

哈希冲突

如果表中桶的数量等于可能的键的数量，则可以使用哈希桶和键之间的一对一关系，其中每个键正好映射到表中的一个桶。

然而，这在大多数情况下是不切实际的，因为潜在键值对的数量事先不知道，或者为每个键值对保留存储桶所需的存储将超过可用的存储容量。好比一个电话簿不可能写得下宇宙中每个可能的名字和其号码。

因此，哈希函数通常是不完美的，并可能导致哈希冲突（Hash Collision），其中两个不同的键映射到相同的哈希值（$f(k_1)=f(k_2),k_1\ne k_2$）。好的哈希函数寻求最小化冲突的可能性，但在大多数情况下它们是不可避免的。

在哈希表中，由于不同的关键字可能被映射到相同的哈希地址，导致哈希冲突（Hash Collision）。为了解决哈希冲突，可以采用以下几种常见的方法：

1. 开放寻址法（Open Addressing）

当发生哈希冲突时，开放地址法通过在哈希表中找到另一个空闲位置来存储冲突的关键字。常见的开放地址法有以下几种策略：

• 线性探测法（Linear Probing） ：当发生冲突时，按顺序检查哈希表的下一个位置，直到找到一个空闲位置。
  优点 ：实现简单，容易理解。
  缺点 ：容易形成“聚集”现象，导致性能下降。
• 二次探测法（Quadratic Probing） ：探测位置不是线性增长，而是按二次函数增长，即探测序列为 hash(key) + 1², hash(key) + 2², ...。
  优点 ：减少了线性探测法中的聚集问题。
  缺点 ：探测序列可能导致访问不到某些位置，尤其是当哈希表大小不是质数时。
• 双重哈希法（Double Hashing） ：使用两个不同的哈希函数 h1(key) 和 h2(key)，当发生冲突时，探测序列为 h1(key) + i * h2(key)。
  优点 ：减少了冲突发生的概率，更均匀地分布关键字。
  缺点 ：实现相对复杂，需要设计两个合适的哈希函数。

2. 链地址法（Chaining）

每个哈希表槽位对应一个链表，当多个关键字被映射到同一槽位时，将这些关键字存储在链表中。
优点 ：

• 容易处理不同大小的哈希表。
• 无需担心哈希表装载因子过大（元素个数超出哈希表大小）。
  缺点 ：
• 链表的使用增加了额外的内存开销。
• 查找和删除操作的时间复杂度取决于链表的长度，最坏情况下为O(n)。

3. 再哈希法（Rehashing）

当发生冲突时，使用一个新的哈希函数重新计算哈希地址，直到找到一个空闲的位置。
优点 ：可以减少冲突的发生，提高哈希表的查找效率。
缺点 ：需要设计多个有效的哈希函数，增加了实现复杂性。

4. 建立公共溢出区（Overflow Area）

将冲突的关键字存放在一个公共的溢出区中，而不是在原哈希表中继续查找位置。
优点 ：

• 简化了哈希表的查找逻辑，尤其是当溢出区结构简单时。
  缺点 ：
• 溢出区可能导致查找效率低下，尤其是在溢出区中的元素较多时。
• 需要额外的内存来存储溢出区。

5. 扩展线性哈希法（Extendible Hashing）

基于二进制哈希值的扩展哈希表，每次冲突会通过增加哈希表的位数来解决冲突。哈希表会随着数据的增加而动态扩展。
优点 ：

• 动态扩展，避免了固定哈希表大小的限制。
• 分布均匀，减少了冲突的概率。
  缺点 ：实现较为复杂，适合需要动态调整哈希表大小的场景。

6. 线性分离法（Cuckoo Hashing）

使用两个哈希函数和两个哈希表，当插入时，如果第一个位置已经被占用，则将占用该位置的元素移动到另一个哈希表中，循环此操作直到没有冲突或达到预设的最大尝试次数。
优点 ：

• 查找时间复杂度为 O(1)，因为每个元素最多只能在两个位置上找到。
• 插入操作复杂度较低。
  缺点 ：
• 可能会出现无限循环，需要重新哈希。
• 需要更大的哈希表空间来避免频繁的冲突。

每种方法都有其适用的场景和局限性，选择合适的哈希冲突解决方法取决于具体应用的需求、哈希表的大小以及允许的冲突处理开销。

空间扩容

由于哈希表能够直接访问查找元素的地址，所以它的时间复杂度为常数的复杂度 O(1)。而每一个key到address的映射关系需要记录下来，假设哈希表有 n 个元素，那么就需要 n 条记录，故空间复杂度为 O(n)。

关于复杂度记法
Ο，读音：big-oh；表示上界，小于等于。
Ω，读音：big omega、欧米伽；表示下界，大于等于。
Θ，读音：theta、西塔；既是上界也是下界，称为确界，等于。
ο，读音：small-oh；表示上界，小于。
ω，读音：small omega；表示下界，大于。
Ο是渐进上界，Ω是渐进下界。Θ需同时满足大Ο和Ω，故称为确界。Ο极其有用，因为它表示了最差性能。

vector扩容

先看以下vector是怎么扩容的。

vector容器不同于数组，能够进行动态扩容，其底层原理：所谓动态扩容，并不是在原空间之后接续新空间，因为无法保证原空间之后尚有可配置的空间。而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，并释放原空间。

push_back扩容机制：当push_back一个元素时，

如果发现size() == capacity()，那么会以两倍空间扩容，然后将元素插入到finish迭代器的下一个元素（注意会申请一个新的空间，并将原有元素拷贝到新空间中，然后释放原有空间）
如果发现size() < capacity()，那么会插入到finish迭代器的下一个元素
不会出现size() > capacity()

pop_back、earse、clear缩容机制：
pop_back会减少一个size()，但是不会改变capacity() （finish迭代器前移一位）
earse会减少一个size()，但是不会改变capacity() （finish迭代器前移一位）
clear令size()为0，但是不会改变capacity()（将finish迭代器移动到start相同位置）

对于resize(new_size)
如果new_size== curr.size，什么也不做
如果new_size< curr.size， 那么 curr.size = new_size，curr.capacity不变
如果new_size> curr.size， 那么 curr.size = new_size，curr.capacity = new_size，将容器capacity 扩大到能容纳new_size的大小，改变容器的curr.size，并且创建对象。

对于reserve(new_size)
如果new_size== curr.size，什么也不做
如果new_size< curr.size，什么也不做
如果new_size> curr.size，curr.size不变，curr.capacity=new_size，将容器capacity 扩大到能容纳new_size的大小，在空间内不真正创建对象，所以不改变curr.size

真正的释放内存

vector<int>(v).swap(v); 

vector(v)通过拷贝构造函数创建了一个匿名对象，这个匿名对象拥有v的全部数据，但是，没有空闲的空间，也就是说，这个匿名对象的容量和数据量是相等的。

此时，通过 swap(v) 调用该匿名对象的swap()方法，交换v与匿名对象的内容。

匿名对象在执行完代码之后会自动调用析构函数，那么空间被释放，最终结果就是，原容器中的空位被释放。

负载因子以及增容

若哈希冲突出现的较为密集，往往代表着此时数据过多，而能够映射的地址过少，而要想解决这个问题，就需要通过 负载因子（装填因子） 的判断来进行增容

负载因子的大小 = 表中数据个数 / 表的容量（长度）

闭散列
对于闭散列来说，因为其是一种线性的结构，所以一旦负载因子过高，就很容易出现哈希冲突的堆积，所以当负载因子达到一定程度时就需要进行增容，并且增容后，为了保证映射关系，还需要将数据重新映射到新位置。对应上述开放寻址法。

闭散列是一种预先分配存储空间的方法。在闭散列中，存储空间被划分为若干个固定大小的桶，每个桶中可以存储多个元素。当插入新元素时，根据其哈希值确定其所属的桶，并将元素添加到该桶中。如果发生哈希冲突，则将元素添加到下一个可用的桶中。这种方法简单易行，但可能会导致某些桶被过度使用，而其他桶仍空闲。
开散列是一种动态调整存储空间的方法。在开散列中，当某个桶已满时，会根据一定规则分配一个新的桶。这种方法可以更好地利用存储空间，但需要额外的空间来管理桶的分配。
在实际应用中，可以根据具体情况选择不同的哈希策略。例如，对于需要快速插入和查找的数据结构，闭散列可能是一个更好的选择。而对于需要高效利用存储空间的数据结构，开散列可能更为合适。

经过算法科学家的计算， 负载因子应当严格的控制在 0.7-0.8 以下，所以一旦负载因子到达这个范围，就需要进行增容。

因为除留余数法等方法通常是按照表的容量来计算，且当对一个质数取模时，冲突的几率会大大的降低，并且因为增容的区间一般是 1.5-2 倍，所以算法科学家列出了一个增容质数表，按照这样的规律增容，冲突的几率会大大的降低。
这也是 STL 中 unordered_map/unordered_set 使用的增容方法。

开散列
因为哈希桶是开散列的链式结构，发生了哈希冲突是直接在对应位置位置进行头插，而桶的个数是固定的，而插入的数据会不断增多，随着数据的增多，就可能会导致某一个桶过重，使得效率过低。对应上述拉链法。

开散列中每个桶放的都是哈希冲突的元素。哈希桶下面挂着的是一个一个的节点（一条链表），如果该位置哈希冲突的元素过多时，通常会将这条链表转为一颗红黑树。

---

GPU上的哈希表

精心设计的哈希函数通过最大化哈希任意两个键将导致不同哈希值的可能性来最小化冲突次数。这意味着对于任何给定的两个键，它们对应的桶可能位于不同的内存位置。

因此，大多数哈希表操作的内存访问模式实际上是随机的。为了理解哈希表的性能，了解随机内存访问的性能非常重要。

下表比较了理论峰值带宽与在现代 GPUs 和 GPUs 上通过 GUPs benchmark 测量的随机 64 位读取的实现带宽（带宽计算为访问大小乘以访问次数除以时间）。

随机内存访问大约比理论峰值带宽慢 10 倍。这是因为内存子系统针对顺序访问进行了优化。更重要的是， NVIDIA GPU s 的随机访问吞吐量比现代 CPU s 的高一个数量级。这些结果表明，性能最好的 CPU 哈希表可能比性能最好的 GPU 哈希表慢一个数量级。

显存允许的情况下那肯定优先考虑使用GPU哈希表了。

以下是一个CUDA的哈希表三方库：

---

参考

• maximizing-performance-with-massively-parallel-hash-maps-on-gpus
• hello-algo/hash_map
• C++进阶（哈希）

---

先到这儿。