【数据结构】哈希表

发表于2021-11-28更新于2022-03-08字数统计6.8k阅读时长37分阅读次数

哈希

https://blog.csdn.net/u011240877/article/details/52940469

哈希，又称“散列”。

散列（hash）英文原意是“混杂”、“拼凑”、“重新表述”的意思。

在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起，而散列通过计算哈希值，打破元素之间原有的关系，使集合中的元素按照散列函数的分类进行排列。

在介绍一些集合时，我们总强调需要重写某个类的 equals() 方法和 hashCode() 方法，确保唯一性。这里的 hashCode() 表示的是对当前对象的唯一标示。计算 hashCode 的过程就称作哈希。

为什么需要哈希

我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较，而通过哈希计算，可以大大减少比较次数。使得每次查找操作的时间复杂度为 O(1)。

img

哈希函数

哈希的过程中需要使用哈希函数进行计算。

哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。表示为：address = H [key]

常见的哈希函数构造方法：除留余数法。具体做法：首先将关键字key进行一个编码运算（例如MD5编码），生成对应的哈希值（MD5码的范围为 0 ~ 2^64 - 1）。然后该哈希值被某个不大于散列表长度 m 的数 p 求余，得到散列地址。即 H(key) = key % p, p < m。

哈希函数的特性：经过哈希函数计算得到的散列地址是均匀分布的，经过 % 也还是均匀分布的。即使两个数字相差很小，经过哈希函数后二者也会大相径庭。这种特性被很好地应用在一致性哈希原理中，使得众多虚拟节点平均地分布在整个哈希域中，从而很好地做到数据库的负载均衡。

常见的哈希算法：MD5 算法和 SHA 算法。

哈希表

在 Java 中哈希表的实现为 HashMap，其底层保存有一个 Entry 数组。通过重写的 hashCode() 方法计算出当前 POJO 对象的哈希值，从而将对象放到不同的位置，相同的哈希值的对象串联在一条链表上。当添加的对象过多导致链表长度过长时，哈希表会进行扩容，增加 Entry 数组的长度，此时会重新计算每个元素的哈希值（因为计算哈希值时的 m 和 p 发生了变化），将其重新分布在扩容后的哈希表上，这个过程是会消耗一定的时间的（JVM会开启另一个线程执行扩容工作，因此扩容过程并不会怎么影响用户线程时间）。

时间复杂度分析：

  • 单次插入、修改或删除哈希表中某个元素的时间复杂度为 O(k)，k 为串联链表上元素的个数，当 k 较小时可以认为是 O(1) 级别的
  • 哈希表N个元素扩容的时间复杂度为 O(N*logN)，单次扩容的理论时间复杂度为 O(logN)。实际工程上通过增大 k 值以减少扩容次数，可以使得单次扩容的时间复杂度接近于 O(1)

借助于哈希表设计数据结构

image-20211129203404158

思路：借助两个哈希表，一个存储的 key : value 为 key : index，另一个存储的为 index : key。等概率删除则借助于哈希表的平均分布的特性，在 index 范围内随机生成一个数字，删除以该数字为 index 的数据即可做到随机删除。

细节：需要在每次删除后将 index 最大的元素交换到当前删除的位置，从而避免删除过程中的索引不连续出现的空洞现象。

哈希表常见问题

哈希表的去重性质，使得其可以解决许多问题，例如：

差值为 k 的去重数字对

给定一个数组 arr，求差值为 k 的去重数字对。

思路：

  • 使用 HashSet，将所有数字加入其中，先做到了一个去重的效果。
  • 然后遍历 HashSet 里的每一个元素，将其加上 k 后，判断该数字是否存在于 HashSet 中，如果存在则找到了一对（这里是把每个元素作为较小的那个，加上 k 后寻找比他大的那个数字，因此可以避免重复加入同一对元素）

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static List<List<Integer>> allPair(int[] arr, int k) {
    HashSet<Integer> set = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        set.add(arr[i]);
    }
    List<List<Integer>> res = new ArrayList<>();
    for (Integer cur : set) {
        if (set.contains(cur + k)) {
            res.add(Arrays.asList(cur, cur + k));
        }
    }
    return res;
}

布隆过滤器

https://zhuanlan.zhihu.com/p/43263751

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

