并查集
需求分析
设计一个数据结构，能够快速执行2个操作
1、查询
2、连接
数组、链表、平衡二叉树、集合（Set）？
查询、连接的时间复杂度都是：O(n)
并查集
并查集也叫作不相交集合（Disjoint Set）
并查集有2个核心操作
有2种常见的实现思路：
Quick Find
查找（Find）的时间复杂度：O(1)
合并（Union）的时间复杂度：O(n)
Quick Union
如何存储数据：
可以用数组实现的树形结构
Quick find
连接节点
查找节点
实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| + 准备
+ 父节点数组
+ 初始化
+ 每个节点单独一个集合（父节点为本身！！！）
+ find查找所属的集合（根节点）
+ 参数校验！！！
+ 直接返回查找元素的父节点
+ issame（查找是否同一集合）
+ 判断父节点是否相等！！
+ union（合并节点所属的集合！！）
+ 参数校验（若已经是同一集合，直接返回）
+ 遍历数组（查找父节点）！！！
+ 将所有父节点为p1的改为父节点为p2！！（包括p1节点本身）
+ 时间效率
Find O(1)
Union O(n)
|
Quick union
时间效率：都是logn
连接原理：找到最根的节点进行连接
1
2
3
4
5
6
7
8
9
| + Union（node1，node2）
+ （左边根节点）跟随（右边根节点）！！！
+ 将v1的根节点嫁接到v2的根节点上
+ 找到两个节点的根节点
+ 根节点1父节点指向根节点2
+ Find（找到集合根节点）
+ 参数校验
+ 向上循环查找即可（while）
|
优化（基于quick union）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| + 树不平衡、甚至链表情况
+ 优化方案
+ 1、基于size的优化
+ 元素少的数 嫁接到 元素多的树！！！
+ 2、基于rank的优化
+ 矮的数 嫁接到 高的树！！！
+ 基于size的优化
+ 初始化
+ size为1
+ union
+ 连接时判断根节点size
+ size小的连接到size大的下面
+ 修改size！！！
+ 大的根节点size相应增加
+ 问题
+ 树不平衡无法解决
+ 基于rank的优化！！！
+ 初始化
+ 每个集合rank（高度）为1
+ 在union时修改即可
+ union
+ 连接时判断根节点rank
+ rank小的根节点连接到rank大的下面
+ rank相等时！！！
+ 左边嫁接到右边
+ 修改rank（其他情况下嫁接后rank不变）
+ 右边的rank+1即可！！
|
路径压缩
1
2
3
4
5
6
7
| + 树的高度越来越高
+ find效率变慢
+ find时路径上的所有节点都指向根节点
+ 降低树的高度
+ 查找越多，越接近2层
+ union、find时效率提升
|
find实现（每个节点指向其祖父）
路径分裂
路径减半
find（路径减半）
自定义类型
实现
1、hash计算
2、链表+映射（map）
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
public class UnionFind_QU_R extends UnionFind_QU {
private int[] ranks;
public UnionFind_QU_R(int capacity) {
super(capacity);
ranks = new int[capacity];
for (int i = 0; i < ranks.length; i++) {
ranks[i] = 1;
}
}
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
if (ranks[p1] < ranks[p2]) {
parents[p1] = p2;
} else if (ranks[p1] > ranks[p2]) {
parents[p2] = p1;
} else {
parents[p1] = p2;
ranks[p2] += 1;
}
}
@Override
public int findPC(int v) {
rangeCheck(v);
if (parents[v] != v) {
parents[v] = find(parents[v]);
}
return parents[v];
}
@Override
public int findPH(int v) {
rangeCheck(v);
while (v != parents[v]) {
parents[v] = parents[parents[v]];
v = parents[v];
}
return v;
}
@Override
public int findPS(int v) {
rangeCheck(v);
while (v != parents[v]) {
int p = parents[v];
parents[v] = parents[parents[v]];
v = p;
}
return v;
}
}
|
1
2
3
4
5
6
7
| 搭配建议：
1、Quick Union
2、基于 rank 的优化
3、Path Halving 或 Path Spliting
|
布隆过滤器
需求分析
如果要经常判断 1 个元素是否存在，你会怎么做？
1、很容易想到使用哈希表（HashSet、HashMap），将元素作为 key 去查找
时间复杂度：O(1)，但是空间利用率不高，需要占用比较多的内存资源
2、是否存在时间复杂度低、占用内存较少的方案？
布隆过滤器（Bloom Filter）
布隆过滤器
1970年由布隆提出
- 它是一个空间效率高的概率型数据结构，可以用来告诉你：一个元素一定不存在或者可能存在
- 二进制向量 + hash函数组成
优缺点
优点：空间效率和查询时间都远远超过一般的算法
缺点：有一定的误判率、删除困难
它实质上是一个很长的二进制向量和一系列随机映射函数（Hash函数）
常见应用：
网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统、解决缓存穿透问题
原理
二进制向量 + hash函数组成
1
2
3
4
5
6
7
8
| + 查找元素是否存在
+ 全部哈希函数索引有一个不为1，不存在 √
+ 全部哈希函数都为1，存在（有一定概率不存在）
+ 索引：二进制
+ 降低误判率：减少哈希冲突
+ 数组加长
+ hash函数增加
|
误判率计算
根据误判率、数据规模
实现
Guava: Google Core Libraries For Java
https://mvnrepository.com/artifact/com.google.guava/guava
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| public class BloomFilter<T> {
private int bitSize;
private long[] bits;
private int hashSize;
public BloomFilter(int n, double p) {
if (n <= 0 || p <= 0 || p >= 1) {
throw new IllegalArgumentException("wrong n or p");
}
double ln2 = Math.log(2);
bitSize = (int) (- (n * Math.log(p)) / (ln2 * ln2));
hashSize = (int) (bitSize * ln2 / n);
bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
}
public boolean put(T value) {
nullCheck(value);
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
boolean result = false;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
int index = combinedHash % bitSize;
if (set(index)) result = true;
}
return result;
}
public boolean contains(T value) {
nullCheck(value);
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
int index = combinedHash % bitSize;
if (!get(index)) return false;
}
return true;
}
private boolean set(int index) {
long value = bits[index / Long.SIZE];
int bitValue = 1 << (index % Long.SIZE);
bits[index / Long.SIZE] = value | bitValue;
return (value & bitValue) == 0;
}
private boolean get(int index) {
long value = bits[index / Long.SIZE];
return (value & (1 << (index % Long.SIZE))) != 0;
}
private void nullCheck(T value) {
if (value == null) {
throw new IllegalArgumentException("Value must not be null.");
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| + 不提供删除功能（保证查询高效）
+ 布隆过滤器
+ 构造
+ 利用long[]作为二进制向量
+ 求出二进制位数、hash函数个数
+ 根据数据规模、误判率
+ 添加元素
+ 原始
+ hashcode()得到元素的hash值
+ hash函数计算生成索引
+ 采用谷歌的实现
+ 生成哈希，并将索引设为1
+ 判断元素是否存在
+ 查询哈希的index是否为1
+ 若有0，则返回false
+ 设置指定索引为1！！！
+ 找到long数组对应的位置
+ 按位或
+ 查看index位置的二进制值！！！
+ 找到long数组对应的位置
+ 按位与
|
