系列文章目录
数据结构之ArrayList_arraylist o(1) o(n)-CSDN博客
目录
4. 基于 LinkedHashMap 实现 LRUCache
前言
本文介绍了两种重要的数据结构：并查集和LRUCache。并查集用于高效处理集合合并与查询操作，文章详细讲解了其原理、模拟实现方法，并给出亲戚关系判断、省份数量计算等应用实例。LRUCache是一种缓存淘汰算法，文章剖析了其哈希表+双向链表的实现原理，提供了完整的模拟实现代码，并介绍了基于LinkedHashMap的简化实现方案。两种数据结构在实际开发中都有广泛应用，本文通过代码示例和解题思路展示了它们的具体使用方法。
一、并查集
1. 并查集的原理
合并集合：选取两个集合，两个集合选取相同的根节点，这两个集合就被合并了；
查询两个元素是否属于同一个集合：
查询两个元素之间的关系时，分别查询两个元素的根节点；
如果根节点相同，就表示两个元素属于同一个集合；
如果根节点不同，表示两个元素不属于同一个集合；
并查集适用于频繁合并集合，以及频繁查询某两个元素是否属于同一集合的应用场景；
2. 模拟实现并查集
elem：表示全集
数组下标表示当前节点，数组中存放的值，表示上一级节点；
例如：elem[0] = 10，表示 0 的父节点是 10；
如果 i 是根节点，则 elem[i] 须为负数，用负数表示根，负号后面的值为当前集合中元素的个数；
例如 ：0 是根节点，elem[0] = -10，表示 0 为根节点，且这个集合中有 10 个元素；
unionFindSet(int n)：并查集的构造方法
n 表示全集中元素的个数；
elem 中所有值都初始化为 -1，表示未合并前都是根节点，且集合中只有当前值这一个元素；
findRoot(int x): int 找 x 所属集合的根节点
如果 x 不存在，抛异常；
循环查找 x 上级节点 elem[x]（x = elem[x]），直到 elem[x] 小于 0，即表示 x 为根节点；
union(int x1, int x2): void 合并 x1 和 x2 所在的集合
判断 x1 和 x2 是否在同一个集合，即 x1 集合的根节点和 x2 集合的根节点是否为同一个节点；
如果是同一个节点，则表示在同一个集合，直接返回；
如果不是同一个节点（root1 表示 x1 所在集合的根节点，root2 表示 x2 所在集合的根节点）：
将 root1 集合 和 root2 集合节点的数量都累加在 root1 中，即 elem[root1] = elem[root1] + elem[root2]；
将 root2 的根节点改为 root1，即 elem[root2] = root1；
isSameUnionFindSet(int x1, int x2): boolean 判断两个节点是否属于同一个集合
找 x1 和 x2 的根节点，并判断是否为同一个节点；
如果是同一个节点，返回 true；
如果不是同一个节点，返回 false；
count(): int 计算一共有几个集合
遍历 elem，返回负数的个数，即为集合的数量；
代码实现：
public class UnionFindSet {
public int[] elem;
public UnionFindSet(int n){
this.elem = new int[n];
Arrays.fill(this.elem, -1);
}
public int findRoot(int x) {
if(x < 0){
throw new PosOutOfBoundsException("输入的下标不合法，是负数！");
}
while(this.elem[x] >= 0){
x = this.elem[x];
}
return x;
}
public boolean isSameUnionFindSet(int x1, int x2){
int index1 = findRoot(x1);
int index2 = findRoot(x2);
if(index1 == index2){
return true;
}else{
return false;
}
}
public void union(int x1, int x2){
int index1 = findRoot(x1);
int index2 = findRoot(x2);
if(index1 == index2){
return;
}
this.elem[index1] = this.elem[index1] + this.elem[index2];
this.elem[index2] = index1;
}
public int count(){
int count = 0;
for(int i = 0; i < this.elem.length; i++){
if(this.elem[i] < 0) count++;
}
return count;
}
}3. 并查集的应用
1.判断亲戚关系
假设亲戚的所有亲戚也是亲戚，有 10 个人，分别用 0 ~ 9 表示，。已知 0 和 6，7，8 是亲戚关系，1 和 4，9是亲戚关系，2 和 3，5 是亲戚关系，判断 6 和 9 是否是亲戚关系，如果 8 和 1 缔结了亲戚关系，6 和 9 是否也有了亲戚关系？
使用并查集判断如下：
public static void main(String[] args) {
UnionFindSet unionFindSet = new UnionFindSet(10);
unionFindSet.union(0, 6);
unionFindSet.union(0, 7);
unionFindSet.union(0, 8);
unionFindSet.union(1, 4);
unionFindSet.union(1, 9);
unionFindSet.union(2, 3);
unionFindSet.union(2, 5);
System.out.println(unionFindSet.isSameUnionFindSet(6, 9));
unionFindSet.union(8, 1);
System.out.println(unionFindSet.isSameUnionFindSet(6, 9));
}运行结果：
2. 判断省份的数量
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
思路：
模拟实现并查集，利用并查集的思想，将相邻的城市放到同一个集合，最终返回集合的数量即可；
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
UnionFindSet ufs = new UnionFindSet(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(isConnected[i][j] == 1){
ufs.union(i, j);
}
}
}
return ufs.count();
}
}
class UnionFindSet {
public int[] elem;
public UnionFindSet(int n){
this.elem = new int[n];
Arrays.fill(this.elem, -1);
}
public int findRoot(int x) {
if(x < 0){
return -1;
}
while(this.elem[x] >= 0){
x = this.elem[x];
}
return x;
}
public boolean isSameUnionFindSet(int x1, int x2){
int index1 = findRoot(x1);
int index2 = findRoot(x2);
if(index1 == index2){
return true;
}else{
return false;
}
}
public void union(int x1, int x2){
int index1 = findRoot(x1);
int index2 = findRoot(x2);
if(index1 == index2){
return;
}
this.elem[index1] = this.elem[index1] + this.elem[index2];
this.elem[index2] = index1;
}
public int count(){
int count = 0;
for(int i = 0; i < this.elem.length; i++){
if(this.elem[i] < 0) count++;
}
return count;
}
}3. 等式方程的可满足性
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
示例 1：
输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
示例 2：
输入：["b==a","a==b"]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
思路：
模拟实现并查集，遍历 equations 数组，将具有等式关系的都放到同一个集合；
再遍历 equations 数组，依次检查具有不等关系的元素，看是否在同一个集合；
如果在同一个集合，则不可能成立，因为具有相等关系才会在一个集合，此时返回 false，
如果所有具有不等关系的元素都不在同一个集合 ，返回 true；
class Solution {
public int[] elem = new int[26];
public int findRoot(int x){
while(elem[x] >= 0){
x = elem[x];
}
return x;
}
public void merge(int x1, int x2){
int index1 = findRoot(x1);
int index2 = findRoot(x2);
if(index1 == index2) return;
elem[index1] = elem[index1] + elem[index2];
elem[index2] = index1;
}
public boolean isSameSet(int x1, int x2){
int index1 = findRoot(x1);
int index2 = findRoot(x2);
if(index1 == index2){
return true;
}
return false;
}
public boolean equationsPossible(String[] equations) {
int n = equations.length;
Arrays.fill(elem, -1);
for(int i = 0; i < n; i++){
String t = equations[i];
if(t.charAt(1) == '='){
merge(t.charAt(0) - 'a', t.charAt(3) - 'a');
}
}
for(int i = 0; i < n; i++){
String t = equations[i];
if(t.charAt(1) == '!'){
boolean flag = isSameSet(t.charAt(0) - 'a', t.charAt(3) - 'a');
if(flag) return false;
}
}
return true;
}
}二、LRUCache
1. LRUCache 的原理
LRU Cache 是 least recently used cache 的缩写；
LRU Cache 是高速缓存使用的一种数据结构，高速缓存价格昂贵，容量有限；因此当缓存的资源满了之后，再插入新资源时，就会淘汰最早使用的资源，保留最近使用的资源；
LRUCache 底层是一个哈希表加双向链表的结构：
存入资源时会先存到链表的尾巴节点，如果超出最大缓存容量，会删除头结点的资源；
查询资源时，不仅会将查询的资源返回，还会将这个资源重新放到链表的尾巴节点；
哈希表的作用就是查询某个资源会在 O(1) 的时间复杂度内查询到，链表的作用是保证资源的顺序（最近使用的顺序），且插入删除时间复杂度也是 O(1)；
2. 模拟实现 LRUCache
DLinkedNode：资源节点类，包含 key，val，prev，next 属性，还有构造方法，作用参考哈希表和双向链表；
head：头结点，不存实际的资源；
tail：尾巴节点，不存实际的资源；
head 和 tail 的作用：方便双向链表进行插入和删除操作，不会出现空节点异常；
usedSize：当前保存的数据的数量；
cache：哈希表，用于保存 key 和 DLinkedNode 的映射关系，用于解决双向链表查询时间复杂度 O(N) 的问题；
capacity：缓存的最大容量；
public class MyLRUCache {
static class DLinkedNode{
public int key;
public int val;
public DLinkedNode prev;
public DLinkedNode next;
public DLinkedNode(){
}
public DLinkedNode(int key, int val){
this.key = key;
this.val = val;
}
}
public DLinkedNode head;
public DLinkedNode tail;
public int usedSize;
public Map<Integer, DLinkedNode> cache;
public int capacity;
// 方法
// ......
}MyLRUCache(int capacity) 初始化头节点，尾巴节点，保存数据的数量，最大容量；
注意：一定要将头节点和尾巴节点连起来，防止首次插入节点时出现空指针异常；
put(int key, int val): void 插入节点；
思路：
插入节点时，要检查节点是否已经存在；
节点不存在，现在哈希表中增加节点，在双向链表的尾巴节点插入，注意 usedSize++；
插入后，注意判断当前节点的数量是否查过最大能缓存的数量；
如果超过了，要在哈希表中删除节点，在双向链表中删除头节点连接的第一个资源，注意 usedSize--；
如果节点已经存在了，更新节点的 val，并在双向链表中，将该节点放到尾巴节点的位置；
get(int key): int 返回节点对应的 val；
节点不存在，返回 -1;
节点存在，返回节点的 val，返回之前注意将节点放到双向链表尾巴节点的位置；
addToTail(DLinkedNode node)：在双向链表的尾巴节点的位置插入节点 node；
removeHead(): DLinkedNode 删除头节点相连的节点，并返回该节点；
remove(DLinkedNode node): void 在双向链表中删除节点 node；
moveToTail(DLinkedNode node): void 在双向链表中删除 node，并将 node 放在双向链表尾巴节点的位置；
public MyLRUCache(int capacity){
this.head = new DLinkedNode();
this.tail = new DLinkedNode();
this.head.next = this.tail;
this.tail.prev = this.head;
cache = new HashMap<>();
this.capacity = capacity;
this.usedSize = 0;
}
public void put(int key, int val){
// 1. 插入的时候要判断节点是否已经存在
DLinkedNode node = cache.getOrDefault(key, null);
if(node == null){
// 3. 如果不存在，就插入哈希表
DLinkedNode cur = new DLinkedNode(key, val);
cache.put(key, cur);
// 4. 将它放在队尾
addToTail(cur);
this.usedSize++;
// 5. 判断容量是否超了
if(usedSize > capacity){
// 6. 删除头结点
DLinkedNode t = removeHead();
cache.remove(t.key);
}
}else{
// 2. 如果存在，就要更新对应 key 的值
node.val = val;
moveToTail(node);
}
}
public int get(int key){
DLinkedNode node = cache.get(key);
if(node == null){
return -1;
}
moveToTail(node);
return node.val;
}
private void addToTail(DLinkedNode node){
DLinkedNode prev = this.tail.prev;
prev.next = node;
node.prev = prev;
node.next = this.tail;
this.tail.prev = node;
}
private DLinkedNode removeHead(){
DLinkedNode dLinkedNode = this.head.next;
DLinkedNode next = dLinkedNode.next;
this.head.next = next;
next.prev = this.head;
return dLinkedNode;
}
private void moveToTail(DLinkedNode node){
remove(node);
addToTail(node);
}
private void remove(DLinkedNode node){
DLinkedNode prev = node.prev;
DLinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
3. LinkedHashMap
JDK 中可以使用 LinkedHashMap 实现 LRUCache；
构造方法：
initialCapacity： 初始容量；
loadFactor：哈希表的负载因子；
accessOrder：
true：每次查询或者新增后，都会将该节点放在双向链表的尾巴节点的位置；
false：会按照默认顺序存放，默认为 false；
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}afterNodeInsertion(boolean evict): void 插入节点后是否要删除插入最早的节点；
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}removeEldestEntry(Map.Entry<K, V> eldest): boolean 是否删除最老的节点，默认为 false；
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}使用 LinkedHashMap 实现 LRUCache 一定要重写这个方法；
4. 基于 LinkedHashMap 实现 LRUCache
基于 LinkedHashMap 实现需要指定容量，重写 put() 和 get() 方法；
重写 removeEldestEntry()：当数据量超出指定容量后，会删除最老的数据；
public class LRUCacheOnLinkedHashMap extends LinkedHashMap<Integer, Integer> {
public int capacity;
public LRUCacheOnLinkedHashMap(int capacity){
this.capacity = capacity;
}
@Override
public Integer put(Integer key, Integer value) {
return super.put(key, value);
}
@Override
public Integer get(Object key) {
return super.get(key);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}