并查集与LRUCache(Java数据结构)

前言：

学习过二叉树之后就应该知道了如何构建一颗二叉树，双亲结点和孩子节点的关系，甚至可以放在顺序表中去构建一棵二叉树！

接下来我们要以另一种方式去组织一棵树：

如何表示一棵树之间的关系？(这棵树只能存放整型数据)

有这样的一个思路，我们可以继续借助顺序表，用顺序表的下标表示每个整型，每个下表里面放的内容有两种情况：

1、如果该节点就是根节点的话，就需要存放 -(所有孩子(包括孙子等)的个数)。(不要忘记加负号)

2、如果该节点不是根节点的时候，就需要存放双亲结点的下标！

接下就以这种方式去组织一棵二叉树！

并查集：

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。

比如：某公司今年校招全国总共招生10 人，西安招 4 人，成都招 3 人，武汉招 3 人， 10 个人来自不同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个数。( 负号下文解释 )

毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：

西安学生小分队 s1={0,6,7,8} ，成都学生小分队 s2={1,4,9} ，武汉学生小分队 s3={2,3,5} 就相互认识了， 10 个人形成了三个小团体。假设右三个群主0,1,2 担任队长，负责大家的出行。

一趟火车之旅后，每个小分队成员就互相熟悉，称为了一个朋友圈。

从上图可以看出：编号 6,7,8 同学属于 0 号小分队，该小分队中有 4 人 ( 包含队长 0) ；编号为 4 和 9 的同学属于 1 号

小分队，该小分队有 3 人 ( 包含队长 1) ，编号为 3 和 5 的同学属于 2 号小分队，该小分队有 3 个人 ( 包含队长 1) 。

仔细观察数组中内融化，可以得出以下结论：

1. 数组的下标对应集合中元素的编号

2. 数组中如果为负数，负号代表根，数字代表该集合中元素个数

3. 数组中如果为非负数，代表该元素双亲在数组中的下标

在公司工作一段时间后，西安小分队中 8 号同学与成都小分队 1 号同学奇迹般的走到了一起，两个小圈子的学

生相互介绍，最后成为了一个小圈子：

现在 0 集合有 7 个人， 2 集合有 3 个人，总共两个朋友圈。

以上的例子很清楚的说明并查集的组织的和过程！

当然此时组织好并查集之后还是可以进行增删查找的工作！

接下来先来手搓一个并查集：

手动实现一个并查集：

public class MyUnionfindset {
    private int[] array;
    public MyUnionfindset(int num) {
        this.array = new int[num];
        Arrays.fill(array,-1);//整体初始化位-1
    }
    /**
     * 查找x的根*
     */
    public int findRoot(int x) {
        if(x >= array.length) {
            throw new ArrayIndexOutOfBoundsException("数据不合法");
        }
        while(array[x] >=0) {
            x = array[x];
        }
        return x;
    }
    /**
     * 合并x1和x2，前提是x1和x2都必须是根节点
     */
    public void union(int x1,int x2) {
        //找x1的根
        int root1 = findRoot(x1);
        //找x2的根
        int root2 = findRoot(x2);
        //说明root1和root2是同一个节点
        if(root1 == root2) {
            return ;
        }
        //合并,root2合并在root1中
        array[root1] = array[root1] + array[root2];
        array[root2] = root1;
    }
    /**
     * 判断两个数字是否在同一个集合当中
     */
    public boolean isSameSet(int x1,int x2) {
        //找x1的根节点
        int root1 = findRoot(x1);
        //找x2的根节点
        int root2 = findRoot(x2);
        if (root1 == root2) {
            return true;
        } else return false;
    }
        /**
         * 求数组当中集合的个数
         */
        public int getCount(int[] array) {
            int count = 0;
            for (int i = 0;i<array.length;i++) {
                if(array[i] < 0) {
                    count++;
                }
            }
            return count;
        }
    public void printArr() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
}

以上述的例子未测试对象：

    public static void main(String[] args) {
        MyUnionfindset myUnionfindset = new MyUnionfindset(10);
        myUnionfindset.union(0,6);
        myUnionfindset.union(0,7);
        myUnionfindset.union(0,8);
        myUnionfindset.union(1,4);
        myUnionfindset.union(1,9);
        myUnionfindset.union(2,3);
        myUnionfindset.union(2,5);
        myUnionfindset.union(0,1);
        myUnionfindset.printArr();
    }

测试结果如下：

并查集的应用：

547. 省份数量 - 力扣（LeetCode）

    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        MyUnionfindset myUnionfindset = new MyUnionfindset(n);
        for(int i = 0;i<n;i++) {
            for(int j = 0;j < isConnected[i].length;j++) {
                //两个城市相连就合并
                if(isConnected[i][j] == 1) {
                    myUnionfindset.union(i,j);
                }
            }
        }
        return myUnionfindset.getCount();
    }

