一、哈希函数（粗略看）

        1、概念及相关性质

1）输入域无穷，输出域有限，如MD5：返回值为0~-1，SHal：返回值为0~，java：0~

2）相同输入，相同输出，没有随机成分

3）不同输入，可能会有相同输出（哈希碰撞）

4）离散&均匀

        2、哈希碰撞

当两个不同的键通过哈希函数映射到同一个索引时，就会发生冲突，常见的解决冲突的方法有：

        1）链地址法：每个索引位置存储一个链表，发生冲突时，将新的元素添加到链表中

        2）开放地址法：当发生冲突时，寻找下一个可用位置，可以通过线性探测、二次探测或双重哈希等方法实现 

        3、哈希表扩容

1）哈希表在使用过程中，随着元素的增加，冲突的可能性也会增加，从而影响性能。因此，当哈希表的负载因子（即元素数量与哈希表容量的比例）超过某个阈值时，就需要进行扩容

2）扩容通常涉及创建了一个更大的哈希表，并将所有元素重新哈希到新的表中

加入了N个元素，经历了几次扩容？O(logN)次，扩容代价O(N），总代价O(N*logN)，单词扩容为O(logN)。哈希表增删改查的时间代价为O(1)

【设计RandomPool结构】

设计一种结构，要有以下三个功能：

        1）Insert(key)：将某个key加入到该结构，做到不重复加入

        2）delete(key)：将原本在该结构的某个key移除

        3）getRandom()：等概率随机返回结构中的任何key

实现需要三个东西：map1(str, index)，map2(index, str), int size = 0;

public class RamdonPool{
    public HashMap<K, Integer> map1;
    public HashMap<Integer, K> map2;
    int size;
    public RamdonPool(){
        this.map1 = new HashMap<>();
        this.map2 = new HashMap<>();
        this.size = 0;
    }

    public static void insert(K key){
        if(map1.containsKey(key)){
            return;
        }
        this.map1.put(key, size++);
        this.map2.put(this.size, key);
    }

    public static void delete(K key){
        if(!map.containsKey(key)){
            return;
        }
        int deleteIndex = map1.get(key);
        int lastIndex = --this.size;
        K lastKey = map1.get(lastIndex);
        this.map1.put(lastKey, deleteIndex);
        this.map2.put(deleteIndex, lastKey);
        this.map1.remove(key);
        this.map2.remove(lastIndex);
    }

    public static K getRandom(){
        if(this.size == 0) return null;
        int randomIndex = (int)(Math.random()*this.size) // 0~size-1
        return this.map2.get(randomIndex);
    }
}

二、布隆过滤器

注意：有删除行为就不能使用布隆过滤器

场景：设置一个100亿的URL黑名单，每个URL为64Byte，该集合有添加有查询但没删除

经典做法：用hashSet进行存储，但需要640GB的内存

布隆过滤器允许一定程度的失误率：

1）黑名单里的认为在白名单里（不会发生）

2）白名单里的认为在黑名单里（通过认为设计能达到万分之一的概率，但不可避免）

【位图相关概率】 bitarr bitmap

int[] arr = new int[10];  //32*10bits = 320bits
//arr[0]  表示 0~31
//arr[1]  表示 32~63
//arr[2]  表示 64~95

int i = 178;        //获得178位的计数，从0开始

int numIndex = i/32;        //数组上第几个数
int bitIndex = i%32;        //第几个数上的第几位

int bit = (arr[numIndex]>>bitIndex) & 1;

arr[numIndex] = arr[numIndex] | (1<<bitIndex);    //将i位的数字改为1
arr[numIndex] = arr[numIndex] & (~(1<<bitIndex));    //将i位的数字改为0

假设有m个bit数组，有k个hash函数

        1）黑名单建立过程：u1通过k个hash函数再%m，得到k个out1；u2通过k个hash函数再%m，得到k个out2....，描黑这些位置

        2）查询：某个url x，通过k个hash函数再%m，得到k个out x，去位图中拿状态，只有out x全为1时才认为集合里有

不确定的值：hash函数个数k，数组长度m

决定失误率：最关键的因素为位图长度m，k则由m和样本量决定

设置条件：n=样本量        P=失误率        与单样本大小无关

1）确认是否没有删除行为，仅查询

2）问失误

                ,P为失误率

，        向上取整

三、并查集

【岛问题】

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

【解法一】

感染过程：把连成一片的1找到并改成2（BFS思想）

如

001010

111010

100100

000000

找到第一个1，变成

002010

222010

200200

000000

public static int countIslands(int[][] matrix){
    int row = matrix.length;
    int col = matrix[0].length;
    int res = 0;
    for(int i = 0; i < row; i++){
        for(int j = 0; j < col; j++){
            if(matrix[i][j]==1){
                res++;
                infection(matrix, i, j, row, col);
            }
        }
    }
}

public static void infection(int[][] matrix, int i, int j, int row, int col){
    if(i<0 || i>row-1 || j<0 || j>col-1 || matrix[i][j]!=1){
        return;
    }
    //没越界，且当前位置为1
    matrix[i][j] = 2;
    infection(matrix, i+1, j, row, col);
    infection(matrix, i, j+1, row, col);
    infection(matrix, i-1, j, row, col);
    infection(matrix, i, j-1, row, col);
}

 【进阶】如何设计一个并行算法

举例

1111 | 1111

1000| 0001

1011| 1111

1011| 0000

1011| 1111

1000|0001

1111|1111

将(0,0)位置的1记为感染A点，标记边界并携带感染点，如(0, 3)边界的1记录感染点为A，(7, 3)边界的1记录感染点为A

同样的，(2, 2)位置的1记为感染B点，将(0, 4)位置的1记为感染C，(4, 4)位置的点记为感染D

【并查集】

操作一：将用户提供的所有样本都生成各自的集合

操作二：对外提供两个方法：

                一、查询两个样本是否为一个集合，返回布尔类型的值        boolean isSameSet

                二、将两个样本所在的集合的所有元素合成一个集合            void union

使用链表的话，方法一不是O(1)，对于链表a来说，要遍历链表b才知道是不是其中

使用哈希表的话，方法二不是O(1)，因为合并的时候要遍历

并查集能使得方法一和方法二的时间复杂度都为O(1)

举例：a、b、c、d、e，先生成顶部指针，指向自己

isSameSet(a, b) 比较顶部指针，不是同一个元素，返回false

union(a, b) 如果长度不一样，短的顶部指针改为长的顶部指针；长的一样，则b的顶部指针指向a

isSameSet(c, d)

union(c, d)

isSameSet(b, d)

union(b, d) 

最后形成一个无环图，a指向自己

        a - e

      /    \

    b      c  - d

public static class Element<V>{
    V value;
    public Element(V value){
        this.value = value;
    }
}

public static class UnionFindSet<V>{
    public HashMap<V, Element> elementMap;

    // key 某个元素 value 该元素的父
    public HashMap<Element<V>, Element<V>> fatherMap;

    // key 某个集合的元素代表 value 该集合的大小
    public HashMap<Element<V>, Integer> sizeMap;

    public static UnionFindSet(List<V> list){
        for(V value: list){
            Element<V> element = new Element(value);
            elementMap.put(value, element);
            fatherMap.put(element, element);
            sizeMap.put(element, 1);
        }
    }

    public static Element<V> findHead(V value){
        Stack<V> path = new Stack();        //记录找时的路
        Element<V> element = elementMap.get(value);
        while(fatherMap.get(element)!=element){
            path.add(element);
            element = fatherMap.get(element);
        }
        while(!path.isEmpty()){
            fatherMap.put(path.pop(), element);    //优化查找操作，找的时候把找过的路的父节点全改为顶节点，路径压缩
        }
        return element;
    }    

    public static boolean isSameSet(V a, V b){
        if(elementMap.containsKey(a)&&elementMap.containsKey(b)){
            return findHead(a)==findHead(b);
        } else {
            return false;
        }
    }

    public static void union(V a, V b){
        if(elementMap.containsKey(a)&&elementMap.containsKey(b)){
            Element<V> aF = fatherMap.get(elementMap.get(a));
            Element<V> bF = fatherMap.get(elementMap.get(b));
            if(aF!=bF){
                Element<V> big = sizeMap.get(aF)>sizeMap.get(bF)? aF: bF;
                Element<V> small = big==aF?bF: aF;
                fatherMap.put(small, big);
                sizeMap.put(big, sizeMap.get(big)+sizeMap.get(small);
                sizeMap.remove(small);   
            }
}