9 Hash&Bloom filter&一致性哈希&并查集&KMP&Manacher算法

1.HashMap

特点：
1）输入域无限，输出域有限
2）相同输入一定是相同输出，没有随机成分；不同的输入，可能输出相同（哈希碰撞）
3）输出离散，结果在域种分布均匀
4）应用：种子MD5（0 ~2^64-1）显示的bt文件是一个16位的16进制数
题目：40亿个整数的文件，每个整数无符号4字节，1G内存，求词频最大的前十个

<40,0000,0000个整数；
直接用Map：key表示整数（4B），value表示词频（4B-2^32=42亿，
满足最差40亿条相同记录）：空间爆炸。
1G/8B=，1G内存都做HashMap可以有1亿条记录
Hash值相同的放到同一号文件，假设有100个文件，那么每个文件就可以放1百万种数据
(https://www.cnblogs.com/LiuYanYGZ/p/10986246.html)

image.png

2.哈希表，以java HashMap为例

HashMap底层原理：
    JDK7：
        HashMap map = new HashMap();
        底层创建了长度为16的数组table，类型为Entry[]
        ..已经多次put..
        map.put(key1,value1)：
            首先，计算key1的hashCode方法，得到哈希值，此
                值经过某种方法得到在Entry中的存储位置：
   情况1----如果该位置为空，——key1-value1直接添加成功
            如果该位置不为空（一个或多个）
                比较key1和存在一个或多个数据的hash值：
   情况2----        都不同：——以链表形式添加成功
                    和某一个相同，继续比较key的equals方法：
                        如果相同：value替换当前的value
    情况3----             不同：——添加成功


    补充：关于情况2、3：链表存储在该位置
        扩容问题：超出阈值且非空时扩容，默认扩容为2倍

    JDK8：
        底层的不同：
        1.new HashMap()：底层没有创建长为16的数组
        2.底层数组存储Node[]类型，不是Entry了
        3.put方法：首次调用时创建长为16的数组（类似ArrayList）
        4.加入了红黑树
            当数组的某一个索引位置的元素以链表形式
            存在的数据个数大于8且当前数组长度大于64
            时候，此索引位置的数据改用红黑树存储；
            因为logN效率高

如果扩容后重新添加节点，成为新的hashMap，代价太大。N条记录扩容次数（logN）每次扩容O（N），平均时间复杂度为O（NlogN），故加入一条记录的平均扩容代价为O（logN）*
而工程上N一般小，认为CUDR逼近于O（1），还因为用户在线时候用的是老的Map，新的Map在后台离线构建，不影响用户操作（JVM）

3.RandomPool结构

image.png

为了get（Key）等概率且key不重复，所以用两个map，

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);
            //保证在indexKeyMap上的所有key是等概率的
                //如果直接删除，比如2，indexKeyMap就会出现空区域
                //0~1，3~size-1，而这种删除方法可以使得空区域消失，
                //并且新的indexKeyMap是0~size-2的 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);
        }

    }

4. 布隆过滤器（大数据问题）

Bloom
好处：省内存
坏处：必然存在失误率，正常的url可能会显示到黑名单，而黑名单内的url不会失误，就是宁可错杀，绝不放过。
位图：
Bloom就是一个大位图，长度为m个比特（占用m/8 Byte的空间），初始为全白（0）。对一个url通过hash1 mod m，可以得到对应的位置，同样用hash2，hash3..这些独立的hash函数得到对应的位置。
假设经历k个hash函数，最大会对k个位置描黑（可能存在重复描黑，描黑的位置不会变白），下一个url做同样的操作，一直做100亿个
如何查询url在黑名单中吗？通过k个hash函数mod m的位置都已经被描黑，那么它就在黑名单中，否则，肯定不属于黑名单
这样就会导致，某些不在黑名单的url，对应的所有位置也可能被描黑。如果m越小，那么失误率就会越高
N个样本，每个样本为S字节，准备的hash函数个数K，bloom位数m：
与S无关：只要保证样本可以作为hash的输入即可；

