跟左神学算法7 进阶数据结构(哈希相关)

内容：

1、认识哈希函数与哈希表

2、设计RandomPool结构

3、认识布隆过滤器

4、认识一致性哈希

5、并查集

6、经典的岛问题

1、认识哈希函数与哈希表

哈希函数：

Hash(又称散列或哈希)就是把任意长度的输入通过散列算法，变换成固定长度的输出，该输出就是散列值。
这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，
而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

哈希函数的性质:
1、经典哈希函数输入域无穷大、输出域有穷尽
2、输入参数一样的情况下得到的输出值是一样的 => 相同输入导致相同输出
3、当输入不一样时候也可能得到一样的输出值(哈希碰撞) =》不同输入也有可能导致相同输出
4、哈希函数的离散性(均匀分布) => 不同输入均匀分布
5、返回值跟输入没有关系 => 用于打乱输入规律
6、哈希函数返回值中的每一位之间互相没有相关性

哈希函数拓展问题:
如何用一个哈希函数做出1000个哈希函数?
方法：比如说用Md5哈希函数，结果16位字符串劈成两个8位字符串，分别是s1和s2
h1 = s1 + 1 * s2
h2 = s1 + 2 * s2
h3 = s1 + 3 * s2
h4 = s1 + 4 * s2
同理这样下去做出1000个哈希函数
另外用数学方法可以证明这1000个哈希函数都是互相独立的

哈希表:

散列表（Hash table，也叫哈希表），是根据key-value直接进行访问的数据结构。也就是说，它通过把key值映射到
表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定一个表，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，
则称这个表为哈希表，函数f(key)为哈希函数

哈希表的经典结构:
哈希表大小: 17 每个节点后面跟的都是链表(Java中是红黑树)

put(key1, value1): key1经过hashCode得到一个数 => 这个数 % 17 = x(0 ~ 16) => 哈希表[x] = (key1, value1)(以链表节点的形式挂上去) 算出来x上有节点时如果节点后面的链表上有key1就把key1对应的值修改，如果没有key1就把(key1, value1)添加到链表最后
get(key1)
remove(key1)

哈希表增删改查:

在理论上可以把哈希表的增删改查操作当作O(1)的操作(实际场景中有很多优化方法)

Java中与哈希有关的结构(HashSet、HashMap)：

 1 　　public static void useHashSetDemo() {
 2         HashSet<Integer> ht = new HashSet<Integer>();
 3         ht.add(0);
 4         ht.add(0);
 5         ht.add(1);
 6         System.out.println(ht.size());// 查看hashset长度
 7         for (Integer integer : ht) {
 8             System.out.println(integer);// 遍历
 9         }
10         System.out.println(ht.contains(0));// 是否包含0
11     }
12 
13     public static void useHashMapDemo() {
14         HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
15         h.put(1, 0);
16         h.put(2, 0);
17         h.put(1, 3);
18         System.out.println(h.get(1));
19         System.out.println(h.keySet());// key的集合
20         System.out.println(h.values());// value的集合
21         System.out.println(h.entrySet());// 输出key=value的集合
22         // 遍历
23         for(Entry<Integer, Integer> entry : h.entrySet()){
24             System.out.println(entry.getKey() + " - " + entry.getValue());
25         }
26     }

2、设计RandomPool结构

题目描述：

设计一种结构，在该结构中有如下三个功能：

insert(key)：将某个key加入到该结构，做到不重复加入。
delete(key)：将原本在结构中的某个key移除。
getRandom()：等概率随机返回结构中的任何一个key。

要求: insert、delete和getRandom方法的时间复杂度都是 O(1)

思路：

如果不考虑delete的时候直接用两个哈希表，用一个size记录插入哈希表中元素个数一个哈希表是(key, size) 另外一个哈希表是(size, key)

insert实现就是将key直接插入这两个哈希表中，getRandom实现依靠random函数随机生成一个0到size-1的数，然后根据随机生成的数来get原先加入的key

如果考虑delete 那么在某些时候哈希表中某些size对应的key不存在会引起空洞现象(随机出一个数但是哈希表中没有这个数) 这是以为某些size在之前被delete了

