Java 容器源码分析之 LinkedHashMap（5）

look_w

在 containsValue 和 internalWriteEntries 中也使用了双向链表进行遍历。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public boolean containsValue(Object value) {     //使用双向链表进行遍历     for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {         V v = e.value;         if (v == value || (value != null && value.equals(v)))             return true;     }     return false; } //覆盖父类方法 //序列化，Called only from writeObject, to ensure compatible ordering. void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {     //调整元素的遍历方式，使用双链表遍历     for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {         s.writeObject(e.key);         s.writeObject(e.value);     } }

使用 LinkedHashMap 实现 LRU CacheLinkedHashMap 的访问序可以方便地用来实现一个 LRU Cache。在访问序模式下，尾部节点是最近一次被访问的节点 (least-recently)，而头部节点则是最远访问 (most-recently) 的节点。因而在决定失效缓存的时候，将头部节点移除即可。
但是，由于链表是无界的，但缓存往往是资源受限的，如何确定何时移除最远访问的缓存呢？前面分析过，在 afterNodeInsertion 中，会调用 removeEldestEntry 来决定是否将最老的节点移除，因而我们可以使用 LinkedHashMap 的子类，并重写 removeEldestEntry 方法，当 Enrty 的数量超过缓存的容量是返回 true 即可。
下面给出基于 LinkedHashMap 实现的 LRU Cache 的代码：
[url=][/url]
public class CacheImpl<K,V> {    private Map<K, V> cache;    private int capacity;    public enum POLICY {        LRU, FIFO    }    public CacheImpl(int cap, POLICY policy) {        this.capacity = cap;        cache = new LinkedHashMap<K, V>(cap, 0.75f, policy.equals(POLICY.LRU)){            //超出容量就删除最老的值            @Override            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {                return size() > capacity;            }        };    }    public V get(K key) {        if (cache.containsKey(key)) {            return cache.get(key);        }        return null;    }    public void set(K key, V val) {        cache.put(key, val);    }    public void printKV() {        System.out.println("key value in cache");        for (Map.Entry<K,V> entry : cache.entrySet()) {            System.out.println(entry.getKey() + ":" + entry.getValue());        }    }    public static void main(String[] args) {        CacheImpl<Integer, String> cache = new CacheImpl(5, POLICY.LRU);        cache.set(1, "first");        cache.set(2, "second");        cache.set(3, "third");        cache.set(4, "fourth");        cache.set(5, "fifth");        cache.printKV();        cache.get(1);        cache.get(2);        cache.printKV();        cache.set(6, "sixth");        cache.printKV();    }}[url=][/url]


小结本文对 JDK 8 中的 LinkedHashMap 的源码及实现进行了简单的分析。LinkedHashMap 继承自 HashMap，并在其基本结构上增加了双向链表的实现，因而 LinkedHashMap 在内存占用上要比 HashMap 高出许多。LinkedHashMap 仍然沿用了 HashMap 中基于桶数组、桶内单链表和红黑树结构的哈希表，在哈希计算、定位、扩容等方面都和 HashMAp 是一致的。LinkedHashMap 同样支持为 null 的键和值。
由于增加了双向链表将所有的 Entry 串在一起，LinkedHashMap 的一个重要的特点就是支持按照插入顺序或访问顺序来遍历所有的 Entry，这一点和 HashMap 的乱序遍历很不相同。在一些对顺序有要求的场合，就需要使用 LinkedHashMap 来替代 HashMap。
由于双向链表的缘故，在遍历时可以直接在双向链表上进行，因而遍历时间复杂度和容量无关，只和当前 Entry 数量有关。这点相比于 HashMap 要更加高效一些。