并查集&LRU Cache

末蓝、 2024-02-05 11:38 54阅读 0赞

**目录**

前言

一 . 并查集

1.1 并查集原理

1.2 并查集的实现

二 . LRU Cache

2.1 什么是LRU Cache

2.2 LRU Cache实现

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

2.4 自己实现链表

总结

--------------------

## 前言 ##

> 大家好,今天给大家介绍两种数据结构并查集&LRU Cache

--------------------

## 一 . 并查集 ##

### 1.1 并查集原理 ###

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

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

![d15ce05363b84132aaaad5239b350390.png][]

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

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

![38f2f35dad634436843ed903fc605ee1.png][]

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

![c64b6f040ccc4fca87b21b77bc318b67.png][]

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

仔细观察数组，可以得出以下结论：

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

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

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

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

![4e55a150fef749a7b8b05b9983cfcd94.png][]

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

通过以上例子可知，并查集一般可以解决一下问题：

**1. 查找元素属于哪个集合**

沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)

**2. 查看两个元素是否属于同一个集合**

沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在

**3. 将两个集合归并成一个集合**

将两个集合中的元素合并 将一个集合名称改成另一个集合的名称

**4. 集合的个数**

遍历数组，数组中元素为负数的个数即为集合的个数。

--------------------

### 1.2 并查集的实现 ###

没什么难度,大家自己看看就好

/**
     * 并查集
     */
    public class UnionFindSet {
        private int[] elem;
        private int usedSize;
    
        public UnionFindSet(int capacity) {
            elem = new int[capacity];
            Arrays.fill(elem,-1);
        }
    
        /**
         * 查找一个数据的根节点
         * @param x
         * @return 下标
         */
        public int findRoot(int x){
            if(x < 0){
                throw new IndexOutOfBoundsException("数组越界,下标不合法!");
            }
            while(elem[x] >= 0){
                x = elem[x];
            }
            return x;
        }
    
        /**
         * 查询两个数字是否在同一个集合
         * @param x1 数字一
         * @param x2 数字二
         * @return 在同一个集合返回true反之返回false
         */
        public boolean isSameUnionFindSet(int x1,int x2){
            return findRoot(x1) == findRoot(x2);
        }
    
        /**
         * 合并操作[合并的是根节点]
         * @param x1
         * @param x2
         */
        public void union(int x1,int x2){
            int rootIndex1 = findRoot(x1);
            int rootIndex2 = findRoot(x2);
            if(rootIndex1 == rootIndex2){
                return;
            }
            elem[rootIndex1] = elem[rootIndex1]+elem[rootIndex2];
            elem[rootIndex2] = rootIndex1;
        }
    
        /**
         * 集合的个数
         * @return
         */
        public int getCount(){
            int count = 0;
            for (int i : elem) {
                if(i < 0){
                    count++;
                }
            }
            return count;
        }
    
        public void print(){
            for (int i : elem) {
                System.out.print(i+" ");
            }
        }
    
    
        public static void main(String[] args) {
            UnionFindSet unionFindSet = new UnionFindSet(10);
            System.out.println("合并: 0和6");
            unionFindSet.union(0,6);
            System.out.println("合并: 0和7");
            unionFindSet.union(0,7);
            System.out.println("合并: 0和8");
            unionFindSet.union(0,8);
            System.out.println("合并: 1和4");
            unionFindSet.union(1,4);
            System.out.println("合并: 1和9");
            unionFindSet.union(1,9);
            System.out.println("合并: 2和3");
            unionFindSet.union(2,3);
            System.out.println("合并: 2和5");
            unionFindSet.union(2,5);
    
            unionFindSet.print();
    
            System.out.println("合并: 8和1");
            unionFindSet.union(8,1);
    
            unionFindSet.print();
    
            System.out.println(unionFindSet.isSameUnionFindSet(6, 9));
        }
    }

练手题