解决方法是在delete的时候把最后一个元素放入要delete的元素的位置

代码：

 1 public class RadomPool {
 2     public HashMap<String, Integer> keyIndexMap;
 3     public HashMap<Integer, String> indexKeyMap;
 4     public int size;
 5 
 6     public RadomPool() {
 7         keyIndexMap = new HashMap<String, Integer>();
 8         indexKeyMap = new HashMap<Integer, String>();
 9         size = 0;
10     }
11 
12     public void insert(String key) {
13         if(!this.keyIndexMap.containsKey(key)){
14             keyIndexMap.put(key, size);
15             indexKeyMap.put(size, key);
16             size++;
17         }
18     }
19     
20     public void delete(String key){
21         if(this.keyIndexMap.containsKey(key)){
22             int deleteIndex = this.keyIndexMap.get(key);
23             int lastIndex = --this.size;
24             String lastKey = this.indexKeyMap.get(lastIndex);
25             // update keyIndexMap
26             this.keyIndexMap.put(lastKey, deleteIndex);
27             this.keyIndexMap.remove(key);
28             // update indexKeyMap
29             this.indexKeyMap.put(deleteIndex, lastKey);
30             this.indexKeyMap.remove(lastIndex);
31         }
32     }
33 
34     public String getRandom() {
35         if (size == 0) {
36             return null;
37         }
38         int randomIndex = (int) (Math.random() * this.size);    // 0 ~ size-1
39         return indexKeyMap.get(randomIndex);
40     }
41 }

3、认识布隆过滤器

布隆过滤器:

布隆过滤器(Bloom Filter)是一种节省空间的概率数据结构，由Burton Howard Bloom在1970年提出，用来测试一个元素是否在一个集合里。

有可能”误报“，但肯定不会”错报“：对布隆过滤器的一次查询要么返回“可能在集合中“，要么”肯定不在集合里“。

判断一个元素是否在一个集合中:
判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较来确定。把元素放到链表、平衡二叉树、散列表或数组里

以上结构的检索时间复杂度分别为O(n), O(logn), O(n/k)，O(n)。而布隆过滤器(Bloom Filter)也是用于检索一个元素是否在一个集合中，它的空间复杂度

是固定的常数O(m)，而检索时间复杂度是固定的常数O(k)。相比而言，有1%误报率和最优值k的布隆过滤器，每个元素只需要9.6个比特位--无论元素的大小。

这种优势一方面来自于继承自数组的紧凑性，另外一方面来自于它的概率性质。1%的误报率通过每个元素增加大约4.8比特，就可以降低10倍

布隆过滤器原理:

布隆过滤器是一种多哈希函数映射的快速查找算法。它可以判断出某个元素肯定不在集合里或者可能在集合里，即它不会漏报，但可能会误报。

通常应用在一些需要快速判断某个元素是否属于集合，但不严格要求100％正确的场合布隆过滤器需要一个位数组，这点和位图类似。还需要k个映射函数，这点和hash表类似

布隆过滤器实现步骤:
1）加入元素
首先，将长度为m个位数组的所有的位都初始化为0 其中的每一位都是一个二进制位。对于有n个元素的集合S={s1,s2,...,sn}，通过k个映射函数{f1,f2,...,fk}，将集合s中的每个元素

映射为k个值{b1,b2,..,bk}然后%m，最后再将位数组中的与之对应的b1,b2,...,bk位设置为1。这样，就将一个元素映射到k个二进制位

2）检查元素是否存在
如果要查找某一个元素是否在集合S中。就可以通过映射函数{f1,f2,...,fk}得到k个值{b1,b2,..,bk}，然后判断位数组中对应的b1,b2,...,bk位是否都为1，如果全部为1，则该元素在集合S中，

否则，就不在集合S中。但有没有误判的情况呢？即对应的位数组的位都为1，但元素却不在集合中。答案是有可能会有误判的情况，但这个概率很小，通常在万分之一以下

布隆过滤器计算相关:

