《Java源码解析》集合框架Map之LinkedHashMap

2016-12-24 16:01
以前都没有贴出来运行环境，今天加上OS和JDK版本，因为发现不同版本实现源码有些许差别：
OS : MacOS 10.11
JDK: jdk1.7-72

LinkedHashMap

1. 还是先看看LinkedHashMap类继承结构图

首先说说我对这个类名的理解，其实我觉得就是LinkedList+HashMap特性的集合。LinkedHashMap使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序。

我们知道HashMap对于插入元素的顺序并没有维护，也就是说迭代HashMap的顺序并不是元素插入的顺序，有时候我们期待一个有序的Map集合，这时LinkedHashMap产生了。它虽然增加了时间和空间上的开销，但是通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素迭代的顺序。

2.LinkedHashMap的基本结构

LinkedHashMap继承自HashMap，首先我们应该很明确两点：
1. LinkedHashMap可以认为是HashMap+LinkedList，即它使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序。
2. LinkedHashMap的基本实现思想就是—-多态，LinkedHashMap重写了其父类HashMap的很多方法以实现双向链表的功能。可以说，理解多态，再去理解LinkedHashMap原理会事半功倍；反之也是，对于LinkedHashMap原理的学习，也可以促进和加深对于多态的理解。

3. 一些重要点在LinkedHashMap上面的答案

LinkedHashMap

关注点	结论
集合底层实现的数据结构	数组(HashMap)+双链表
集合中元素是否允许为空	Key和Value都允许为空
是否允许重复的数据	Key会被覆盖，但是Value 允许重复
是否有序	有序(插入顺序与迭代顺序一致)
是否线程安全。	非线程安全

4.重要属性

前面我们已经知道了LinkedHashMap是继承自HashMap的，所以HashMap的属性，LinkedhashMap直接继承过来了，此外还有一些LinkedHashMap为了实现双链表新加的属性：

//header指针，指向双链表的头部
private transient Entry<K,V> header;
//accessOrder为true: 表示按照访问的顺序来，也就是谁最先访问，就排在第一位 
//accessOrder为false表示按照存放顺序来，就是你put元素的时候的顺序。
private final boolean accessOrder;

此外，因为要实现双向链表的特性，所以LinkedHashMap的Entry类也必须增加属性，源码如下：

private static class Entry<K,V> extends HashMap.Entry<K,V> {
//双链表的前驱和后继
    Entry<K,V> before, after;

//构造函数
    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
    }

/**
 * 从双向链表中删除该结点
 */
private void remove() {
        before.after = after;
        after.before = before;
    }

/**
 * Inserts this entry before the specified existing entry in the list.
 */
private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }

/**
 * This method is invoked by the superclass whenever the value
 * of a pre-existing entry is read by Map.get or modified by Map.set.
 * If the enclosing Map is access-ordered, it moves the entry
 * to the end of the list; otherwise, it does nothing.
 */
void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }

void recordRemoval(HashMap<K,V> m) {
        remove();
    }
}

列一下Entry里面有的一些属性吧：
1. K key
2. V value
3. Entry next;
4. int hash
5. Entry before//前驱
6. Entry after//后继
其中前面四个是从HashMap.Entry中继承过来的；后面两个是LinkedHashMap独有的。不要搞错了next和before、After：next是用于维护HashMap指定table[i]位置上连接的Entry的顺序的，before、After是用于维护Entry插入的先后顺序的。
还是用图表示一下，列一下属性而已：

LinkedHashMap的构造函数

该类最后都会调用LinkedHashMap(int initialCapacity, float loadFactor) 该方法来实现构造Map。可知里面主要是调用了父类HashMap的构造函数，只是多加了一个accessOrder = false; 设置Map的迭代顺序是按照插入的顺序。

public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
    accessOrder = false;
}

重要的方法：

在LinkedHashMap中由于多态的特性重写了很多方法，下面主要分析以下方法：

void addEntry(int hash, K key, V value, int bucketIndex)