视图.png
参数计算

公式.png

如果得到m为小数，那么向上取整；
如果得到K为小鼠，那么同样向上取整；
最终重新计算出失误率；
hash函数的设计：只需要设计f1=A f2=B，那么以后的函数可以设置为A+iB，他们都是独立的*
因为使用了hash查询，所以时间复杂度为O（1）
hadoop就是布隆过滤器，每个文件是一个bloom filter，给一个key遍历所有文件的布隆过滤器，会给出可能匹配的文件，在这几个文件查找即可
面试时候如果给出失误率的大数据问题，那么必然是Bloom filter算法

5 一致性hash原理

场景描述

场景.png
策略

image.png
问题：

image.png
引入一致性hash算法：https://www.cnblogs.com/yft-javaNotes/p/10779042.html#autoid-4-5-0
优点：服务器数量变化时候，只有部分缓存发生改变，前端的缓存仍然可以分担部分压力
缺点：可能会出现hash环的偏斜——虚拟节点发解决。

引入虚拟节点.png

6 并查集

image.png

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：

合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。

如何保证时间复杂度都是O（1）？

方式一：union时候，小集合的头点挂在大集合头点下面，isSameSet，比较各自的头点即可
优化：findHead(ele)

// 给定一个ele，往上一直找，把代表元素返回，其实就是头点
        private Element<V> findHead(Element<V> element) {
            //path记录沿途节点
            Stack<Element<V>> path = new Stack<>();
            while (element != fatherMap.get(element)) {
                path.push(element);
                element = fatherMap.get(element);
            }
            //至此，记录完成，element就是头点
            
            while (!path.isEmpty()) {
                //沿途的节点父节点更新为此头点
                fatherMap.put(path.pop(), element);
            }
            return element;
        }

// 样本进来会包一层，叫做元素
    public static class Element<V> {
        public V value;

        public Element(V value) {
            this.value = value;
        }

    }

    public static class UnionFindSet<V> {
        public HashMap<V, Element<V>> elementMap;
        // key  某个元素  value 该元素的父
        public HashMap<Element<V>, Element<V>> fatherMap;
        // key 某个集合的代表元素   value 该集合的大小,其实只存头点，作为挂载的标准
        public HashMap<Element<V>, Integer> sizeMap;
        
        //初始化
        public UnionFindSet(List<V> list) {
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            for (V value : list) {
                Element<V> element = new Element<V>(value);
                elementMap.put(value, element);
                fatherMap.put(element, element);
                sizeMap.put(element, 1);
            }
        }

        // 给定一个ele，往上一直找，把代表元素返回，其实就是头点
        private Element<V> findHead(Element<V> element) {
            Stack<Element<V>> path = new Stack<>();
            while (element != fatherMap.get(element)) {
                path.push(element);
                element = fatherMap.get(element);
            }
            while (!path.isEmpty()) {
                fatherMap.put(path.pop(), element);
            }
            return element;
        }

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

        public void union(V a, V b) {
            if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
                Element<V> aF = findHead(elementMap.get(a));
                Element<V> bF = findHead(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(aF) + sizeMap.get(bF));
                    sizeMap.remove(small);
                }
            }
        }

    }

map结构，key要包装，因为对于int是按值传递的，而对于两个ele中v相同，但其实是两个对象，得到的hashcode也不同，可以区分
1）小集合挂大集合
2）网上找的过程中，沿途的链扁平化，便于后面的查找头点
3）每条链只痛苦一次，假设样本数量为N，如果两个操作所有的次数逼近O（N），则单次操作时间复杂度为O（1）——调用的越频繁，时间复杂度越好

岛问题.png
利用上面的并查集结构直接做

