Java中的LinkedHashMap

在Java编程中，我们经常需要使用到HashMap，它是一个非常常用的数据结构。用于存储键值对，并且可以根据键快速的查找对应的值。但是HashMap在遍历时是无序的，因为HashMap使用哈希表来存储数据，哈希表并不保证元素的顺序。如果需要有序的遍历，就可以使用LinkedHashMap，它是HashMap的一个子类，除了具备HashMap的所有特性外，还可以保证插入顺序或者访问顺序。

LinkedHashMap的使用

LinkedHashMap类定义了两种运行模式：插入顺序和访问顺序。默认情况下，LinkedHashMap是以插入顺序运行的，即保持元素的插入顺序，当指定accessOrder=true时，LinkedHashMap将按访问顺序运行，即元素被访问的顺序。

下面是一个使用LinkedHashMap的例子：

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("1", "One");
        linkedHashMap.put("2", "Two");
        linkedHashMap.put("3", "Three");
        linkedHashMap.put("4", "Four");
        linkedHashMap.put("5", "Five");

        for (Map.Entry<String, String> entry : linkedHashMap.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}

输出结果为：

1 = One
2 = Two
3 = Three
4 = Four
5 = Five

可以看到输出的顺序与插入的顺序一致。如果我们将LinkedHashMap中的元素访问一遍，再进行输出，则输出的顺序将会变为访问的顺序。

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true); // accessOrder=true
        linkedHashMap.put("1", "One");
        linkedHashMap.put("2", "Two");
        linkedHashMap.put("3", "Three");
        linkedHashMap.put("4", "Four");
        linkedHashMap.put("5", "Five");

        linkedHashMap.get("1"); // 访问1
        linkedHashMap.get("3"); // 访问3

        for (Map.Entry<String, String> entry : linkedHashMap.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}

输出结果为：

2 = Two
4 = Four
5 = Five
1 = One
3 = Three

可以看到输出的顺序已经不再是插入的顺序，而是访问的顺序。

如何在LinkedHashMap中实现LRU缓存

LRU是Least Recently Used的缩写，即最近最少使用算法。在缓存淘汰策略中，会优先淘汰最近最少被使用的数据，而保留最常用的数据。在LinkedHashMap中，通过accessOrder=True可以实现按照访问顺序来运行，因此可以用LinkedHashMap来实现LRU缓存。

下面是一个简单的实现LRU缓存的例子：

import java.util.LinkedHashMap;
import java.util.Map;

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int cacheSize;

    public LRUCache(int cacheSize) {
        super((int) Math.ceil(cacheSize / 0.75f) + 1, 0.75f, true); // accessOrder=true
        this.cacheSize = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > cacheSize;
    }
}

public class LRUCacheExample {
    public static void main(String[] args) {
        LRUCache<String, String> cache = new LRUCache<>(3);
       cache.put("1", "One");
        cache.put("2", "Two");
        cache.put("3", "Three");
        System.out.println(cache); // 输出：{1=One, 2=Two, 3=Three}

        cache.get("2");
        System.out.println(cache); // 输出：{1=One, 3=Three, 2=Two}

        cache.put("4", "Four");
        System.out.println(cache); // 输出：{3=Three, 2=Two, 4=Four}

        cache.put("5", "Five");
        System.out.println(cache); // 输出：{2=Two, 4=Four, 5=Five}
    }
}

在LRUCache类中，我们继承了LinkedHashMap，重写了其removeEldestEntry方法。该方法会在每次put操作后被调用，如果返回true，则移除第一个元素，否则继续保留。在LRUCache构造函数中，我们指定了accessOrder=true，因此LinkedHashMap会按照访问顺序来保存元素。

在LRUCacheExample中，我们首先插入了三个元素1、2、3，此时LinkedHashMap中保存的顺序是1、2、3。然后我们访问了元素2，此时LinkedHashMap中的顺序变为1、3、2。然后插入了元素4，LinkedHashMap中的顺序变为3、2、4，因为元素1是最早插入的，同时最近没有被访问，因此被移除了。最后插入元素5，LinkedHashMap中保留的元素为2、4、5，因为元素3已经被访问过，但是比元素1晚插入，因此被移除了。

结论

LinkedHashMap是HashMap的一个子类，除了具备HashMap的所有特性外，还可以保证插入顺序或者访问顺序。可以用LinkedHashMap来实现LRU缓存。在LinkedHashMap中，通过accessOrder=True可以实现按照访问顺序来运行。在LRUCache中，我们继承了LinkedHashMap，重写了其removeEldestEntry方法，该方法会在每次put操作后被调用，如果返回true，则移除第一个元素，否则继续保留。