布隆过滤器失误率：位数组越大失误率越低
失误率计算公式: m = -(n * lnP)/(ln2)^2 n =》样本量 P =》预期失误率
当n = 100亿 P = 0.001的时候 m为131,571,428,572bit => 22.3G空间
布隆过滤器哈希函数个数计算：k = ln2 * m/n = 0.7 * m/n => 13个
布隆过滤器真实失误率：当m和k向上取整时的正式失误率 = (1 - e ^ (-(n*k)/m) ) ^ k

布隆过滤器优缺点和应用：
优点：

存储空间和插入/查询时间都是常数，远远超过一般的算法
Hash函数相互之间没有关系，方便由硬件并行实现
不需要存储元素本身，在某些对保密要求非常严格的场合有优势

缺点:

有一定的误识别率
删除困难

应用:

搜索引擎中的海量网页去重
leveldb等数据库中快速判断元素是否存在，可以显著减少磁盘访问

4、认识一致性哈希

传统负载均衡：有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务

以存储及查询key-value为例：

存储：请求随机打到前端的负载均衡服务器上，前端服务器对key进行hash，假设后端服务器有3个那么将hash得到的值%3最后得到0或1或2 然后根据这个结果将key-value存到对应的服务器上
查询：前端先hash然后根据hash的值%3的结果去相应的后端服务器上查询

传统负载均衡带来的问题：

当扩充节点(加后端服务器)时需要把原先所有存储的key-value进行相应的重新计算比如后端服务器由3变成100时就需要重新计算然后重新分配这些key-value到后端服务器上

这样做的代价是极高的我们可以使用一致性哈希来解决这个问题让扩充的代价变得极低

一致性哈希:
一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法，常用于负载均衡。Memcached client也选择这种算法，解决将key-value均匀分配到众多Memcached server

上的问题。它可以取代传统的取模操作，解决了取模操作无法应对增删Memcached Server的问题(增删server会导致同一个key,在get操作时分配不到数据真正存储的server，命中率会急剧下降)

一致性哈希步骤:

将整个哈希值空间组织成一个虚拟的圆环，如假设某哈希函数H的值空间为0 - (2^32)-1（即哈希值是一个32位无符号整形）整个空间按顺时针方向组织
将各个服务器使用H进行一个哈希，具体可以选择服务器的ip或主机名作为关键字进行哈希，这样每台机器就能确定其在哈希环上的位置
接下来使用如下算法定位服务器：将数据key使用相同的函数H计算出哈希值h，通根据h确定此数据在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位到的服务器

一致性哈希优化:
为了使一致性哈希的分布结果更均匀我们将每个服务器分成1000个节点用一个路由表保存节点和服务器的关系
在上面的步骤中我们是直接用服务器进行哈希，现在我们用节点值进行哈希，这样可以保存服务器的分布更均匀
在保存和读取时根据路由表确定key该用哪个服务器来存放或读取在删除服务器和添加服务器时以为不是直接
用服务器来hash 而是用的1000个节点所以最后服务器的分布范围基本上是均匀的

5、并查集

什么是并查集：

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按
一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来
反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，
往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛
规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示

并查集两大功能:

合并: union =》将两个不相交的子集合合并成一个大集合(参数是两个集合中的元素)
查找: find =》查找某个元素所在的集合，返回该集合的代表元素 =》 isSameSet
合并查找的时间复杂度：查询次数和合并次数总的次数超过或逼近O(N)次时单次操作时间复杂度都是O(1)级别

并查集扁平优化：在查找的过程中将节点元素向上一直到代表节点中的所有节点都直接指向代表节点(将树打扁平)以便下一次合并和查找相同的节点时提高效率

注意：并查集初始化的时候必须把所有数据样本给它(不能针对流)