应用场景

首先假设一个场景，需要设计一个黑名单URL的过滤器，使得黑名单的URL被拦截。如果使用传统的数组或哈希表来存储的话，那么显然大量的URL会占据非常多的系统资源（例如100亿条URL会占用几百G的内存）。因此就需要一种更好的数据结构来存储这些黑名单信息，既能节省内存又能以 O(1) 的时间复杂度进行增加和查询。

布隆过滤器即可以处理这种问题（但是不能做到删除），也常用在预防缓存穿透。

布隆过滤器数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组。其是以 bit 为单位（区别于 int[] 以32个 bits 为单位，boolean[] 以8个 bits 为单位）。数组的每个位置存储1或0。

  • 初始状态时，所有位都是0。
  • 设置黑名单时，首先经过 k 个不同的哈希函数，计算出 k 个哈希值；将这 k 个哈希值对应的数组元素设置为 1，代表这里来过一个黑名单（的 k 分之一）
  • 再来另一个黑名单时，仍然进行该操作。因为哈希函数的均匀分布性，不同的URL算出的哈希值会均匀分布在整个数组上。若发现某个位置已经为1了，则不做任何操作（意味着不同的URL生成的某种哈希值可能相同，这也导致了可能出现误判断的情况）。
  • 当所有黑名单设置完毕后，再来一个新的URL，同样计算其 k 个哈希值，判断是否都为1
    • 如果都为1，说明当前URL是黑名单（但可能出现误判断，概率较低）
    • 如果不都为1，说明当前URL一定不是黑名单

示意图：

image-20211129205936391

误判的解释：

  • 黑名单误判成白名单：不可能发生，因为只要是黑名单，其对应的 k 个哈希值一定都为1
  • 白名单误判成黑名单：有可能发生但是概率非常低

使用布隆过滤器的好处：极大地节省空间，不需要存储URL的信息，只需要维护一个位图即可，通常可以控制在30G以内。

如何选择哈希函数个数和布隆过滤器长度

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

img

k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率。如何选择适合业务的 k 和 m 值呢，公式：

image-20211129211516885

大 Value 拆分

Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。

拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。

一致性哈希

https://segmentfault.com/a/1190000021199728

在分布式系统中，当有多台数据库服务器时，使用传统的哈希算法进行负载均衡的思路时：对某个 key，先计算其哈希值，然后对节点数量 n 取模，从而决定其应该存储在哪台服务器节点上。示意图：

image-20211129213109729

这种方式的一种局限性是：当增加和删除节点时，数据迁移的代价是全量的。例如本来有三个节点，所有数据均匀地分布在这三个节点上。当再来一台时，需要重新计算所有 key 的哈希值，然后再对4取模进行重新分配，这会浪费极大的时间。

选择作为哈希值的 key 时，要选择种类比较多的，能够让高频中频和低频的 key 在多台机器上分布比较均匀，从而实现数据库的负载均衡，让数据均匀分布在所有数据库上。

一些不好的key选择：例如国家不适合作为 key，因为其分布不够均匀，会让大量相同国家的数据分布到同一台机器上；或选用性别的话只会分到两台机器上。

一致性哈希算法

一致性哈希算法在 1997 年由麻省理工学院提出，是一种特殊的哈希算法，在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。一致性哈希解决了简单哈希算法在分布式哈希表（Distributed Hash Table，DHT）中存在的动态伸缩等问题 。

一致性哈希算法原理

一致性哈希算法通过一个叫作一致性哈希环的数据结构实现。这个环的起点是 0，终点是 2^32 - 1，并且起点与终点连接，故这个环的整数分布范围是 [0, 2^32-1]（一致性哈希不计算取模 %），如下图所示：

image-20211129213029701

1、将对象放置到哈希环

假设我们有 “semlinker”、“kakuqo”、“lolo”、“fer” 四个对象，分别简写为 o1、o2、o3 和 o4，然后使用哈希函数计算这个对象的 hash 值，值的范围是 [0, 2^32-1]：

image-20211129213229644

图中对象的映射关系如下：

1
2
hash(o1) = k1; hash(o2) = k2;
hash(o3) = k3; hash(o4) = k4;

2、将服务器放置到哈希环

