认识哈希函数
- 哈希函数的输入域是无穷大的，输出域是有限的
- 输入相同的值，返回结果都是一样的，没有随机成分
- u：if in —> same out 不同的输入也有可能有相同的输出（哈希碰撞）
它能把一定量的数据离散的放到同一个作用域里，使得它的均匀性和离散性得到保障，数据量小时效果不明显
哈希表的实现
-
设计RandomPool结构
【题目】设计一种结构，在该结构中有如下三个功能：
insert(key)：将某个key加入到该结构，做到不重复加入
- delete(key)：将原本在结构中的某个key移除
- getRandom()：等概率随机返回结构中的任何一个key。
【要求】Insert、delete和getRandom方法的时间复杂度都是O(1)
public class 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) {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 -1return 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());}}
详解布隆过滤器
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
首先要了解位图
public static void main(String[] args) {
// a 32bit java中int类型占32位
int a = 0;
int[] arr = new int[10]; // 32bit * 10 -> 320bits
// arr[0] int 0 ~ 31
// arr[1] int 32 ~ 63
// arr[2] int 64 ~ 95
int i = 178; // 想取得第178个bit的状态
int numIndex = 178 / 32; // 查找178在数组中的哪位上 arr[n]
int bitIndex = 178 % 32; // 查找178在arr[n]上的哪一位上
// 拿到178位的状态
// arr[numIndex] >> (bitIndex) 178位的信息跑到最右侧
// 想找某一位就让某一位移到最右侧，然后和1与
int s = ( (arr[numIndex] >> (bitIndex)) & 1);
// 请把178位的状态改成1
arr[numIndex] = arr[numIndex] | (1 << (bitIndex));
i = 178; // 请把178位的状态改成0
arr[numIndex] = arr[numIndex] & (~ (1 << bitIndex));
i = 178; // 请把178位的状态拿出来
// bit 0 1
int bit = (arr[i / 32] >> (i % 32)) & 1;
}
布隆过滤器就是一个位图
比如黑明单网站，将所有的黑名单网站放到位图里：
定义m大小的位图，k个哈希函数
- 先找几个哈希函数，然后将url放到哈希函数里将返回值对应的位的状态进行改变，所有的哈希函数返回值都在位图里进行改变为1
如果想要判断某一个url是否在位图里，就将所有的状态全部查出来，如果全部为1就在过滤器里，否则没有。
由上面推出
黑（不合法url） ——-> 白（合法url） 不可能 因为你的状态在过滤器里面完全存在
- 白（合法url） ———> 黑（不合法url） 可能 如果过滤器的大小设置的很小，然后数据量很大，那么所有的状态可能都会被改过，很可能出错。
- 不适合删除，因为删除是改变状态，但改某一个状态可能会影响其它数据
- 位图很大，失误率会很小。位图很小，失误率会很大。
- 哈希函数的个数不能太多，也不能太少。
- 如果太多，一个数据就得改变很多个状态，如果数据很多，那么失误率会增加。
- 太少不够精准
-
设计布隆过滤器的三个公式
如果面试时，问到有关黑名单这种问题，可以问一下面试管是否有失误率，如果有就是使用布隆过滤器
n = 样本量 p = 失误率
计算布隆过滤器需要多少位，有可能计算出小数，向上取整
k = ln2 m / n % 0.7 m / n 计算需要多少个哈希函数
一致性哈希原理
在前端服务器上有一个数组，这个数组里面存的是后面存储服务器的哈希值的值，并且是按顺序来存储的，这样的在接收到一个请求的话，就很方便使用二分法查找到这个请求对应所应该对应的服务器。
上面的机器成环存在两个问题：
这两个问题都是有哈希函数的性质所引起的，哈希函数是离散的函数，是均匀分布的，但是前提是量，数量要多，对于上面的问题来说也就是服务器的数量要多，量起来之后才能体现哈希的特点。
- 在服务器数量较少的时候，哈希域 （也就是上图中的那个环），不一定会被服务器均分
- 就算你解决了第一个问题，服务器均分了哈希域，当你再增加服务器的时候，哈希域又注定不会被均分。
上面两个问题是由哈希函数的性质引起的，那么又该如何解决上面的问题呢？
一个方法，虚拟结点技术：
假设环还是那个环，服务器还是那三台服务器
M1，M2, M3
给M1在哈希域环上虚拟出10000个结点，M2也是，M3也是，此时将有30000个结点遍布在环上，归属于M1的10000个结点中应该存放的数据，都存放在M1上。此时哈希域上的结点数量起来了，哈希域也就自然被均分了。
第一个问题解决，当增加服务器数量的时候也是类似的方法，将服务器虚拟出大量的结点，这样就达到了均分的目的。第二个问题也被解决了
关于服务器虚拟出来的节点类似于路由器中的路由表，可以根据路由表找到结点，也可以根据节结点知道，这个结点属于哪一个路由器。岛问题
【题目】一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连，如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛？
【举例】001010 111010 100100 000000
这个矩阵中有三个岛
【进阶】如何设计一个并行算法解决这个问题
public class 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) {
return;
}
m[i][j] = 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));
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));
}
}
若有收获，就点个赞吧
0 人点赞