public static int countsIslands(int[][] m) {
        List<String> list = new ArrayList<>();
        for (int row = 0; row < m.length; row++)
            for (int col = 0; col < m[0].length; col++) {
                //记录所有值为1的位置
                if (m[row][col] == 1) {
                    //5,3---> 5_3
                    String position = String.valueOf(row) + "_" + String.valueOf(col);
                    list.add(position);
                }
            }

        UnionFindSet<String> unionFindSet = new UnionFindSet<>(list);

        for (int row = 0; row < m.length; row++)
            for (int col = 0; col < m[0].length; col++) {
                //记录所有值为1的位置
                if (m[row][col] == 1) {
                    //5,3---> 5_3
                    String position = String.valueOf(row) + "_" + String.valueOf(col);
                    if (row - 1 > 0 && m[row - 1][col] == 1) {
                        String up = String.valueOf(row - 1) + "_" + String.valueOf(col);
                        unionFindSet.union(up, position);
                    }
                    if (row + 1 < m.length && m[row + 1][col] == 1) {
                        String down = String.valueOf(row + 1) + "_" + String.valueOf(col);
                        unionFindSet.union(down, position);
                    }
                    if (col - 1 > 0 && m[row][col - 1] == 1) {
                        String left = String.valueOf(row) + "_" + String.valueOf(col - 1);
                        unionFindSet.union(left, position);
                    }
                    if (col + 1 < m[0].length && m[row][col + 1] == 1) {
                        String right = String.valueOf(row) + "_" + String.valueOf(col + 1);
                        unionFindSet.union(right, position);
                    }
                }
            }
        return unionFindSet.getSetNum();
    }

设计一个并行算法优化，如果m非常大，设置一个大的并查集结构，和小块的
//并查集结构，union边界

四 KMP算法

https://www.zhihu.com/question/21923021

Partial Match Table：PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度，第i位的表示0~i-1位置的最长前后缀匹配串长度，0和1位置规定位-1和0；

image.png
匹配过程（加速暴力匹配）：，此时j位置最大长度为4，所以指针回到第5位继续比较，前4位就不必比较了

image.png
时间复杂度：O（）
得到next数组

//得到ms的next数组
    public static int[] getNextArray(char[] ms) {
        int[] arr = new int[ms.length];
        arr[0] = -1;
        arr[1] = 0;
        int count = 0;
        //
//        public String toString() {
//            return getClass().getName() + "@" + Integer.toHexString(hashCode());
//        }
//        错误写法，数组没有重写toString，返回的不是转换后的String
//        String mss = ms.toString();
        String mss = String.valueOf(ms);
        for (int i = 2; i < ms.length; i++) {
            count = 0;
            for (int j = 0; j < i - 1; j++) {
                //必须使用String.valueof
                //[0,j]   [i-1-j, i-1]
                String sub1 = mss.substring(0, j+1);
                String sub2 = mss.substring(i-1-j, i);
                if(sub1.equals(sub2))
                    count = j+1;
            }
            arr[i] = count;
        }
        return arr;
    }

真正的加速找到next

//得到ms的next数组
    public int[] getNextArray(char[] ms) {
        if (ms.length == 1) {
            return new int[] { -1 };
        }
        int[] next = new int[ms.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2; // next数组的位置
        int cn = next[i-1]; //next[i-1]
        while (i < next.length) {
            //next[i]表示前k和后k相同 那么
            if (ms[i - 1] == ms[cn]) {
                next[i] = ++cn;
                i++;//下一个
            } else if (cn > 0) {
                // 当前跳到cn位置的字符，和i-1位置的字符配不上，开始缩小cn，
                // 直到匹配
                //又因为目前两个长为k前后完全相同，那么选next【cn】就保证了
                //新前后缀也相同
                cn = next[cn];
            } else {
                //cn=0时候，回到了原点，显然next为0
                next[i++] = 0;
            }
        }
        return next;
    }

根据next数组加速查找

 //得到匹配的最小索引
    public int strStr(String hsystack, String needle) {
        if(needle.equals(""))
            return 0;
        if (hsystack == null || hsystack.length() < needle.length()) {
            return -1;
        }
        char[] str1 = hsystack.toCharArray();
        char[] str2 = needle.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int[] next = getNextArray(str2); // O (M)
        // O(N)
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) {
                i1++;
                i2++;
            } else if (next[i2] == -1) { // str2中比对的位置已经无法往前跳了
                i1++;
            } else {
                i2 = next[i2];
            }
        }
        // i1 越界  或者  i2越界了
        return i2 == str2.length ? i1 - i2 : -1;
}

