JDK源码之LinkedHashMap源码剖析

发表于 | 分类于

LinkedHashMap继承了HashMap类并实现了Map接口，其内部维护了一个双向链表，在每次插入数据或者修改访问数据，在双链表中会存在相应的增删高的操作，从而实现将无序的HashMap通过双链表将其管理为有序状态的map类型。

内部节点

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中的节点Entry继承了HashMap中内部类Node，为其添加两个链表以实现节点之间的有序存储。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//Hashmap中的节点
static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        //omit
    }

同时存在两个成员变量，head和tail指向双链表的首尾两端，以及一个accessOrder，accessOrder指定双链表的迭代顺序，如果其为true，则采用访问顺序，如果为false，则采用插入顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> head;
/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMap.Entry<K,V> tail;
/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * 构造一个按照插入顺序迭代的Hashmap对象，并指定初始容量和扩展因子
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
/**
 * 构造一个按照插入顺序迭代的Hashmap对象，并指定初始容量，使用默认的扩展因子0.75
 * @param  initialCapacity the initial capacity
 * @throws IllegalArgumentException if the initial capacity is negative
 */
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
/**
 * 构造一个按照插入顺序迭代的Hashmap对象，使用默认的初始容量16和扩展因子0.75
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}
/**
 * 通过一个map构造一个按照插入顺序迭代的Hashmap对象，
 * 初始容量为大于map的值,扩展因子0.75
 *
 * @param  m the map whose mappings are to be placed in this map
 * @throws NullPointerException if the specified map is null
 */
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    //批量插入一个map到本集合中
    putMapEntries(m, false);
}
/**
 * 构造一个按照插入顺序迭代的Hashmap对象，并指定初始容量和扩展因子，和迭代顺序
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @param  accessOrder     the ordering mode - <tt>true</tt> for
 *         access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

新增节点

  • LinkedHashMap添加节点采用的是HashMap中的put方法。在putVal方法中调用了newNode()方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
          //omit...
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
  • LinkedHashMap重写了构建节点newNode()方法。
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;
}
  • 每次构建新节点时，通过linkNodeLast(p)将新节点链接在内部双向链表的尾部。
1
2
3
4
5
6
7
8
9
10
11
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}
  • putVal方法中最后调用了afterNodeInsertion(evict),很容易发现，在HashMap中这个方法是空的，而LinkedHashMap中重写了这些方法，用于对相应操作之后对双链表的修改。如果是按照
1
2
3
4
5
// hashMao中的预留函数
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
1
2
3
4
5
6
7
8
9
10
11
12
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    //判断是否需要移除最老的值
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
//默认是不移除的，但是如果要实现缓存，需要删除最老的值。实现LRUCache需要重写该方法
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}
  • Demo展示：
1
2
3
4
5
6
7
8
9
public class LinkedHashMapDemo {
    public static void main(String[] args) {
        Map<Integer,String> map = new LinkedHashMap<>();
        for (int i = 1; i < 7; i++) {
            map.put(i, "" + i);
            System.out.println(map.toString());
        }
    }
}
1
2
3
4
5
6
{1=1}
{1=1, 2=2}
{1=1, 2=2, 3=3}
{1=1, 2=2, 3=3, 4=4}
{1=1, 2=2, 3=3, 4=4, 5=5}
{1=1, 2=2, 3=3, 4=4, 5=5, 6=6}

删除节点

  • LinkedHashMap没有重写删除节点，调用HashMap中的删除方法。删除之后通过调用重写之后的afterNodeRemoveal()这个回调方法来对双链表进行调整。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//删除节点e时，需要相应调整双链表
void afterNodeRemoval(Node<K,V> e) { // unlink
   LinkedHashMap.Entry<K,V> p =
       (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
   //链表节点中只有e一个节点
   p.before = p.after = null;
   //e为头节点
   if (b == null)
       head = a;
   else
       b.after = a;
   //e为尾节点
   if (a == null)
       tail = b;
   else
       a.before = b;
}
  • Demo展示
1
2
3
4
5
6
7
8
9
10
11
12
13
public class LinkedHashMapDemo {
    public static void main(String[] args) {
        Map<Integer,String> map = new LinkedHashMap<>();
        for (int i = 1; i < 7; i++) {
            map.put(i, "" + i);
            System.out.println(map.toString());
        }
        map.remove(6);
        System.out.println(map.toString());
        map.remove(3);
        System.out.println(map.toString());
    }
}
1
2
3
4
5
6
7
{1=1, 2=2}
{1=1, 2=2, 3=3}
{1=1, 2=2, 3=3, 4=4}
{1=1, 2=2, 3=3, 4=4, 5=5}
{1=1, 2=2, 3=3, 4=4, 5=5, 6=6}
{1=1, 2=2, 3=3, 4=4, 5=5}
{1=1, 2=2, 4=4, 5=5}

查找节点

  • 没错，LinkedHashMap重写了get方法及getOrDefaul方法,比较简单，就是查找，查找完之后，如果迭代顺序采用是访问顺序，则需要调用函数afterNodeAccess来调整双向链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}
public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
   if (accessOrder)
       afterNodeAccess(e);
   return e.value;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//将访问过的节点移动至内部的双向链表的尾部。
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

  • Demo展示

    • 按照插入顺序输出

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      public class LinkedHashMapDemo {
          public static void main(String[] args) {
              Map<Integer,String> map = new LinkedHashMap<>();
              for (int i = 1; i < 7; i++) {
                  map.put(i, "" + i);
              }
              System.out.println(map.toString());
              map.get(3);
              map.get(6);
              System.out.println(map);
          }
      }
      1
      2
      {1=1, 2=2, 3=3, 4=4, 5=5, 6=6}
      {1=1, 2=2, 3=3, 4=4, 5=5, 6=6}

    • 按照访问顺序输出，accessOrder=true

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      public class LinkedHashMapDemo {
          public static void main(String[] args) {
              Map<Integer,String> orderMap = new LinkedHashMap<Integer, String >(16,0.75f, true);
              for (int i = 1; i < 7; i++) {
                  orderMap.put(i, "" + i);
              }
              System.out.println(orderMap.toString());
              orderMap.get(3);
              System.out.println(orderMap);
              orderMap.get(1);
              System.out.println(orderMap);
          }
      }
      1
      2
      3
      {1=1, 2=2, 3=3, 4=4, 5=5, 6=6}
      {1=1, 2=2, 4=4, 5=5, 6=6, 3=3}
      {2=2, 4=4, 5=5, 6=6, 3=3, 1=1}

containsValue方法

HashMap中的containsValue方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

LinkedHashMap中：

1
2
3
4
5
6
7
8
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;
}

显然，后者的实现更加的高效。

遍历

LinkedHashMap中重写了entrySet()方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
    public final int size()                 { return size; }
    public final void clear()               { LinkedHashMap.this.clear(); }
    public final Iterator<Map.Entry<K,V>> iterator() {
        return new LinkedEntryIterator();
    }
    public final boolean contains(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        Object key = e.getKey();
        Node<K,V> candidate = getNode(hash(key), key);
        return candidate != null && candidate.equals(e);
    }
    public final boolean remove(Object o) {
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Object value = e.getValue();
            return removeNode(hash(key), key, value, true, true) != null;
        }
        return false;
    }
    public final Spliterator<Map.Entry<K,V>> spliterator() {
        return Spliterators.spliterator(this, Spliterator.SIZED |
                                        Spliterator.ORDERED |
                                        Spliterator.DISTINCT);
    }
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        if (action == null)
            throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
            action.accept(e);
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}
  • 重写之后迭代LinkedHashMap就是从内部维护的双链表的表头开始循环输出。

总结

  • LinkedHashMap继承HashMap，只需要重写几个方法，来改变其迭代遍历的顺序。同时在插入数据，访问数据，修改数据，会增加双链表上的节点或者调整顺序，来决定迭代时的输出顺序。
  • 相应操作的回调函数，HashMap中有相应的空方法，也就意味着LinkedHashMap只需要重写这几个回调函数，而不用重写插入和删除方法。
  • LinkedhashMap重写了get方法。
  • LinkedHashMap优化了containsValue方法，提高其遍历性能。

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.LinkedHashMap;
import java.util.Map;
/**
 * Created by cdx0312
 * 2018/4/4
 */
public class LinkedHashMapDemo {
    public static void main(String[] args) {
        Map<Integer,String> map = new LinkedHashMap<>();
        for (int i = 1; i < 7; i++) {
            map.put(i, "" + i);
//            System.out.println(map.toString());
        }
        System.out.println(map.toString());
//        map.remove(6);
//        System.out.println(map.toString());
//        map.remove(3);
//        System.out.println(map.toString());
        map.get(3);
        map.get(6);
        System.out.println(map);
        Map<Integer,String> orderMap = new LinkedHashMap<Integer, String >(16,0.75f, true);
        for (int i = 1; i < 7; i++) {
            orderMap.put(i, "" + i);
        }
        System.out.println(orderMap.toString());
        orderMap.get(3);
        System.out.println(orderMap);
        orderMap.get(1);
        System.out.println(orderMap);
    }
}

Donate comment here