紧接着上一篇文章常用数据结构(一)，我们继续来探讨以下数据结构：HashTable、并查集、树状数组、后缀数组。

1、HashTable

1.1、什么是HashTable

HashTable，哈希表，是一种数据结构，可以通过使用称为hash的技术提供从键到值的映射。

key：其中key必须是唯一的，key必须是可以hash；

value：value可以重复，value可以是任何类型；

HashTable经常用于根据Key统计数量，如key为服务id，value为错误次数等。

1.2、什么是Hash函数

哈希函数 H(x) 是将键“ x”映射到固定范围内的整数的函数。

我们可以为任意对象(如字符串，列表，元组等)定义哈希函数。

1.2.1、Hash函数的特点

如果 H(x) = H(y) ，那么x和y可能相当，但是如果 H(x) ≠ H(y)，那么x和y一定不相等。

Q：我们如何提高对象的比较效率呢？

A：可以比较他们的哈希值，只有hash值匹配时，才需要显示比较两个对象。

Q：两个大文件，如何判断是否内容相同？

A：类似的，我们可以预先计算H(file1)和H(file2)，比较哈希值，此时时间复杂度是O(1)，如果相等，我们才考虑进一步比较稳健。(稳健的哈希函数比哈希表使用的哈希函数会更加复杂，对于文件，通常使用加密哈希函数，也称为checksums)。

哈希函数 H(x) 必须是确定的

就是说，如果H(x) = y，那么H(x)必须始终能够得到y，而不产生另一个值。这对哈希函数的功能至关重要。

我们需要严谨的使用统一的哈希函数，最小化哈希冲突的次数

所谓哈希冲突，就是指两个不同的对象，哈希之后具有相同的值。

Q：上面我们提到HashTable的key必须是可哈希的，意味着什么呢？

A：也就是说，我们需要是哈希函数具有确定性。为此我们要求哈希表中的key是不可变的数据类型，并且我们为key的不可以变类型定义了哈希函数，那么我们可以成为该key是可哈希的。

1.2.2、优秀哈希函数特点

一个优秀的Hash函数具有如下几个特点：

**正向快速：**给定明文和Hash算法，在有限的时间和优先的资源内能计算到Hash值；

**碰撞阻力：**无法找到两个不相同的值，经过Hash之后得到相同的输出；

**隐蔽性：**只要输入的集合足够大，那么输入信息经过Hash函数后具有不可逆的特性。

**谜题友好：**也就是说对于输出值y，很难找到输入x，是的H(x)=y，那么我们就可以认为该Hash函数是谜题友好的。

Hash函数在区块链中占据着很重要的地位，其隐秘性使得区块链具有了匿名性。

1.3、HashTable如何工作

理想情况下，我们通过使用哈希函数索引到HashTable的方式，在O(1)时间内很快的进行元素的插入、查找和删除动作。

只有具有良好的统一哈希函数的时候，才能真正的实现花费恒定时间操作哈希表。

1.3.1、哈希冲突的解决办法

哈希冲突：由于哈希算法被计算的数据是无线的，而计算后的结果范围是有限的，因此总会存在不同的数据结果计算后得到相同值，这就是哈希冲突。

常用的两种方式是：链地址法和开放定址法。

1.3.1.1、链地址法

链地址法是通过维护一个数据结构(通常是链表)来保存散列为特定key的所有不同值来处理散列冲突的策略之一。

链地址通常使用链表来实现，针对散列冲突的数据，构成一个单向链表，将链表的头指针存放在哈希表中。

除了使用链表结构，也可以使用数组、二叉树、自平衡树等。

如下，假设我们哈希函数实现如下：名字首字符的ASCII码 mod 6，有如下数据需要存储到哈希表中：

Key (name)	Value(age)	Hash(name首字符 mod 6)
Tom	12	0
Jim	18	2
Talor	14	0
Will	12	3
Shelly	14	5
Sam	15	5
Jay	14	2
Jason	12	2

构造哈希表如下：

