认识哈希函数----- 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（布隆过滤器大小和每个样本的大小无关）。

布隆过滤器大小

图片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));
    }
}