Java集合——LinkedHashMap

LinkedHashMap继承了HashMap，其操作与HashMap类似，结构也差不多。与HashMap最大区别就是通过节点Entry增加了before和after属性来维护顺序使其有序。示例根据插入顺序排序:

public static void main(String[] args) {
        System.out.println("**********HashMap***********");
        Map hashMap = new HashMap();
        hashMap.put("Marvel", "漫威");
        hashMap.put("Deadpool", "死侍");
        hashMap.put("Hulk", "绿巨人");
        hashMap.put("Thor", "雷神");
        hashMap.put("Wolverine", "金刚狼");
        for (Iterator it = hashMap.entrySet().iterator(); it.hasNext(); ) {
            Map.Entry obj = (Map.Entry)it.next();
            System.out.println(obj.getKey() + "-" +obj.getValue());
        }
        System.out.println("**********LinkedHashMap***********");
        Map linkedHashMap = new LinkedHashMap();
        linkedHashMap.put("Marvel", "漫威");
        linkedHashMap.put("Deadpool", "死侍");
        linkedHashMap.put("Hulk", "绿巨人");
        linkedHashMap.put("Thor", "雷神");
        linkedHashMap.put("Wolverine", "金刚狼");
        for (Iterator it = linkedHashMap.entrySet().iterator(); it.hasNext(); ) {
            Map.Entry obj = (Map.Entry)it.next();
            System.out.println(obj.getKey() + "-" +obj.getValue());
        }
    }

输出:

**********HashMap***********
    Thor-雷神
    Deadpool-死侍
    Wolverine-金刚狼
    Marvel-漫威
    Hulk-绿巨人
    **********LinkedHashMap***********
    Marvel-漫威
    Deadpool-死侍
    Hulk-绿巨人
    Thor-雷神
    Wolverine-金刚狼

源码分析

LinkedHashMap字段

final boolean accessOrder;                //是否按照访问顺序，true:访问顺序，false:插入顺序
    transient LinkedHashMap.Entry head;       //双向链表头节点
    transient LinkedHashMap.Entry tail;       //双向链表尾结点
    
    /**
     * 节点类继承了HashMap.Node，改成双向链表
     * next表示桶上连接的Entry顺序
     * before、after插入前后，插入顺序(维护双向链表)
     */
    static class Entry extends HashMap.Node {
        Entry before, after;
    }

构造方法

前四个默认插入排序，最后一个可指定排序，accessOrder为true时访问顺序，false时插入顺序

public LinkedHashMap() {
        super();
        accessOrder = false;
    }
    
    //指定初始化容量
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
    
    //指定初始化容量和负载因子
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
    
    //利用另一个map来构建
    public LinkedHashMap(Map m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }
    
    //指定初始化容量、负载因子和是否按照访问顺序
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

put方法

LinkedHashMap沿用了HashMap的put方法，不过重写了其newNode()、afterNodeAccess()、afterNodeInsertion()方法