接着使用同样的哈希函数，我们将服务器也放置到哈希环上，可以选择服务器的 IP 或主机名作为键进行哈希，这样每台服务器就能确定其在哈希环上的位置。这里假设我们有 3 台缓存服务器，分别为 cs1、cs2 和 cs3：

image-20211129213311601

图中服务器的映射关系如下：

1
hash(cs1) = t1; hash(cs2) = t2; hash(cs3) = t3; # Cache Server

3、为对象选择服务器

将对象和服务器都放置到同一个哈希环后，在哈希环上顺时针查找（可以使用二分查找实现）距离这个对象的 hash 值最近的机器，即是这个对象所属的机器。 以 o2 对象为例，顺序针找到最近的机器是 cs2，故服务器 cs2 会缓存 o2 对象。而服务器 cs1 则缓存 o1，o3 对象，服务器 cs3 则缓存 o4 对象。

image-20211129213405673

4、服务器增加的情况

假设由于业务需要，我们需要增加一台服务器 cs4，经过同样的 hash 运算，该服务器最终落于 t1 和 t2 服务器之间，具体如下图所示：

image-20211129213425565

对于上述的情况，只有 t1 和 t2 服务器之间的对象需要重新分配。在以上示例中只有 o3 对象需要重新分配，即它被重新到 cs4 服务器。在前面我们已经分析过，如果使用简单的取模方法，当新添加服务器时可能会导致大部分缓存失效，而使用一致性哈希算法后，这种情况得到了较大的改善，因为只有少部分对象需要重新分配。

5、服务器减少的情况

假设 cs3 服务器出现故障导致服务下线，这时原本存储于 cs3 服务器的对象 o4，需要被重新分配至 cs2 服务器，其它对象仍存储在原有的机器上。

image-20211129213452096

虚拟节点

到这里一致性哈希的基本原理已经介绍完了，但对于新增服务器的情况还存在一些问题：

  1. 一开始服务器数量很少的时候，如何保证均匀性
  2. 一旦增加或减少服务器时，会导致负载不均衡，新增的服务器只承受较少的流量

例如：新增的服务器 cs4 只分担了 cs1 服务器的负载，服务器 cs2 和 cs3 并没有因为 cs4 服务器的加入而减少负载压力。如果 cs4 服务器的性能与原有服务器的性能一致甚至可能更高，那么这种结果并不是我们所期望的。

我们可以通过引入虚拟节点来解决负载不均衡的问题。即将每台物理服务器虚拟为一组虚拟服务器，将虚拟服务器放置到哈希环上，如果要确定对象的服务器，需先确定对象的虚拟服务器，再由虚拟服务器确定物理服务器。

因为每个节点的虚拟服务器可以设置非常多个（例如1000个），从而使得这些虚拟服务器可以非常均匀地分布在整个哈希域上。并且新增或减少服务器时，其增加或减少的虚拟节点在环上的分布也是比较均匀的，因此仍然能保证负载均衡。

image-20211129213534006

图中 o1 和 o2 表示对象，v1 ~ v6 表示虚拟服务器，s1 ~ s3 表示物理服务器。

一致性哈希算法优点

  • 可扩展性。一致性哈希算法保证了增加或减少服务器时，数据存储的改变最少，相比传统哈希算法大大节省了数据移动的开销 。
  • 更好地适应数据的快速增长。采用一致性哈希算法分布数据，当数据不断增长时，部分虚拟节点中可能包含很多数据、造成数据在虚拟节点上分布不均衡，此时可以将包含数据多的虚拟节点分裂，这种分裂仅仅是将原有的虚拟节点一分为二、不需要对全部的数据进行重新哈希和划分。虚拟节点分裂后，如果物理服务器的负载仍然不均衡，只需在服务器之间调整部分虚拟节点的存储分布。这样可以随数据的增长而动态的扩展物理服务器的数量，且代价远比传统哈希算法重新分布所有数据要小很多

大数据问题

本章将介绍使用哈希函数解决大数据问题的常见技巧：

  • 哈希函数可以把数据按照种类均匀分流
  • 布隆过滤器用于集合的建立与查询，并可以节省大量空间
  • 一致性哈希解决数据服务器的负载管理问题
  • 利用并查集结构做岛问题的并行计算
  • 位图解决某一范围上数字的出现情况，并可以节省大量空间
  • 利用分段统计思想、并进一步节省大量空间
  • 利用堆、外排序来做多个处理单元的结果合并