并查集实现：

 1 // 并查集实现
 2 public class UnionFind {
 3     public static class Node<T> {
 4         // T is whatever you like eg: String, Int, Char, Double 、、、
 5         public T value;
 6         public Node(T v) {
 7             this.value = v;
 8         }
 9     }
10             
11     public static class UnionFindSet {
12         // fatherMap: key is child, value is father
13         // sizeMap: the size of the node in set
14         public HashMap<Node, Node> fatherMap;
15         public HashMap<Node, Integer> sizeMap;
16             
17         public UnionFindSet(List<Node> nodes) {
18             // init the map
19             fatherMap = new HashMap<Node, Node>();
20             sizeMap = new HashMap<Node, Integer>();
21             for (Node node : nodes) {
22                 // one Node become one set
23                 fatherMap.put(node, node);
24                 sizeMap.put(node, 1);
25             }
26         }
27             
28         private Node findHead(Node node) {
29             // find the head of a set
30             Node father = fatherMap.get(node);
31             if (father != node) {
32                 father = findHead(father);
33             }
34             fatherMap.put(node, father); // 将链变扁平
35             return father;
36         }
37         
38         // ================================
39         // extrenal useable method
40         public boolean isSameSet(Node a, Node b) {
41             // to judge a two node in a same set
42             return findHead(a) == findHead(b);
43         }
44             
45         public void union(Node a, Node b) {
46             // to union two set by two node
47             if (a == null || b == null) {
48                 return;
49             }
50             Node aHead = findHead(a);
51             Node bHead = findHead(b);
52             if (aHead != bHead) {
53                 int aSetSize = sizeMap.get(aHead);
54                 int bSetSize = sizeMap.get(bHead);
55                 int size = aSetSize + bSetSize;        // the size of after union
56                 if (aSetSize <= bSetSize) {
57                     // union a to b
58                     fatherMap.put(aHead, bHead);
59                     sizeMap.put(bHead, size);
60                 } else {
61                     // union b to a 
62                     fatherMap.put(bHead, aHead);
63                     sizeMap.put(aHead, size);
64                 }
65             }
66         }
67     }
68 }

6、经典的岛问题

题目描述：

岛问题是一个经典的问题，描述如下:

一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？
举例：
0 0 1 0 1 0
1 1 1 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0
这个矩阵中有三个岛

经典思路：

传统思路就是从左上角遍历到右下角一旦遇到1就递归将1的上下左右(1相邻所有区域)的数改成2
把res+1 然后这次递归完了就继续遍历又遇到1就继续上面的递归依次下去直到最后一个点

代码：

 1 public class IslandProblemByDFS {
 2     public static void infect(int[][] arr, int i, int j, int N, int M) {
 3         if (i < 0 || i >= N || j < 0 || j >= M || arr[i][j] != 1) {
 4             return;
 5         }
 6         arr[i][j] = 2;
 7         infect(arr, i + 1, j, N, M);
 8         infect(arr, i - 1, j, N, M);
 9         infect(arr, i, j + 1, N, M);
10         infect(arr, i, j - 1, N, M);
11     }
12     
13     public static int countIslands(int[][] arr) {
14         if (arr == null || arr[0] == null) {
15             return 0;
16         }
17         int N = arr.length;
18         int M = arr[0].length;
19         int res = 0;
20     
21         for (int i = 0; i < N; i++) {
22             for (int j = 0; j < M; j++) {
23                 if (arr[i][j] == 1) {
24                     res++;
25                     infect(arr, i, j, N, M);
26                 }
27             }
28         }
29         return res;
30     }
31         
32     public static void main(String[] args) {
33         int[][] m1 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
34                 { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
35                 { 0, 1, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
36                 { 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
37         System.out.println(countIslands(m1));
38         int[][] m2 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
39                 { 0, 1, 1, 1, 1, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 },
40                 { 0, 1, 1, 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 },
41                 { 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, };
42         System.out.println(countIslands(m2));
43     }
44     
45 }

并查集思路：

把一块大区域分成若干个小区域然后对这若干个小区域用上面的方法求得每个小区域的岛的数量，然后再边界出判断岛是否相连，如果相连就把岛连起来然后把岛的总数量减1

每个岛都是一个并查集岛中每个元素都指向岛的第一个元素边界判断时如果两个岛相连(findHead相等) 那么将一个岛的集合并到另一个岛中然后把岛的总数减1