void createEntry(int hash, K key, V value, int bucketIndex) 

public V get(Object key)

void init()

void transfer(HashMap.Entry[] newTable, boolean rehash)

init()方法

该方法被HashMap构造器调用，在hashMap中该方法是空函数体，由于在LinkedHashMap中被override重写了，所以初始化LInkedHashMap时调用的是LinkedHashMap中的init()方法。这就是典型的多态的应用。具体源码如下：

void init() {
    header = new Entry<>(-1, null, null, null);
    header.before = header.after = header;
}

里面也就做了一件事，初始化维护LinkedHashMap有序性的双向链表，即new了一个头结点，并让header指向这个头结点，这里这个头结点的key和value都是null，其next也是null。

addEntry(int hash, K key, V value, int bucketIndex)方法

我们发现在LinkedHashMap中并没有重写put()方法，说明LinkedHashMap的put()操作调用的HashMap中的put()方法，但是我们却发现，在HashMap中的put()方法中调用的addEntry(hash, key, value, i);方法在LinkedHashMap中被重写了，我们看看重写之后的源码：

void addEntry(int hash, K key, V value, int bucketIndex) {
//先调用HashMap中的addEntry()函数
    super.addEntry(hash, key, value, bucketIndex);

// Remove eldest entry if instructed
    Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    }
}

调用HashMap中的addEntry()函数中又在LinkedHashMap中重写了createEntry(int hash, K key, V value, int bucketIndex) ，在LinkedHashMap中如下：

void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    e.addBefore(header);
    size++;
}

函数中前三行和HashMap中没什么区别，区别在于多执行了一个
e.addBefore(header); 这个函数，这个函数主要在双向链表中是在header结点前面插入e结点，其实也就是在双向链表的尾部插入了新节点e。

/**
 * 在链表中指定结点existingEntry前面插入该实体this。
 */
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

2.get(Object key)

get()方法在LinkedHashMap中被重写了。

public V get(Object key) {
//1. 根据key获取到实体
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
    e.recordAccess(this);
return e.value;
}

其实该方法和hashMap中的几乎一模一样，唯一的区别在于增加了这么一句：
e.recordAccess(this);

void recordAccess(HashMap<K,V> m) {
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//将结点移动到双向链表的末尾
if (lm.accessOrder) {
        lm.modCount++;
        remove();
        addBefore(lm.header);
    }
}

在LinkedHashMap中，由于需要有顺序需要维护，因此，当accessOrder = true 时，则需要调用recordAccess(this)方法将此节点放到双向链表的末尾。而如果accessOrder = false.则完全与HashMap类中的get方法一模一样。

小结

LinkedHashMap 和hashMap 功能基本一样，都是维护的键值对集合，连遍历 以及方法都类似，唯一的区别在于HashMap 里面的元素是根据hash值来决定存放位置的，是无序的，而LinkedHashMap 维护的是一个按顺序存放的双向链表，是有序的。

因此，记住，他们的区别在于：LinkedHashMap是“数组和双向链表”的结合体，而HashMap是“数组和单向链表”的结合体就够了。

测试

@Test
public void testMap(){
//无序
Map<String, String> map = new HashMap<>();
map.put("1","1");
map.put("2","2");
map.put("3","3");
map.put("4","4");
map.put("5","5");

Set<Map.Entry<String,String>> set = map.entrySet();
    Iterator<Map.Entry<String,String>> it = set.iterator();

while (it.hasNext()){
        System.out.println(it.next());
    }

}

@Test
public void testMapLinked(){
//有序
Map<String, String> map = new LinkedHashMap<String,String>();
map.put("1","1");
map.put("2","2");
map.put("3","3");
map.put("4","4");
map.put("5","5");

Set<Map.Entry<String,String>> set = map.entrySet();
    Iterator<Map.Entry<String,String>> it = set.iterator();

while (it.hasNext()){
        System.out.println(it.next());
    }

}

结果：
HashMap:

LinkedHashMap