Q：一旦HashTable被填满了，并且链表很长，怎么保证O(1)的插入和查找呢？

A：应该创建一个更大容量的HashTable，并将旧的HashTable的所欲项目重新哈希分散存入新的HashTable中。

Q：如何查找元素？

A：把需要查找的元素hash成具体的key，在HashTable中查找桶位置，然后判断是否桶位置为一个链表，如果是则遍历链表一一比较元素，判断是否为要查找的元素：

如查找Jason，定位到桶2，然后遍历链表对比元素：

Q：如何删除HashTable中的元素

A：从HashTable中查找到具体的元素，删除链表数据结构中的节点。

10.3.1.2、开放式寻址法

在哈希表中查找到另一个位置，把冲突的对象移动过去，来解决哈希冲突。

使用这种方式，意味着键值对存储在HashTable本身中，并不是存放在单独的链表中。这需要我们非常注意HashTable的大小。

假设需要保持O(1)时间复杂度，负载因子需要保持在某一个固定值下，一旦负载因子超过这个阈值时间复杂度将成指数增长，为了避免这种情况，我们需要增加HashTable的大小，也就是进行扩容操作。以下是来自wikipedia的负载因子跟查找效率的关系图：

当我们对键进行哈希处理H(k)获取到键的原始位置，发现该位置已被占用，那么就需要通过探测序列P(x)来找到哈希表中另一个空闲的位置来存放这个原始。

开放式寻址探测序列技术

开放式寻址常见的探测序列方法有：

线性探查法：P(x) = ax + b，其中a、b为常数
平方探查法：P(x) = ax^2 + bx + c，其中a, b, c为常数
双重哈希探查法：P(k, x) = x * H2(k)，其中H2(k)，是另一个哈希函数；
伪随机数发生器法：P(k, x) = x*RNG(H(k), x)，其中RNG是一个使用H(k)作为seed的随机数字生成函数；

10.3.1.2.1开放式寻址法的解决思路

在大小为N的哈希表上进行开放式寻址的一般插入方法的伪代码如下：

x = 1;
keyHash = H(k) % N;
index = keyHash;
while ht[index] != null {
	index = (keyHash + P(k, x)) %N;
	x++;
}
insert (k, v) at ht[index]

其中H(k)是key的哈希函数，P(k, x)是寻址函数。

10.3.1.2.2、混乱的循环

大多数选择的以N为模的探测序列都会执行比HashTable大小少的循环。当插入一个键值对并且循环寻址找到的所有桶都被占用了，那么将会陷入死循环。

诸如线性探测、二次探测、双重哈希等都很容易引起死循环问题。每种探测技术都有对应的解决死循环的方法，这里不深入展开探讨了。

1.4、使用场景

https://blog.csdn.net/winner82/article/details/3014030

数据校验
单向性的运用，hash后存储，hash对比是否一致

1.5、时间复杂度

操作	平均	最差
insert	O(1)	O(n)
remove	O(1)	O(n)
search	O(1)	O(n)

1.6、编程实践

JDK中的实现，链地址法：java.util.HashMap
JDK中的实现，开放式寻址法：java.lang.ThreadLocal.ThreadLocalMap

2、并查集

关于并查集，有一个很牛逼的比喻博文，还不了解并查集的同学可以看看这里：超有爱的并查集~，包你一看就懂。主要提供三个功能：

查找根节点
合并两个集合
路径压缩

2.1、使用场景

Kruskal最小生成树算法
网格渗透
网络连接状态
图像处理

2.2、最小生成树[^3]

最小生成树：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 [1] 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

如果对图相关概念不太了解，可以查阅这篇文章：图论（一）基本概念。

生成基本流程：

把图的边按照权重进行排序；
遍历排序的边并查看该边所属的两个节点，如果节点有连接在一起的路径了，则不用纳入该边，否则将其纳入在内并连接节点；这里判断节点是否已连接和连接节点主要用到并查集的查找根节点和合并两个集合操作；
当c处理完每条边或所有顶点都连接在一起之后，算法终止。