[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

class Solution {
        private int[] elem;
        private int usedSize;
    
        public int findCircleNum(int[][] isConnected) {
            elem = new int[isConnected.length];
            Arrays.fill(elem,-1);
            for(int i = 0; i<isConnected.length; i++){
                for(int j = 0; j<isConnected[0].length; j++){
                    if(isConnected[i][j] == 1)
                        union(i,j);
                }
            }
            return getCount();
        }
    
        /**
         * 查找一个数据的根节点
         * @param x
         * @return 下标
         */
        public int findRoot(int x){
            if(x < 0){
                throw new IndexOutOfBoundsException("数组越界,下标不合法!");
            }
            while(elem[x] >= 0){
                x = elem[x];
            }
            return x;
        }
    
        /**
         * 合并操作[合并的是根节点]
         * @param x1
         * @param x2
         */
        public void union(int x1,int x2){
            int rootIndex1 = findRoot(x1);
            int rootIndex2 = findRoot(x2);
            if(rootIndex1 == rootIndex2){
                return;
            }
            elem[rootIndex1] = elem[rootIndex1]+elem[rootIndex2];
            elem[rootIndex2] = rootIndex1;
        }
    
        /**
         * 集合的个数
         * @return
         */
        public int getCount(){
            int count = 0;
            for (int i : elem) {
                if(i < 0){
                    count++;
                }
            }
            return count;
        }
    }

class Solution {
        public boolean equationsPossible(String[] equations) {
            UnionFindSet unionFind = new UnionFindSet(26);
            for(String s : equations){
                if(s.charAt(1) == '='){
                    unionFind.union(s.charAt(0)-'a',s.charAt(3)-'a');
                }
            }
    
            for(String s : equations){
                if(s.charAt(1) == '!'){
                    boolean flag = unionFind.isSameUnionFindSet(s.charAt(0)-'a',s.charAt(3)-'a');
                    if(flag){
                        return false;
                    }
                }
            }
    
            return true;
        }
    
         /**
         * 并查集
         */
        public class UnionFindSet {
            private int[] elem;
            private int usedSize;
        
            public UnionFindSet(int capacity) {
                elem = new int[capacity];
                Arrays.fill(elem,-1);
            }
        
            /**
             * 查找一个数据的根节点
             * @param x
             * @return 下标
             */
            public int findRoot(int x){
                if(x < 0){
                    throw new IndexOutOfBoundsException("数组越界,下标不合法!");
                }
                while(elem[x] >= 0){
                    x = elem[x];
                }
                return x;
            }
        
            /**
             * 查询两个数字是否在同一个集合
             * @param x1 数字一
             * @param x2 数字二
             * @return 在同一个集合返回true反之返回false
             */
            public boolean isSameUnionFindSet(int x1,int x2){
                return findRoot(x1) == findRoot(x2);
            }
        
            /**
             * 合并操作[合并的是根节点]
             * @param x1
             * @param x2
             */
            public void union(int x1,int x2){
                int rootIndex1 = findRoot(x1);
                int rootIndex2 = findRoot(x2);
                if(rootIndex1 == rootIndex2){
                    return;
                }
                elem[rootIndex1] = elem[rootIndex1]+elem[rootIndex2];
                elem[rootIndex2] = rootIndex1;
            }
        
        }
    }

## 二 . LRU Cache ##

###  ###

### 2.1 什么是LRU Cache ###

> LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。 什么是Cache？狭义 的Cache指的是位于CPU和主存间的快速RAM， 通常它不像系统主存那样使用DRAM技术，而使用昂贵但较 快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度 差异的结构。除了CPU与主存之间有Cache， 内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种 意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。
> 
> **Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有 的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。**其实， LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。

### 2.2 LRU Cache实现 ###

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

![92870bc056864cdaba8c72e9f86fd7b0.png][]

### 2.3 JDK中类似LRUCahe的数据结构LinkedHashMap ###

参数说明：

1. initialCapacity 初始容量大小，使用无参构造方法时，此值默认是16

2. loadFactor 加载因子，使用无参构造方法时，此值默认是 0.75f

3. accessOrder false： 基于插入顺序 true： 基于访问顺序

示例1：当accessOrder的值为false的时候

> public static void main(String\[\] args) \{
> 
> Map 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);
> 
> \}

输出结果： \{1=a, 2=b, 4=e, 3=c\}

以上结果按照插入顺序进行打印

示例2：当accessOrder的值为true的时候

> public static void main(String\[\] args) \{
> 
> Map 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("1");
> 
> map.get("2");
> 
> System.out.println(map);
> 
> \}

输出结果： \{4=e, 3=c, 1=a, 2=b\}

每次使用get方法，访问数据后，会把数据放到当前双向链表的最后。

当accessOrder为true时，get方法和put方法都会调用recordAccess方法使得**最近使用的Entry移到双向链表的末尾**；当accessOrder为默认值false时，从源码中可以看出recordAccess方法什么也不会做。

