LinkedHashMapHashMap的子类,其与HashMap最大的区别就是 使用了一个双向链表对结点进行存储,通过这个链表可以实现Map中的数据有序。在HashMap中遍历数据是根据key的哈希值遍历的,LinkedHashMap可以根据key插入的顺序或者结点的访问顺序进行遍历。当我们需要记录插入Map结点的顺序时,可以使用LinkedHashMap。同时LinkedHashMap是线程不同步的,如果需要进行同步可以使用Collections.synchronizedMap(new LinkedHashMap(...))

LinkedHashMap.Entry

LinkedHashMap.EntryLinkedHashMap的内部类,继承自HashMap.Node,是LinkedHashMap中的结点类型。它相比于HashMap.Node就增加了两个引用,构成双向链表。

1
2
3
4
5
6
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.put

LinkedHashMap的put方法继承自HashMap,在HashMap源码解析中我们已经提到了这个方法,其中需要注意的是LinkedHashMap重写了HashMap中的newNode方法,这样就可以替换掉HashMap.Node

1
2
3
4
5
6
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

在newNode方法的最后,将新建的对象加入双向链表的尾部。

accessOrder

在LinkedHashMap中保存了三个主要的成员变量:

1
2
3
4
5
transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;

final boolean accessOrder;

分别代表双向链表的头、尾,以及LinkedHashMap的遍历顺序,accessOrder为false则表示按照结点插入顺序遍历,否则按结点访问顺序遍历。

结点插入顺序比较好理解,但是结点访问顺序就有点难懂,下面我们写个实例来看看两种顺序的区别。

插入顺序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
Map<String, String> map = new LinkedHashMap<>(16,0.75f,false);
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");


for (Object o : map.entrySet()) {
    Map.Entry entry = (Map.Entry) o;
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

输出结果:

1
2
3
4
apple=苹果
watermelon=西瓜
banana=香蕉
peach=桃子

访问顺序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Map<String, String> map = new LinkedHashMap<>(16,0.75f,true);
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");

map.get("banana");
map.get("apple");

for (Object o : map.entrySet()) {
    Map.Entry entry = (Map.Entry) o;
    System.out.println(entry.getKey() + "=" + entry.getValue());
}

输出结果:

1
2
3
4
watermelon=西瓜
peach=桃子
banana=香蕉
apple=苹果

从上面我们可以看出访问过的元素都输出在最后,这是为什么呢?我们来看看get方法。

1
2
3
4
5
6
7
8
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

如果accessOrder为true,也就是访问顺序,就会调用afterNodeAccess方法,afterNodeAccess方法就是将这个结点放到链表的尾部。

put方法内部也会触发afterNodeAccess方法,所以要注意put方法也算访问元素,会导致List的遍历顺序发生改变