Java中LinkedHashMap的作用 解析保持插入顺序的Map实现

linkedhashmap与hashmap的区别在于前者维护插入顺序，后者不保证顺序。1.linkedhashmap继承hashmap并用双向链表记录顺序，遍历时按插入顺序访问；2.hashmap查找效率更高但无序；3.当需要顺序或实现lru缓存时应使用linkedhashmap；4.linkedhashmap通过accessorder参数和removeeldestentry方法支持lru策略；5.其迭代性能略低于hashmap但空间开销稍大。

LinkedHashMap在Java中主要作用是提供一个可以记住键值对插入顺序的Map实现。这意味着当你遍历LinkedHashMap时，你会按照元素被添加到Map中的顺序访问它们。这在某些需要维护元素顺序的场景下非常有用。

保持插入顺序的Map实现

LinkedHashMap继承自HashMap，但它通过维护一个双向链表来记录元素的插入顺序。因此，它在HashMap的基础上增加了顺序性。

立即学习“Java免费学习笔记（深入）”；

LinkedHashMap与HashMap的区别是什么？什么时候应该使用LinkedHashMap？

HashMap不保证元素的顺序，而LinkedHashMap保证元素的插入顺序。当你需要按照元素插入的顺序来遍历Map时，应该使用LinkedHashMap。例如，LRU缓存的实现就非常适合使用LinkedHashMap。HashMap查找效率更高（平均情况下），但是不保证顺序。LinkedHashMap在迭代时会有额外的开销，因为它需要维护链表。

具体来说，如果你的应用场景对顺序没有要求，且性能是首要考虑因素，那么HashMap可能是更好的选择。但如果顺序很重要，或者你需要实现一些特殊的缓存策略（如LRU），那么LinkedHashMap就是理想的选择。

BlackBox AI

AI编程助手，智能对话问答助手

下载

LinkedHashMap是如何实现保持插入顺序的？

LinkedHashMap内部维护了一个双向链表，它连接了所有Map中的Entry。每次插入或访问元素时，LinkedHashMap会更新这个链表，以保证链表中元素的顺序与插入顺序一致。

具体来说，LinkedHashMap内部的Entry类除了包含key、value和hash值外，还包含before和after两个指针，分别指向链表中的前一个和后一个Entry。当put一个新的键值对到LinkedHashMap中时，新的Entry会被添加到链表的末尾。当访问一个已存在的键值对时，如果accessOrder设置为true（默认是false，即保持插入顺序），那么这个Entry会被移动到链表的末尾。

如何使用LinkedHashMap实现一个简单的LRU缓存？

LRU (Least Recently Used) 缓存是一种常见的缓存淘汰策略，它会移除最近最少使用的元素。使用LinkedHashMap可以很容易地实现一个LRU缓存。

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

public class LRUCache extends LinkedHashMap {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder = true
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache<>(3);
        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);
        System.out.println(cache); // {A=1, B=2, C=3}

        cache.get("A");
        System.out.println(cache); // {B=2, C=3, A=1}

        cache.put("D", 4);
        System.out.println(cache); // {C=3, A=1, D=4}  B被移除了
    }
}

这段代码的关键在于LinkedHashMap的构造函数中的accessOrder = true，以及重写removeEldestEntry方法。当accessOrder为true时，每次访问元素都会将其移动到链表末尾。removeEldestEntry方法会在每次put新元素时被调用，如果返回true，则会移除链表头部的元素，也就是最久未使用的元素。

LinkedHashMap的性能如何？与HashMap相比有什么差异？

LinkedHashMap在插入和删除操作上的性能与HashMap相似，都是O(1)（平均情况下）。但是，由于LinkedHashMap需要维护一个双向链表，所以在迭代时会有额外的开销。HashMap的迭代时间复杂度是O(capacity)，而LinkedHashMap的迭代时间复杂度是O(size)，其中capacity是HashMap的容量，size是Map中元素的数量。因此，当Map中的元素数量远小于容量时，LinkedHashMap的迭代性能可能会更好。

总的来说，如果对顺序有要求，且Map中的元素数量不大，那么LinkedHashMap的性能是可以接受的。但如果对性能要求非常高，且不需要保证顺序，那么HashMap可能更适合。另外，需要注意的是，LinkedHashMap的空间复杂度略高于HashMap，因为它需要额外的空间来存储链表节点。