认识哈希函数----- out f(in data)
1）输入参数data，假设是in类型，特征：可能性无穷大，比如str类型的参数。
2）输出参数类型out，特征：可能性可以很大，但一定是有穷尽的。
3）哈希函数没有任何随机的机制，固定的输入一定是固定的输出。
4）输入无穷多但输出值有限，所以不同输入也可能输出相同（哈希碰撞）。
5）再相似的不同输入，得到的输出值，会几乎均匀的分布在out域上。
重点：第5条！
哈希函数作用：可以把数据根据不同值，几乎均匀的分开。
布隆过滤器（不会把已经有的数据判断为没有，但是会把没有的数据误判成已有）
1）利用哈希函数的性质。
2）每一条数据提取特征。
3）加入描黑库。
布隆过滤器的实现细节：
- 给点长度位数组bitArr。
- k个不同的哈希函数。
- 预期失误率。
- 用过滤url做列子，同一个url,经过k个哈希函数求值，取模，会在位数组上留下k个点，若这k个点都命中了那么说明在以前url被标记过，否则没有被标记过。
位数组的实现
- java中一个整形为四字节32位，我们可以用一个整形数组来代表位数组，列入int[] bitMap = new int[100];表示一个3200位的位数组，
- 获取某一位上的状态
// 假如获取第456位的状态
int[] bitMap = new int[100]
// 先计算此位位于数组中那个整数元素中
int index = 456 / 32;
int bitA = bitMap[index];
// 计算在这个整数的哪一位
int bit = 456 % 32;
// 提取这一位的值,吧这个整数向右移动bit位，
int status = (bitMap[index] >> bit) & 1;
- 设置某一位的状态
// 假如设置第456位的状态为1
int[] bitMap = new int[100]
// 先计算此位位于数组中那个整数元素中
int index = 456 / 32;
int bitA = bitMap[index];
// 计算在这个整数的哪一位
int bit = 456 % 32;
// 设置这一位的值,吧这个整数向右移动bit位，
int status = bitMap[index] | (1 << bit);
- 由于数组的长度有限，若需更大的数组，可以用Long,如果也不够可以用二维数组。
布隆过滤器的三个重要公式
1，假设数据量为n，预期的失误率为p（布隆过滤器大小和每个样本的大小无关）。
布隆过滤器大小
3，根据m和n，算出Bloom Filter需要多少个哈希函数，向上取整，记为k。
图片2.png
4，根据修正公式，算出真实的失误率p_true。
图片3.png
- 先确定数据量，允许的预期失误率。
应用：
- HDFS文件系统。
- Reids。
一致性哈希
分布式存储结构最常见的结构
1）哈希域变成环的设计。
2）虚拟节点技术。
并行算法
- 岛问题：一个只有0和1两种数字的二维矩阵中，上下左右能练成一片的1，算一个岛，返回矩阵中，一共有几个岛。
/**
*
* 岛问题：一个只有0和1两种数字的二维矩阵中，上下左右能练成一片的1，
* 算一个岛，返回矩阵中，一共有几个岛。
*
*/
public class DaoProblem {
public static int daoProblem(int[][] matrix){
if(matrix == null || matrix.length == 0){
return 0;
}
// 遍历每个节点都去感染，每感染一轮岛屿数量加一
int sum = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] == 1){
// 当前点是1时才去感染
sum++;
effect(matrix,i,j);
}
}
}
return sum;
}
// 函数返回i , j位置可以向后感染的区域全部变成2，知道不能继续感染
private static void effect(int[][] matrix,int i,int j){
if(i < 0 || i >= matrix.length
|| j < 0 || j >= matrix[0].length
|| matrix[i][j] != 1){
// 如果位置越界，且当前位置不是1则结束感染
return;
}
// 否则吧感染位置变为1，继续向i,j的四周感染
matrix[i][j] = 2;
effect(matrix,i,j-1);
effect(matrix,i,j+1);
effect(matrix,i+1,j);
effect(matrix,i-1,j);
}
public static void main(String[] args) {
int[][] arr = {{0,0,0,0,1,1},
{1,1,0,0,1,1},
{1,1,0,0,1,0},
{0,1,0,0,0,0}};
System.out.println(daoProblem(arr));
}
}