均匀分流

题目一：

image-20211206160259675

思路：如果内存不受限制，则可以创建一个超大的词频表，记录每个数字出现的频次，频次为0的即为未出现过的数。但是当内存受限时，不能创建所有数字的词频表，只能创建少量数字的词频表。

此时的思路为：创建一个词频表（长度为 N），该表中每个元素代表某一个区间范围内的数字出现的总次数。这样对于没有出现过的数字所在的区间，其词频总数就会小于 40 亿 / N。因此通过第一次的统计，就可以得知哪个区间内的数字至少有一个从未出现过，那么第二次遍历就可以直接缩小范围到该区间内，在该区间内再平均划分 N 份，然后再遍历一次 40 亿个数字，将在该子区间内的数字进行词频统计……重复该过程直到找到某一个数字从未出现过。

细节：

  • unsigned int 的范围为 [0, 2^32 - 1]，2^32 - 1 > 40 亿
  • 词频表长度 N 如何确定—— N = 10MB（内存限制 ） / 4B（unsigned int 长度）= 10240 * 1000 / 4 = 2560000，从而将 [0, 2^32 - 1] 范围内的数字均匀分到长度为 2560000 的词频表中
  • 如何确定某个数字应该被分配到词频表的哪个位置：先用 2^32 / N，计算出每个区间上数字的取值范围，然后来一个数字，就将其除以 2^32 / N，即可知道该数字属于哪个区间

题目二：

image-20211206165633171

1 GB = 2^30 byte

思路一：哈希函数均匀分流

  • 先将所有数字先后经过哈希函数和取模操作，均匀分流到不同的子文件，记录其词频
  • 然后在该子文件中使用哈希表等方式统计出词频为 2 的数字
  • 对所有子文件都进行该操作，即可得到所有出现 2 次的数字

思路二：位图

  • 创建一个位图，每两个 bit 代表一个数字出现的次数：
    • 00：没出现过
    • 01：出现过一次
    • 10：出现过两处
    • 11：出现过三次及以上
  • 这样对于 unsigned int 类型的整数，可以在 1GB 的内存空间内创建这么一个位图，每两个 bit 代表一个数字出现的次数，遍历所有数字更新该位图，即可得知所有出现两次的数字。

使用基本数据类型创建位图的方法见博客：【算法】位运算

【进阶】 如果最多只能用 10 MB 的内存，如何找到这 40 亿个整数的中位数？

思路：同上一题一样，可以使用均匀分流的技巧。

  • 先根据内存限制计算出词频数组的长度，然后将每个数字分配到不同的区间内，记录其频次
  • 遍历完一遍即可得知每个区间内出现数字的总频次
  • 题目要找的第 20 亿个数字，据此判断这个数字是落在哪个子区间上
  • 对该子区间继续划分子区间重复上述过程，不断缩小搜索范围，直到找到全局的第 20 亿个数字

重复的 URL

问题：有一个包含 100 亿个 URL 的大文件，假设每个 URL 占用 64B，请找出其中所有重复的URL。

方法一：哈希函数均匀分流

所有 URL 放到同一个文件中，则该文件太大。因此可以使用哈希函数将所有的 URL 进行均匀分流，分别存储在许多的小文件中。具体做法为：将每个 URL 经过哈希函数计算后再对某个数（小文件的个数）取模；将其存放在计算结果对应的文件中。这样即可完成一次粗定位，将所有 URL 按照种类均匀存储在不同的文件中。然后再在每个子文件中使用哈希表等方式进行查重。

方法二：使用布隆过滤器

创建布隆过滤器，当来一个 URL 时，计算其在布隆过滤器中的位置，并都标记为1。之后如果该 URL 再来一次的话，就可以发现其对应的位置在布隆过滤器中都已存在，这说明该 URL 已存在。但是该方法的缺点是会存在一定的错误率。可能两个不同的 URL 算出的值是相同的。

【进阶】 某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设计一种求出每天热门 Top 100 词汇的可行办法。

