算法学习系列（7）——哈希表、布隆过滤器、一致性哈希、岛问题、并查集_基于fpga实现布隆过滤器
赞
踩
1.认识哈希函数和哈希表
哈希函数及其重要，在大数据的题目中常考。下边介绍几个哈希函数相关的概念：
1.1什么是 Hash
Hash（哈希），又称“散列”。
散列（hash）英文原意是“混杂”、“拼凑”、“重新表述”的意思。
在某种程度上，散列是与排序相反的一种操作，排序是将集合中的元素按照某种方式比如字典顺序排列在一起，而散列通过计算哈希值，打破元素之间原有的关系，使集合中的元素按照散列函数的分类进行排列。
在介绍一些集合时，我们总强调需要重写某个类的 equlas() 方法和 hashCode() 方法，确保唯一性。这里的 hashCode() 表示的是对当前对象的唯一标示。计算 hashCode 的过程就称作 哈希。
1.2为什么要有 Hash
我们通常使用数组或者链表来存储元素，一旦存储的内容数量特别多，需要占用很大的空间，而且在查找某个元素是否存在的过程中，数组和链表都需要挨个循环比较，而通过 哈希 计算，可以大大减少比较次数。
1.3举个栗子：
现在有 4 个数 {2,5,9,13}，需要查找 13 是否存在。
1.使用数组存储，需要新建个数组 new int[]{2,5,9,13}，然后需要写个循环遍历查找：
int[] numbers = new int[]{2,5,9,13};
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] == 13){
System.out.println("find it!");
return;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
这样需要遍历 4 次才能找到，时间复杂度为 O(n)。
2.而假如存储时先使用哈希函数进行计算，这里我随便用个函数：
H[key] = key % 3;
- 1
四个数 {2,5,9,13} 对应的哈希值为：
H[2] = 2 % 3 = 2;
H[5] = 5 % 3 = 2;
H[9] = 9 % 3 = 0;
H[13] = 13 % 3 = 1;
然后把它们存储到对应的位置。
当要查找 13 时，只要先使用哈希函数计算它的位置，然后去那个位置查看是否存在就好了，本例中只需查找一次，时间复杂度为 O(1)。
因此可以发现，哈希 其实是随机存储的一种优化，先进行分类，然后查找时按照这个对象的分类去找。
哈希通过一次计算大幅度缩小查找范围，自然比从全部数据里查找速度要快。
比如你和我一样是个剁手族买书狂，家里书一大堆，如果书存放时不分类直接摆到书架上（数组存储），找某本书时可能需要脑袋从左往右从上往下转好几圈才能发现；如果存放时按照类别分开放，技术书、小说、文学等等分开（按照某种哈希函数计算），找书时只要从它对应的分类里找，自然省事多了。
1.4哈希函数
哈希的过程中需要使用哈希函数进行计算。
哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。
表示为：
address = H [key]
哈希函数的实现等查看：哈希函数
1.5 哈希函数的特点：
- 1）Hash可用于任意大小的数据块；
- (2)hash可以接受任意长度的信息，并将其输出成固定长度的消息摘要；
- (3)单向性。给定一个输入M，一定有一个h与其对应，满足H(M)=h，反之，则不行，算法操作是不可逆的。
- (4)抗碰撞性。给定一个M,要找到一个M’满足是不可H(M)=H(M’)是不可能的。即不能同时找到两个不同的输入使其输出结果完全一致。
- (5)低复杂性：算法具有运算的低复杂性。
1.6 哈希表常用的功能演示
代码：
//哈希表的增删改查的复杂度是近似于O(1)，实际应该是O(log5N之类的形式) public class Code_01_HashMap { public static void main(String[] args) { HashMap<String, String> map = new HashMap<>(); map.put("wang", "31"); System.out.println(map.containsKey("wang")); System.out.println(map.containsKey("laowu")); System.out.println("========================="); System.out.println(map.get("wang")); System.out.println(map.get("laowu")); System.out.println("========================="); System.out.println(map.isEmpty()); System.out.println(map.size()); System.out.println("========================="); System.out.println(map.remove("wang")); System.out.println(map.containsKey("wang")); System.out.println(map.get("wang")); System.out.println(map.isEmpty()); System.out.println(map.size()); System.out.println("========================="); map.put("wang", "31"); System.out.println(map.get("wang")); map.put("wang", "32"); System.out.println(map.get("wang")); System.out.println("========================="); map.put("wang", "31"); map.put("lao", "32"); map.put("wu", "33"); for (String key : map.keySet()) { System.out.println(key); } System.out.println("========================="); for (String values : map.values()) { System.out.println(values); } System.out.println("========================="); map.clear(); map.put("A", "1"); map.put("B", "2"); map.put("C", "3"); map.put("D", "1"); map.put("E", "2"); map.put("F", "3"); map.put("G", "1"); map.put("H", "2"); map.put("I", "3"); for (Entry<String, String> entry : map.entrySet()) { String key = entry.getKey(); String value = entry.getValue(); System.out.println(key + "," + value); } System.out.println("========================="); // you can not remove item in map when you use the iterator of map // for(Entry<String,String> entry : map.entrySet()){ // if(!entry.getValue().equals("1")){ // map.remove(entry.getKey()); // } // } // if you want to remove items, collect them first, then remove them by // this way. List<String> removeKeys = new ArrayList<String>(); for (Entry<String, String> entry : map.entrySet()) { if (!entry.getValue().equals("1")) { removeKeys.add(entry.getKey()); } } for (String removeKey : removeKeys) { map.remove(removeKey); } for (Entry<String, String> entry : map.entrySet()) { String key = entry.getKey(); String value = entry.getValue(); System.out.println(key + "," + value); } System.out.println("========================="); } }
- 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
2.设计RandomPool结构
【题目】 设计一种结构，在该结构中有如下三个功能： insert(key)：将某个key加入到该结构，做到不重复加入。 delete(key)：将原本在结构中的某个key移除。 getRandom()： 等概率随机返回结构中的任何一个key。
【要求】 Insert、delete和getRandom方法的时间复杂度都是 O(1)
public class Code_02_RandomPool { public static class Pool<K> { private HashMap<K, Integer> keyIndexMap; private HashMap<Integer, K> indexKeyMap; private int size; public Pool() { this.keyIndexMap = new HashMap<K, Integer>(); this.indexKeyMap = new HashMap<Integer, K>(); this.size = 0; } public void insert(K key) { if (!this.keyIndexMap.containsKey(key)) { this.keyIndexMap.put(key, this.size); this.indexKeyMap.put(this.size++, key); } } public void delete(K key) { //将指定位置的key删除，并将该洞补全 if (this.keyIndexMap.containsKey(key)) { int deleteIndex = this.keyIndexMap.get(key); int lastIndex = --this.size; K lastKey = this.indexKeyMap.get(lastIndex); this.keyIndexMap.put(lastKey, deleteIndex); this.indexKeyMap.put(deleteIndex, lastKey); this.keyIndexMap.remove(key); this.indexKeyMap.remove(lastIndex); } } public K getRandom() { if (this.size == 0) { return null; } int randomIndex = (int) (Math.random() * this.size); // 0 ~ size -1 return this.indexKeyMap.get(randomIndex); } } public static void main(String[] args) { Pool<String> pool = new Pool<String>(); pool.insert("zuo"); pool.insert("cheng"); pool.insert("yun"); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); System.out.println(pool.getRandom()); } }
- 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
3.认识布隆过滤器（搜索面试中必考题目）
3.1布隆过滤器含义：
布隆过滤器在wiki上的介绍: 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难
3.2 为什么要用布隆过滤器？
HashMap 的问题: 讲述布隆过滤器的原理之前，我们先思考一下，通常你判断某个元素是否存在用的是什么？应该蛮多人回答 HashMap 吧，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。
还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。
事实上，布隆过滤器被广泛用于网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统以及解决缓存穿透问题。通过介绍已经知晓布隆过滤器的作用是检索一个元素是否在集合中。可能有人认为这个功能非常简单，直接放在redis中或者数据库中查询就好了。又或者当数据量较小，内存又足够大时，使用hashMap或者hashSet等结构就好了。但是如果当这些数据量很大，数十亿甚至更多，内存装不下且数据库检索又极慢的情况，我们应该如何去处理？这个时候我们不妨考虑下布隆过滤器，因为它是一个空间效率占用极少和查询时间极快的算法，但是需要业务可以忍受一个判断失误率。
3.3 哈希函数
哈希函数的性质:
- 经典的哈希函数都有无限大的输入值域(无穷大)。
- 经典的哈希函数的输出域都是固定的范围(有穷大，假设输出域为S)
- 当给哈希函数传入相同的值时，返回值必一样
- 当给哈希函数传入不同的输入值时，返回值可能一样，也可能不一样。
- 输入值会尽可能均匀的分布在S上
前三点都是哈希函数的基础，第四点描述了哈希函数存在哈希碰撞的现象，因为输入域无限大，输出域有穷大，这是必然的，输入域中会有不同的值对应到输入域S中。第五点事评价一个哈希函数优劣的关键，哈希函数越优秀，分布就越均匀且与输入值出现的规律无关。比如存在"hash1",“hash2”,"hash3"三个输入值比较类似，经过哈希函数计算后的结果应该相差非常大，可以通过常见的MD5和SHA1算法来验证这些特性。如果一个优秀的函数能够做到不同的输入值所得到的返回值可以均匀的分布在S中，将其返回值对m取余(%m),得到的返回值可以认为也会均匀的分布在0~m-1位置上。
3.4基于缓存业务分析布隆过滤器原理
在大多应用中，当业务系统中发送一个请求时，会先从缓存中查询；若缓存中存在，则直接返回；若返回中不存在，则查询数据库。其流程如下图所示:
缓存穿透：当请求数据库中不存在的数据，这时候所有的请求都会打到数据库上，这种情况就是缓存穿透。如果当请求较多的话，这将会严重浪费数据库资源甚至导致数据库假死。
接下来开始介绍布隆过滤器。有一个长度为m的bit型数组，如我们所知，每个位置只占一个bit，每个位置只有0和1两种状态。假设一共有k个哈希函数相互独立，输入域都为s且都大于等于m，那么对同一个输入对象（可以想象为缓存中的一个key），经过k个哈希函数计算出来的结果也都是独立的。对算出来的每一个结果都对m取余，然后在bit数组上把相应的位置设置为1(描黑)，如下图所示：
至此一个输入对象对bit array集合的影响过程就结束了，我们可以看到会有多个位置被描黑，也就是设置为1。接下来所有的输入对象都按照这种方式去描黑数组，最终一个布隆过滤器就生成了，它代表了所有输入对象组成的集合。
那么如何判断一个对象是否在过滤器中呢？假设一个输入对象为hash1,我们需要通过看k个哈希函数算出k个值，然后把k个值取余（%m），就得到了k个[0,m-1]的值。然后我们判断bit array上这k个值是否都为黑，如果有一个不为黑，那么肯定hash1肯定不在这个集合里。如果都为黑，则说明hash1在集合里，但有可能误判。因为当输入对象过多，而集合过小，会导致集合中大多位置都会被描黑，那么在检查hash1时，有可能hash1对应的k个位置正好被描黑了，然后错误的认为hash1存在集合里。
例子：将30000加入布隆过滤器中。底层用的是int类型的数组，长度为1000。
- 30000的含义是将数组中第30000个bit描黑，并非实际的数字。
- 数组长度1000，一共可容纳32*1000个bit。
3.5 控制布隆过滤器的误判率
如果bit array集合的大小m相比于输入对象的个数过小，失误率就会变高。这里直接引入一个已经得到证明的公式，根据输入对象数量n和我们想要达到的误判率为p计算出布隆过滤器的大小m和哈希函数的个数k.
布隆过滤器的大小m公式:
哈希函数的个数k公式:
布隆过滤器真实失误率p公式：
假设我们的缓存系统，key为userId，value为user。如果我们有10亿个用户，规定失误率不能超过0.01%，通过计算器计算可得m=19.17n，向上取整为20n，也就是需要200亿个bit，换算之后所需内存大小就是2.3G。通过第二个公式可计算出所需哈希函数k=14.因为在计算m的时候用了向上取整，所以真是的误判率绝对小于等于0.01%。
更多概念：布隆过滤器
3.6布隆过滤器的实现
public class BloomFilter { /** * bitSet的大小 */ private static final int DEFAULT_SIZE = 2 << 24; /** * 选取的hash函数 */ private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134}; /** * bitSet每一位只能是true或false 其实就是bit数组说的0或者1 */ private BitSet bits = new BitSet(DEFAULT_SIZE); private SimpleHash[] func = new SimpleHash[SEEDS.length]; public static void main(String[] args) { String value = "wxwwt@gmail.com"; BloomFilter filter = new BloomFilter(); System.out.println(filter.contains(value)); filter.add(value); System.out.println(filter.contains(value)); } public BloomFilter() { for (int i = 0; i < SEEDS.length; i++) { func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]); } } public void add(String value) { for (SimpleHash f : func) { bits.set(f.hash(value), true); } } public boolean contains(String value) { if (value == null) { return false; } boolean ret = true; for (SimpleHash f : func) { ret = ret && bits.get(f.hash(value)); } return ret; } public static class SimpleHash { private int cap; private int seed; public SimpleHash(int cap, int seed) { this.cap = cap; this.seed = seed; } /** * 计算hash值 * * @param value * @return */ public int hash(String value) { int result = 0; int len = value.length(); for (int i = 0; i < len; i++) { result = seed * result + value.charAt(i); } return (cap - 1) & result; } } }
- 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
其实更多时候用的是谷歌（guava）中实现的布隆过滤器。
3.4 布隆过滤器使用场景
1.网络爬虫可以通过布隆过滤器判断当前的url是否已经爬取过；
2.防止恶意链接或者垃圾邮件，短信之类的，从数十亿个链接或者垃圾邮件中判断该链接（邮件发件人，短信发信人是否是在黑名单中），
平时手机上来电提示写着对方式恶意推销，外卖，这种场景也是可以用布隆过滤器来判断；
3.防止缓存击穿，将已存在的缓存放到布隆中，当使用缓存的时候，可以先访问布隆过滤器，存在则访问缓存，不存在则访问数据库；
4.检索系统查询当前的输入信息是否存在于数据库中，也可以使用布隆过滤器。
4.认识一致性哈希（服务器抗压/负载均衡）
详情看：一致性哈希
5.岛问题
一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右 四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个 矩阵中有多少个岛？
举例：
这个矩阵中有三个岛。
首先想到：使用经典的递归方法来解决：
public class Code_03_Islands { public static int countIslands(int[][] m) { if (m == null || m[0] == null) { return 0; } int N = m.length;//行 int M = m[0].length;//列 int res = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (m[i][j] == 1) { res++; infect(m, i, j, N, M);//感染函数 } } } return res; } public static void infect(int[][] m, int i, int j, int N, int M) {//这个递归会不断地执行的，遇到了下边的这个返回条件才会终止 if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] != 1) {//只要行或者列小于0，或者大于边界了，或者值不等于1，直接返回 return; } m[i][j] = 2;//被感染的数都置成2 infect(m, i + 1, j, N, M);//感染当前数的上一行的数字 infect(m, i - 1, j, N, M);//感染当前数的下一行的数字 infect(m, i, j + 1, N, M);//感染当前数的右边一行数字 infect(m, i, j - 1, N, M);//感染当前数的左边一行数字 } public static void main(String[] args) { int[][] m1 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 }, { 0, 1, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, { 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, }; System.out.println(countIslands(m1));//3 int[][] m2 = { { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 1, 1, 1, 1, 0 }, { 0, 1, 1, 1, 0, 0, 0, 1, 0 }, { 0, 1, 1, 0, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 0, 1, 1, 0, 0 }, { 0, 0, 0, 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 }, }; System.out.println(countIslands(m2));//1 } }
- 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
如果对于一个超大型的矩阵可以使用下边的这种划分的方法来思考，使用并查集的算法思想来解决。。。
