Java8集合系列之LinkedHashMap

Posted on   |   In   |     |   visitors

前段时间整理了一下Java集合框架中的常用的集合类，用xmind进行了归类，如下：

LinkedHashMap相比较ConcurrentHashMap和HashMap两个map类来说用的要少，但是还是想了解一下这个map的实现原理，看完发现其实很简单，从源码的行数就可以看出，HashMap有2300多行代码，而LinkedHashMap才700多行，为什么呢？

继承结构

public class LinkedHashMap extends HashMap implements Map

LinkedHashMap是继承了HashMap，所以相当于是拥有了HashMap的特性，然后根据自身特点进行了定制。

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//调用父类HashMap的构造方法。
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
/**
 * //调用父类HashMap的构造方法。
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the default initial capacity (16) and load factor (0.75).
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}

重要属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//链表结点
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);
    }
}
private static final long serialVersionUID = 3801124242820219131L;
//链表头部
transient LinkedHashMap.Entry<K,V> head;
//链表尾部
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.
 */
final boolean accessOrder;

put方法

在LinkedHashMap中根本找不到put方法，那只有在父类中看了，关于这一部分源码可以看HashMap这篇文章，里面有put方法的介绍，不过对于put中调用的一些关键的特殊的方法，LinkedHashMap进行了重写。

newNode方法

1
2
3
4
5
6
7
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    //Entry内部类是继承了HashMap中的Node类
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

LinkedHashMap重写了该方法，在put进行了调用，newNode方法在新建一个结点的同时，直接将结点按照插入顺序加在了链表的末尾，而且该链表是双向链表。

replacementTreeNode

在进行红黑树转换的时候一些方法也进行了重写，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    //TreeNode依旧是HashMap中的内部类
    TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}
//就是对原来双向链表中的结点结点进行替换，替换成TreeNode结点（另外，TreeNode继承了LinkedHashMap.Entry）
private void transferLinks(LinkedHashMap.Entry<K,V> src,
                           LinkedHashMap.Entry<K,V> dst) {
    LinkedHashMap.Entry<K,V> b = dst.before = src.before;
    LinkedHashMap.Entry<K,V> a = dst.after = src.after;
    if (b == null)
        head = dst;
    else
        b.after = dst;
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}

get方法

1
2
3
4
5
6
7
8
9
public V get(Object key) {
    Node<K,V> e;
    //调用HashMap中的getNode方法
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)//accessOrder默认值false
        afterNodeAccess(e);
    return e.value;
}

小结

  • 如果这样一种情形，我们需要按照元素插入的顺序来访问元素，此时，LinkedHashMap就派上用场了，它保存着元素插入的顺序，并且可以按照我们插入的顺序进行访问。
  • LinkedHashMap会将元素串起来，形成一个双链表结构。可以看到，其结构在HashMap结构上增加了链表结构。数据结构为（数组 + 单链表 + 红黑树 + 双链表）。

-EOF-