![4940879c3aeb403ea79194059091630a.png][]

![1819cae16b9d457488e4ddde52b3a4be.png][]

![f947c49661da4fefa5a7d1ce11a16fab.png][]

### 2.4 自己实现链表 ###

/*
    * 最近最久未使用cache替换算法
    * 哈希+双向链表
    * */
    public class LruCache extends LinkedHashMap {
    
        private final ListNode head; // 傀儡头节点,避免分情况讨论
        private final ListNode tail; // 傀儡尾节点,避免分情况讨论
        private final int capacity;
        private int usedSize;
    
        private final Map<Integer,ListNode> hash;
    
        public LruCache(int capacity) {
            this.capacity = capacity;
            hash = new HashMap<>(capacity);
            head = new ListNode();
            tail = new ListNode();
            head.next = tail;
            tail.pre = head;
        }
    
    
        /**
         * 获取当前key对应的value
         * @param key
         * @return
         */
        public int get(int key){
            ListNode node = hash.get(key);
            // key 不存在,返回-1
            if(node == null) return -1;
            // key存在,将该节移动至尾部
            moveTail(node);
            return node.val;
        }
    
        private void moveTail(ListNode node){
            removeNode(node);
            addToTail(node);
        }
    
        private void addToTail(ListNode node) {
            tail.pre.next = node;
            node.pre = tail.pre;
            node.next = tail;
            tail.pre = node;
        }
    
    
        private void removeNode(ListNode node){
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
    
    
        /**
         * 删除第一个节点的数据
         */
        public ListNode removeHead(){
            ListNode next = head.next;
            head.next = head.next.next;
            head.next.pre = head;
            usedSize--;
            return next;
        }
    
        /**
         * 添加节点
         * @param key
         * @param value
         */
        public void put(int key,int value){
            /*
            * 1.查看是否存在该key对应的节点
            * 2.如果不存在,在map中添加该key,并在尾部添加节点
            * 3.如果usedSize > capacity 移除头部元素
            * 4.如果存在,将该节点拖到尾部即可
            * */
            ListNode node = hash.get(key);
            // 1.查看是否存在该key对应的节点
            if(node == null){
                node = new ListNode(key,value);
                hash.put(key,node);
                usedSize++;
                // 3.如果usedSize > capacity 移除头部元素
                if(usedSize > capacity){
                    ListNode listNode = removeHead();
                    hash.remove(listNode.key);
                    usedSize--;
                }
                //  4.如果存在,将该节点拖到尾部即可
                addToTail(node);
            }else{
                // 2.如果不存在,在map中添加该key,并在尾部添加节点
                node.val = value;
                // 移动至尾部
                moveTail(node);
            }
        }
    
        /**
         * 节点内部类
         */
        static class ListNode {
            int val;
            int key;
            ListNode pre;
            ListNode next;
    
            public ListNode(int key,int val) {
                this.key = key;
                this.val = val;
            }
    
            public ListNode() {
    
            }
        }
    
        public static void main(String[] args) {
            LinkedHashMap<String,Integer> l = new LinkedHashMap(16,0.75f,false);
        }
    }

--------------------

## 总结 ##

代码都很简单,大家多多理解,下一篇博客见!

[d15ce05363b84132aaaad5239b350390.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/b9383f4723ac4230b18b4d8ec3df1df9.png
[38f2f35dad634436843ed903fc605ee1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/80e8a56a3ce04591a63fb5289f7ebfc5.png
[c64b6f040ccc4fca87b21b77bc318b67.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/3e1a530dd1f041e1bf6d0848ba2a3af3.png
[4e55a150fef749a7b8b05b9983cfcd94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/e2d516a33edd471c898334933e0073b2.png
[LeetCode_ -]: https://leetcode-cn.com/problems/number-of-provinces/
[LeetCode_ - 1]: https://leetcode-cn.com/problems/satisfiability-of-equality-equations/comments/
[92870bc056864cdaba8c72e9f86fd7b0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/3c4d374aed0f454d9abb9aaebdc21866.png
[4940879c3aeb403ea79194059091630a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/1f765497f1484c6c987a69eafaf4243a.png
[1819cae16b9d457488e4ddde52b3a4be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/85845683d59a49fab5cf5d097c5131f6.png
[f947c49661da4fefa5a7d1ce11a16fab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/05/0b7f2ca09b3d421ca3acd4ad540fbaba.png