/**
 * @author : liulinzhi
 * @date: 2020/08/13/15:22
 * @description:
 */
public class KMP {
    //得到匹配的最小索引
    public int strStr(String hsystack, String needle) {
        if(needle.equals(""))
            return 0;
        if (hsystack == null || hsystack.length() < needle.length()) {
            return -1;
        }
        //得到next数组
        int[] next = getNextArray(needle.toCharArray());
        //设置两个指针
        int i = 0;
        int j = 0;
        while(i < hsystack.length() && j < needle.length()){
            if(hsystack.charAt(i) == needle.charAt((j))){
                i++;
                j++;
            }else if(next[j] == -1)
            //                    j = 0;因为=-1时候j已经在0位置了
                i++;
            else
                j = next[j];
        }
        return j == needle.length() ? (i - needle.length()) : -1;
}


    //快速得到ms的next数组
    public int[] getNextArray(char[] ms) {
        int[] next = new int[ms.length];
        if(ms.length < 2){
            next[0] = -1;
            return next;
        }
        next[0] = -1;
        next[1] = 0;

        int i = 2;
        int tmp = 0;//和i-1位置比较的字符，初始为next【1】=0
        while (i < ms.length){
            if(ms[i - 1] == ms[tmp]){
                next[i] = tmp + 1;
                tmp++;
                i++;
            }else if(tmp > 0){
                //tmp退化，继续比较ms[i - 1]和ms[tmp]
                tmp = next[tmp];
            }else{//已经没有相同前后缀了
                next[i++] = 0;
            }
        }
        return next;
    }


    public static void main(String[] args) {
        String str = "abcabcababaccc";
        String match = "ababa";

        KMP k = new KMP();
        System.out.println(k.strStr(str, match));
    }

}

反证法可以证明next[i+1]<= next[i] + 1
时间复杂度O（N），getNextArray时间复杂度为O（2M），综合getNextArrayO（M）

五 Manacher算法

求一个字符串中的最长回文子串，这是一道经典的面试题目，解法有很多，详细可见：最长回文子串问题。其实个人感觉 Manacher 算法代码实现还是有一定难度的，真正在做题目的时候采用的可能性不是很大，但是由于 Manacher 算法求解回文子串方面的时间复杂度为 O(N)，所以了解其思想还是很有必要的，coding 能力比较强的话，采用 Manacher 算法解决最长回文子串问题更是最合适不过了。

回文串的概念：一个字符串正着读和倒着读都是一样
的，比如：abba、noon 等；

最长回文子串：一个字符串的最长回文子串即为这个字
符串的子串中，是回文串的最长的那个。

https://blog.csdn.net/pcwl1206/article/details/94876776

5.1 暴力解法

思路：对字符串遍历每一个字符，以对每一个字符，以它为中心，往两边扩，找出以该字符串为中心的回文串大小。这里要分为两种情况，一种是回文串长度是奇数的情况，另一种是回文串长度是偶数的情况，奇数直接扩能找出回文，偶数则不可以。为了解决这样的奇偶差异，可以在每个数字的前后加上一个虚轴 “#”。
加#后，按0索引开始，回文串长度为加上#的回文串长度/2，其实这个字符可以任意的，不一定非要串中不存在的字符，因为虚轴总和虚轴比，实轴和实轴比。时间复杂度O（N^2）

Manacher