2.3、实现思路

2.3.1、构建并查集

假设我们想通过这些字母构建并查集：E A B F C D，我们可以把这些字母映射到数组的索引中，数组的元素值代表当前字母的上级字母索引值，由于刚开始还没有做合并操作，所以所有元素存的都是自己的索引值：

同时我们新增一个数组，用于记录当前字母手下收了多少个字母小弟，当两个字母要合并的时候，首先找到两个字母的大佬，然后字母大佬收的小弟少的要拜字母大佬小弟多的人为大佬：

为了合并两个元素，可以找到每个组件的根节点，如果根节点不同，则使一个根节点成为另一个根节点的父节点。

接下来我们要执行以下合并操作：

union(E, A), union(A, B)

接着执行

union(F, C), union(C, B)

执行到这里，这里会剩下两个组件：EABFC，D

2.3.2、并查集搜索

看到这里，相信你对并查集的搜索原理也了解了。要查找某个特定元素属于哪个组件，可以通过跟随父节点直到达到自环（该节点父节点指向本身）来找到该组件的根。比如要搜索C，我们会沿着记录的parent索引id一直往上层搜索，最终搜到E。

组件数等于剩余的root根数。另外，请注意，根节点的数量永远不会增加。

2.2.3、并查集路径压缩

我们可以发现，在极端情况下，需要找很多层的parent节点，才能找到最终的根节点。

为此我们可以在find查找节点的时候，找到该节点到跟节点中间的所有节点，重新指向最终找到的根节点来减小路径长度，这样下次在find这些节点的时候，就非常快了。如下图，我们查找A的根节点，查找到之后进行路径压缩：

2.3、时间复杂度

操作	时间复杂度
construction	O(n)
union	α(n)
find	α(n)
size	α(n)
checkConnected	α(n)
countComponents	O(1)

α(n)：均摊时间^[1]

2.4、编程实践

UnionFind

3、树状数组 Fenwick Tree

3.1、为什么需要Fenwick Tree

假设我们有一个数组A，需要计算数组中[i, j) 区间的数据之和，为了方便获取，我们提前把算好的前面n个元素之和存到另一个数组B的n+1中，如下：

这样我们就很方便的计算区间和了，如：

[2, 5) = B[5] - B[2] = 18 - 6 = 12

但是假设我们想修改A中第i个元素的值，那么B中第i+1之后的元素值都得更新：

也就是说更新的复杂度为O(n)，有没有更好的办法加快更新速度呢？这个时候我们的Fenwick Tree就要出场了，Fenwick Tree也叫Binary Indexed Tree(二元索引树)。

3.2、什么是Fenwick Tree

Fenwick Tree是一种支持给静态数组范围求和，以及在静态数组中更新元素的值后也能够进行进行范围求和的数据结构。

最低有效位(LSB least significant bit)：静态数组的小标可以转换为二进制，如8：01000，最低有效位指的是从右往左数，不为0的位，这里为 1000，计算数组小标最低有效为的函数我们一般命名为lowbit，实现参考后续代码。

数组下标的最低有效位的值n，表示该下标存储了从该下标往前数n位元素的数值之和。如下图：

我们可以发现：

1：只保存当前下标元素的值，对应上面红色区块；
10：保存下标往前数总共2个元素的值，对应上面蓝色区块；
100：保存下标往前数总共4个元素的值，对应上面紫色区块；
1000：保存下标往前数总共8个元素的值，对应上面绿色区块；
10000：保存下标往前数总共16个元素的值，对应上面浅蓝色区块；

3.2.1、范围求和

有了上面的数据结构，我们就可以进行范围求和了。

假设我们要求和[1, 7]，我们只要把以下红色区块值相加就可以了，也就是 sum = B[7] + B[6] + B[4]

如果我们要求和[10, 14]，那么我们可以这样处理：sum = sum[1, 14] - sum[1, 9] = (B[14] + B[12] + B[8]) - (B[9] + B[8])。