990. 等式方程的可满足性 - 力扣（LeetCode）

    public boolean equationsPossible(String[] equations) {
        MyUnionfindset myUnionfindset = new MyUnionfindset(26);
        for(String x: equations) {
          if(x.charAt(1) == '=') {
            myUnionfindset.union(x.charAt(0)-'a',x.charAt(3)-'a');
          }
        }
        for(String x: equations) {
          if(x.charAt(1) == '!') {
            //找根节点
            int n1 = myUnionfindset.findRoot(x.charAt(0)-'a');
            int n2 = myUnionfindset.findRoot(x.charAt(3)-'a');
            if(n1 == n2) {
                return false;
            }
          }
        }
        return true;
    }

LRUCache:

什么是LRUCache？

LRU是 Least Recently Used 的缩写，意思是 最近最少使用 ，它是一种 Cache 替换算法。什么是 Cache ？狭义的Cache 指的是位于 CPU 和主存间的快速 RAM ，通常它不像系统主存那样使用 DRAM 技术，而使用昂贵但较快速的SRAM 技术。广义上的 Cache 指的是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构。除了CPU 与主存之间有 Cache ，内存与硬盘之间也有 Cache ，乃至在硬盘与网络之间也有某种意义上的Cache ── 称为 Internet 临时文件夹或网络内容缓存等。

Cache 的容量有限，因此当 Cache 的容量用完后，而又有新的内容需要添加进来时，就需要挑选并舍弃原有 的部分内容，从而腾出空间来放新内容。 LRU Cache 的替换原则就是将最近最少使用的内容替换掉 。

LRUCache的实现：

实现LRU Cache的方法和思路很多，但是要保持高效实现O(1)的put和get，那么使用双向链表和哈希表的搭配是最高效和经典的。使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，使用哈希表是因为哈希表的增删查改也是O(1)。

.JDK 中类似 LRUCahe 的数据结构 LinkedHashMap

    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<>(16,0.75f,false);
        map.put("1", "a");
        map.put("2", "b");
        map.put("4", "e");
        map.put("3", "c");
        System.out.println(map);
    }

参数说明：

LInkedHashMap类的构造方法有很多种，但是其中最全面的就是有三个参数的构造方法：

1、initialCapacity表示的是初始容量，可以自己传入初始容量，初始容量默认是16。

2、loadFactor表示的是负载因子，在学习HashMap的时候已将介绍过了负载因子，为了降低冲突，系统默认负载因子位0.75。

3、accessOrder表示的是访问顺序：

当传入true时，如果进行get按访问顺序。

当传入false时，如果进行get按插入顺序。

（如果不太能理解，下面会进行示范）

如下所示：

如果传入的参数是false时，此时我get一个数据：

    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<>(16,0.75f,true);
        map.put("1", "a");
        map.put("2", "b");
        map.put("4", "e");
        map.put("3", "c");
        map.get("2");
        System.out.println(map);
    }

结果如下：

如果传入的参数是true时，此时我继续get一个数据：

    public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<>(16,0.75f,true);
        map.put("1", "a");
        map.put("2", "b");
        map.put("4", "e");
        map.put("3", "c");
        map.get("2");
        System.out.println(map);
    }

结果如下：

发先如果是true时，此时打印的顺序将发生改变！！

将刚刚get的数据放在了链表的最后！！

手动实现LRUCache：

还是一样我们先手动实现一个，更加清楚的了解内部的原理：

public class LRUCache {
    //链表节点
    public class DLinkedNode {
        int key;
        int value;
        DLinkedNode prve;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    Map<Integer,DLinkedNode> map = new HashMap<>();
    private int size;
    private int capacity;
    //带哨兵位的双向链表
    private DLinkedNode head,tail;
    public LRUCache(int capacity) {
        size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prve = head;
    }
    public int get(int key) {
        DLinkedNode node = map.get(key);
        if(node == null) {
            return -1;
        }
        moveTail(node);
        return node.value;
    }
    private void moveTail(DLinkedNode node) {
    removeNode(node);
    addToTail(node);
    }
    private void removeNode(DLinkedNode node) {
        node.prve.next = node.next;
        node.next.prve = node.prve;
    }
    private void addToTail(DLinkedNode node) {
        tail.prve.next = node;
        node.prve = tail.prve;
        node.next = tail;
        tail.prve = node;
    }
    public void put(int key,int value) {
        //查看K是否存在
        DLinkedNode node = map.get(key);
        if(node == null) {
            //如果不存在那么就新创建一个，并且放入哈希表中
            DLinkedNode newNode = new DLinkedNode(key,value);
            map.put(key,newNode);
            size++;
            addToTail(newNode);
            if(size > capacity) {
                //如果插入的数量大于容量，就需要删除头节点
                DLinkedNode tail = removeHead();
                //删除哈希表对应的相
                map.remove(tail.key);
                size--;
            }
        }else {
            //如果key存在先通过哈希表找到对应的位置修改value
            node.value = value;
            //移动到链表末尾
            moveTail(node);
        }
    }
    //删除头节点
    private DLinkedNode removeHead() {
        DLinkedNode ret = head.next;
        head.next = ret.next;
        ret.next.prve = head;
        return ret;
    }
}