Node newNode(int hash, K key, V value, Node e) {
        //调用LinkedHashMap的entry构造方法
        LinkedHashMap.Entry p =
            new LinkedHashMap.Entry(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
    
    /**
     * 将新增节点置于链表尾部
     */
    private void linkNodeLast(LinkedHashMap.Entry p) {
        //获取当前链表尾部节点
        LinkedHashMap.Entry last = tail;
        //将p设为尾部节点
        tail = p;
        //若当前集合为空，p既是头节点又是尾节点
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

从上面的源码可以看出，linkedHashMap额外维护了一个双向链表。

/**
     * 将当前被访问的节点移至双向链表尾部
     */
    void afterNodeAccess(Node e) { // move node to last
        LinkedHashMap.Entry last;
        //若accessOrder为true且原尾节点不是节点e
        if (accessOrder && (last = tail) != e) {
            //将节点e强转为双向链表节点p，获取p插入前后的节点
            LinkedHashMap.Entry p =
                (LinkedHashMap.Entry)e, b = p.before, a = p.after;
            //因为需要将e置于链表尾部，所以将其after属性设为null
            p.after = null;
            //对于双向链表，若p的前驱节点为空，头节点设为p的后继
            if (b == null)
                head = a;
            else
            //否则将p前驱节点的后继节点设为p的后继节点
                b.after = a;
            //若p的后继节点不为null，将p的后继节点的前驱节点设为p的前驱节点    
            if (a != null)
                a.before = b;
            else
            //否则将p的前驱节点设为尾结点
                last = b;
            //若原尾节点为空，将p设为头节点    
            if (last == null)
                head = p;
            else {
            //否则将p的前驱节点改为原尾节点，原尾节点的后继节点改为p
                p.before = last;
                last.after = p;
            }
            //尾节点改为p
            tail = p;
            ++modCount;
        }
    }

在put方法中新增节点情况下最后会调用afterNodeInsertion()方法，源码如下:

/**
     * 删除双向链表头节点
     */
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }
    
    //默认返回false
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return false;
    }

void afterNodeInsertion(boolean evict)以及boolean removeEldestEntry(Map.Entry<K,V> eldest)是构建LruCache需要的回调，在LinkedHashMap里可以忽略它们

get方法

LinkedHashMap重写了其get()方法

public V get(Object key) {
        Node e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

相对于HashMap的get操作，linkedHashMap多了一步操作，若accessOrder为true会调用afterNodeAccess()方法。afterNodeAccess()方法上面已经提及，需要注意的是在此方法会修改modCount即当迭代LinkedHashMap,若同时查询访问数据，会导致fail-fast，因为迭代顺序变了

remove方法

LinkedHashMap沿用了HashMap的remove()方法，不过重写了其afterNodeRemoval()方法

/**
     * 将节点e从双向链表中删除
     */
    void afterNodeRemoval(Node e) { // unlink
        LinkedHashMap.Entry p =
            (LinkedHashMap.Entry)e, b = p.before, a = p.after;
        //待删除节点p的前驱后继节点都置空    
        p.before = p.after = null;
        //若前驱节点为空，则将p后继节点设为头节点
        if (b == null)
            head = a;
        //否则将p后继节点设为p前驱节点的后继节点    
        else
            b.after = a;
        //若p后继节点为空，则将p的前驱节点设为尾结点    
        if (a == null)
            tail = b;
        //否则p前驱节点设为p后继节点的前驱节点    
        else
            a.before = b;
    }

用LinkedHashMap实现缓冲机制

FIFO

FIFO(First In First Out):先入先出，和队列一样。举个生活例子，超市购物收银台结账先排队的客户先结账离开

FIFO实现:LinkedHashMap默认(accessOrder为false)就是按存储的数据排序，满足先进先出，示例如下:

public class FIFOCache extends LinkedHashMap {

    private final int maxSize;//限制数据

    public FIFOCache(int maxSize) {
        super();//调用父类默认构造方法，accessOrder为false
        this.maxSize = maxSize;
    }

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

    public static void main(String[] args) {
        Map fifoCache = new FIFOCache(10);//限定10个
        for (int i = 0; i < 10; i++) {
            fifoCache.put(i, i);
        }
        System.out.println("初始情况:" + fifoCache.toString());

        fifoCache.put(6, 6);//访问已存在数据
        System.out.println("已存在数据被访问后:" + fifoCache.toString());

        fifoCache.put(10, 10);
        System.out.println("新增一个数据后:" + fifoCache.toString());
    }
}

输出:

初始情况:{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
已存在数据被访问后:{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
新增一个数据后:{1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9, 10=10}

从输出结果中看，其满足FIFO规则，按插入顺序进行排序，若命中缓存中的任意数据也不会破坏先进先出规则。若新增了一个缓存外的数据会把最先插入的数据移除

LRU

public class LRUCache extends LinkedHashMap {

    private final int maxSize;

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

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

    public static void main(String[] args) {
        Map fifoCache = new LRUCache(10);//限定10个
        for (int i = 0; i < 10; i++) {
            fifoCache.put(i, i);
        }
        System.out.println("初始情况:" + fifoCache.toString());

        fifoCache.put(6, 6);//访问已存在数据
        fifoCache.get(3);
        System.out.println("已存在数据被访问后:" + fifoCache.toString());

        fifoCache.put(10, 10);
        System.out.println("新增一个数据后:" + fifoCache.toString());
    }
}

输出:

初始情况:{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
已存在数据被访问后:{0=0, 1=1, 2=2, 4=4, 5=5, 7=7, 8=8, 9=9, 6=6, 3=3}
新增一个数据后:{1=1, 2=2, 4=4, 5=5, 7=7, 8=8, 9=9, 6=6, 3=3, 10=10}

从输出结果中可以看出，符合LRU规则