也就是说，针对范围查询，我们会根据LSB一直回溯上一个元素，然后把回溯到的元素都加起来。

最差的情况下，求和的复杂度为：O(log2(n))

以下是实现范围求和的代码：

/**
 * 求和 [1, i]
 */
public int prefixSum(int i) {
  sum = 0;
  while(i != 0) {
    sum = sum + tree[i]
    i = i = lowbit(i);
  }
  return sum;
}

/**
 * 求和 [i, j]
 */
public int rangeQuery(int i, int j) {
  return prefixSum(j) - prefixSum(i - 1);
}

3.2.2、单点更新

更新数组中的某一个元素的过程中，与范围查询相反，我们不断的根据LSB计算到下一个元素位置，同时给该元素更新数组。如下，更新A[9]，会级联查找到以下红色的位置的元素：

以下是实现代码，给第i个元素+x：

public void add(int i, int x) {
  while (i < N) {
    tree[i] = tree[i] + x;
    i = i + lowbit(i)
  }
}

3.2.3、构造Fenwick Tree

假设A为静态数组，B数组存放Fenwick Tree，我们首先把A数组clone到B数组，然后遍历A数组，每个元素A[i]依次加到下一个负责累加的B节点B[i + LSB]中(称为父节点)，直到到达B数组的上界，代码如下：

public FenwickTree(int[] values) {
    N = values.length;
		values[0] = 0L;

		// 为了避免直接操纵原数组，破坏了其所有原始内容，我们复制一个values数组
		tree = values.clone();

		for (int i = 1; i < N; i++) {
			// 获取当前节点的父节点
			int parent = i + lowbit(i);
			if (parent < N) {
				// 父节点累加当前节点的值
				tree[parent] += tree[i];
			}
		}
}

思考：如果我们想要快速更新数组的区间范围，如何实现比较好呢？参考：

3.3、时间复杂度

操作	时间复杂度
construction	O(n)
point update	O(log(n))
range sum	O(log(n))
range update	O(log(n))
adding index	/
removing index	/

3.4、编程实践

单点更新，区间查找：FenwickTreeRangeQueuePointUpdate
区间更新，单点查找：FenwickTreeRangeUpdatePointQuery
练习：
- Range Sum Query - Mutable

4、后缀数组 Suffix Array

后缀数组是后缀树的一种节省空间的替代方法，后缀树本身是trie的压缩版本。

后缀数组可以完成后缀树可以完成的所有工作，并且带有一些其他信息，例如最长公共前缀(LCP)数组

4.1、后缀数组格式

如下图，字符串：arthinking，所有的后缀，从长到短列出来：

给后缀排序，排序后对应的索引构成的数组既是后缀数组：

后缀数组sa：后缀suffix列表排序后，suffix的下标构成的数组sa；

rank：suffix列表每个元素的排位权重(权重越大排越后面)；

4.2、后缀数组构造过程

上面的后缀构造过程是怎样的呢？

这里我们介绍最常见的倍增算法来得到后缀数组。

我们获取每一个元素的权重rank，获取到之后，依次继续

第0轮：suffix[i] = suffix[i] + suffix[2^0]，重新评估rank；
第1轮：suffix[i] = suffix[i] + suffix[2^1]，重新评估rank；
...
第n轮：suffix[i] = suffix[i] + suffix[2^n]，重新评估rank；
...

最终得到所有rank都不相等即可。如下图所示：

这样就得到rank了，我们可以根据rank很快推算出sa数组。

为什么可以这样倍增，跳过中间某些元素进行比较呢？

这是一种很巧妙的用法，因为每个后缀都与另一个后缀有一些共同之处，并不是随机字符串，迁移轮比较，为后续比较垫底了基础。

假设要处理substr(i, len)子字符串。我们可以把第k轮substr(i, 2^k)看成是一个由substr(i, 2^k−1)和substr(i + 2^k−1, 2^k−1)拼起来的东西，而substr(i, 2^k−1)的字符串是上一轮比较过的并且得出了rank。