深入了解 Java 各种容器（三）

此篇了解 LinkedHashSet 与 LinkedHashMap

继承了 HashMap 的 LinkedHashMap 拥有 HashMap 所有的特点，除此之外，LinkedHashMap 还通过双向链表保证了元素的有序

LinkedHashMap 源码只有 700 来行，主要通过重写 HashMap 的方法来增加功能

基础属性与方法

首先从构造方法开始，LinkedHashMap 对外提供 5 中构造方法

// 无参构造
public LinkedHashMap() {
    super();
    accessOrder = false;
}

// 指定初始容量
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false
}

// 指定初始容量与负载因子boolean accessOrder
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

// 指定初始容量、负载因子和排序模式
public LinkedHashMap(int initialCapacity, 
                     float loadFactor, 
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

// 先使用无参构造实例化，然后将指定map映射到初始化的实例中
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

LinkedHashMap 中多了一个属性 accessOrder 排序模式，如果为 true 表示按访问顺序，false 表示按插入顺序

另外还有两个关键的属性

// 链表头元素
transient LinkedHashMap.Entry<K,V> head;

// 链表尾元素
transient LinkedHashMap.Entry<K,V> tail;

双向链表的静态内部类节点

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

重写方法

LinkedHashMap 对 HashMap 重写的方法是其核心

void reinitialize() {
    super.reinitialize();
    this.head = this.tail = null;
}

HashMap.Node<K, V> newNode(int hash, K key, V value, HashMap.Node<K, V> e) {
    Entry<K, V> p = new Entry(hash, key, value, e);
    this.linkNodeAtEnd(p);
    return p;
}

HashMap.Node<K, V> replacementNode(HashMap.Node<K, V> p, HashMap.Node<K, V> next) {
    Entry<K, V> q = (Entry)p;
    Entry<K, V> t = new Entry(q.hash, q.key, q.value, next);
    this.transferLinks(q, t);
    return t;
}

HashMap.TreeNode<K, V> newTreeNode(int hash, K key, V value, HashMap.Node<K, V> next) {
    HashMap.TreeNode<K, V> p = new HashMap.TreeNode(hash, key, value, next);
    this.linkNodeAtEnd(p);
    return p;
}

HashMap.TreeNode<K, V> replacementTreeNode(HashMap.Node<K, V> p, HashMap.Node<K, V> next) {
    Entry<K, V> q = (Entry)p;
    HashMap.TreeNode<K, V> t = new HashMap.TreeNode(q.hash, q.key, q.value, next);
    this.transferLinks(q, t);
    return t;
}

// remove 后断开链接
void afterNodeRemoval(HashMap.Node<K, V> e) {
    Entry<K, V> p = (Entry)e;
    Entry<K, V> b = p.before;
    Entry<K, V> a = p.after;
    p.before = p.after = null;
    if (b == null) {
        this.head = a;
    } else {
        b.after = a;
    }

    if (a == null) {
        this.tail = b;
    } else {
        a.before = b;
    }

}

void afterNodeInsertion(boolean evict) {
    Entry first;
    // removeEldestEntry 可用于实现 LRU，删除最「老」节点
    if (evict && (first = this.head) != null && this.removeEldestEntry(first)) {
        K key = first.key;
        this.removeNode(hash(key), key, (Object)null, false, true);
    }

}

// 将节点移动到最后
void afterNodeAccess(HashMap.Node<K, V> e) {
    Entry<K, V> last;
    if (accessOrder && (last = tail) != e) {// 按插入排序并且e不是最后一个节点
        Entry<K, V> p = (Entry<K, V>) e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;// 如果e是头节点，将头换为e的下节点
        else
            b.after = a;// 如果e不是头节点，将上个节点连接下个节点
        if (a != null)
            a.before = b;// 如果存在下个节点，连接下个节点与上个节点
        else
            last = b;// 如果不存在下个节点，先将上个节点放到最后
        if (last == null)
            head = p;// 如果最后个节点为空，就直接把p（e）放到最后
        else {
            // 如果最后个节点不为空，就将p加到最后个节点的后面
            p.before = last;
            last.before = p;
        }
        tail = p;
        ++modCount;
    }
}

void internalWriteEntries(ObjectOutputStream s) throws IOException {
    for(Entry<K, V> e = this.head; e != null; e = e.after) {
        s.writeObject(e.key);
        s.writeObject(e.value);
    }
}

有序性

可以通过 LinkedHashMap 的 accessOrder 属性控制其内部元素的顺序

public class LinkedHashMapExample {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();

        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");

        System.out.println("Insertion Order:");
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        // Access order demonstration
        map = new LinkedHashMap<>(16, 0.75f, true);
        map.put(1, "one");
        map.put(2, "two");
        map.put(3, "three");

        map.get(2);
        map.get(1);

        System.out.println("Access Order:");
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

LRU 缓存

利用 LinkedHashMap 的访问顺序特性，可以轻松实现一个 LRU（Least Recently Used，最近最少使用）缓存。只需要在构造 LinkedHashMap 时设置 accessOrder 为 true，并覆盖 removeEldestEntry 方法，使其在缓存大小超过指定容量时自动删除最久未访问的条目

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

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

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

LinkedHashSet

和 HashSet 一样，LinkedHashSet 也是对 LinkedHashMap 的封装，本质依然是 LinkedHashMap