分析：如果直接对所有数据进行排序，则空间复杂度过大。因此可以使用均匀分流的思路，将所有的词汇平均分配到多个子文件中，然后对每个子文件中的词汇进行排序，选出 Top 100。最终可以得到 N 个 Top 100 排行表。然后利用堆、外排序来做多个处理单元的结果合并。具体思路：

  • 初始化：
    • 将每个子文件中的 Top 100 数据放入到一个大根堆中
    • 创建一个总堆，用于存储所有词汇的 Top 100 数据
    • 将所有子堆的堆顶弹出并压入到总堆中；
  • 迭代计算 Top 100：
    • 弹出总堆的堆顶元素，放入到 Top 100 的结果集中
    • 该堆顶元素属于哪个子堆，就从哪个子堆中再弹出一个堆顶元素压入到总堆中
    • 继续弹出总堆的堆顶元素，放入到 Top 100 的结果集中
    • 再判断该堆顶元素属于哪个子堆，就从哪个子堆中再弹出一个堆顶元素压入到总堆中
    • 重复上述过程，直到总堆弹出100个堆顶元素，即找到了所有词汇的 Top 100 词语

文件数据排序

有 10GB int32 类型的无序文件数据。希望能使用 5G/5M 内存将这些数据进行排序并存储在硬盘中（只使用少量内存完成大容量文件数据的排序）。

方法一：小根堆

使用小根堆结构，保存每个文件数据的值与词频数：Element<value: count>

实现步骤：

  • 将 [-2^31, 2^31 - 1] 范围的 10GB 文件数据先按照大小分为 N 组。N 的计算方法为：
    • 首先根据题目的限制 5GB 计算出这个内存空间能保存多少个Element<value: count>元素：假设一个元素占 8（value:4 count:4） + 8（堆的其他结构） = 16 字节，则 5GB 能保存 5 * 2^30 / 16 ≈ 2^28 个元素。将其称为一组数据，一组数据保存着 2^28 个不同的数字
    • 然后根据内存中最大能保存的元素个数计算出 [-2^31, 2^31 - 1] 范围的数据一共需要的组数 N = 2^32 / 2^28 = 16 组。注意是计算的 int32 范围的所有数组能划分多少组，和题目给的 10GB 无关
  • 确定了组数后，遍历一次这 10GB 的数据，将符合当前区间范围（[-2^31, -231+228]）的数字放入到小根堆中，同时更新其词频（记录词频的原因：如果一个数字出现了非常多次。如果保存值的话，需要将该值保存非常多份；而如果保存词频的话，只需要记录该值以及其出现的次数，只用 8 byte 即可，这样即可不受制于题目给的 10GB 限制，哪怕有很多重复的数字，也能通过记录词频的方式较好的降低了内存）
  • 该小根堆按照升序记录了 2^28 个数字以及其词频。可以利用该信息完成 [-2^31, -231+228] 区间内的所有数字的排序，将其内的数据按照升序保存到磁盘中即完成了该部分的排序。
  • 清空内存，继续下一轮遍历。每遍历一次 10GB 的文件，确定某一个区间内的数字的词频，重复上述过程 16 次，即可完成整体的排序

方法二：大根堆

使用大根堆结构，并设置一个阈值，每次往大根堆中存储高于该阈值的最小的 M 个数据。该阈值的大小将随着遍历而不断提高，直到完成整个文件数据的排序。具体步骤：

  • 设置阈值为 -2^31，遍历一遍整个文件，将大于阈值的数据加入到大根堆中，同时保证大根堆中只能存储 M 个数据（该数据用上文中的方法进行计算得到）
  • 这样遍历完一次后，就可以得到当前区间范围内的 M 个排好序的数据，将其保存到磁盘中
  • 接着提高阈值为当前大根堆的最大值，然后继续重复上述过程，直到阈值提升到所有数据中的最大值，就完成了所有数据的排序

岛问题

image-20211206150425460

进阶：若该地图特别大，希望用并行算法同时计算多个子地图中的岛屿数量，最后汇总。

思路：使用并查集

  • 先单独计算每个子地图上的岛屿数量，并在子地图与其他子地图交接的边缘区域，将每个岛屿编上号，分别初始化为不同的集合。
  • 然后两块接壤的子地图的边界元素开始进行并查集算法中的合并操作，若能合并，则当前两个岛屿是同一个；若不能合并，则是两个独立岛屿。