上两篇文章
http://www.jianshu.com/p/a122c79ee60c
http://www.jianshu.com/p/336b1b45d140
我们讲了HashMap的实现原理，今天我们来讲讲HashMap的子类LinkedHashMap的内部实现。
构造方法
因为它是HashMap的子类，所以他们的存储都是数组形式，不同的是它添加了一个排序的参数accessOrder，这个参数对后面的方法实现都会有影响，可以通过构造方法给它赋值
public LinkedHashMap(
int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
init();
this.accessOrder = accessOrder;
}
initialCapacity默认数组的大小；loadFactor是加载因子，默认是0.75，我们添加数据的数量大于这个加载因子loadFactor时就会扩充数组的大小；accessOrder就是排序。
put方法
因为它是HashMap的子类，所以它的put方法和HashMap的put方法一样，唯一不同的是它重写了put方法当中的（put方法的解析可以看我文章开头链接）addNewEntry方法和preModify方法，我们先来看看addNewEntry方法
@Override
void addNewEntry(K key, V value, int hash, int index) {
//LinkedHashMap内部维护了一个双向链表, header是链表的头
LinkedEntry<K, V> header = this.header;
// 如果LinkedHashMap有数据，并且removeEldestEntry方法返回true，
// 就移除掉最早添加的数据, removeEldestEntry默认返回false
LinkedEntry<K, V> eldest = header.nxt;
if (eldest != header && removeEldestEntry(eldest)) {
remove(eldest.key);
}
// new一个LinkedEntry对象，最后面的两个参数一个是这个对象的上一个属性值，
// 一个是下一个属性值，table[index]对象是维护它在数组当中的单向链表值
LinkedEntry<K, V> oldTail = header.prv;
LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
key, value, hash, table[index], header, oldTail);
table[index] = oldTail.nxt = header.prv = newTail;
}
从上面方法可以得出结论：LinkedHashMap维持了HashMap原来的数据结构，并且添加了一个双向链表，所以LinkedHashMap是有序的，在put数据的同时可以通过removeEldestEntry方法来决定是否删除最早添加的数据。
我们再来看看preModify方法，preModify方法是在有重复key的时候会调用
@Override
void preModify(HashMapEntry<K, V> e) {
//如果为true就执行makeTail方法
if (accessOrder) {
makeTail((LinkedEntry<K, V>) e);
}
}
private void makeTail(LinkedEntry<K, V> e) {
// e是那个重复key的 对象
//就是把链表当中的e对象删除掉，然后让e的上一个和下一个对象通过链表的形式关联起来
e.prv.nxt = e.nxt;
e.nxt.prv = e.prv;
// 然后把e添加到最后
LinkedEntry<K, V> header = this.header;
LinkedEntry<K, V> oldTail = header.prv;
e.nxt = header;
e.prv = oldTail;
oldTail.nxt = header.prv = e;
modCount++;
}
从上面的方法可以得出结论：如果有重复的key并且accessOrder是true，就会把重复key的对象移动到最后；put方法到此就解析完了，下面来看看get方法
@Override
public V get(Object key) {
/*
* This method is overridden to eliminate the need for a polymorphic
* invocation in superclass at the expense of code duplication.
*/
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null)
return null;
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
if (accessOrder)
makeTail((LinkedEntry<K, V>) e);
return e.value;
}
}
return null;
}
上面的逻辑很容易理解，就是说如果accessOrder为true就执行makeTail方法，makeTail方法上面已经分析过了，从上面代码可以得出结论：如果在我取值的时候accessOrder为true，那么就会把我取的这个值移动到链表的最后，header的上面。
代码验证
首先来验证一下遇到重复key，accessOrder不同值的情况
LinkedHashMap linkedHashMap = new LinkedHashMap(16 , 0.75f, false);
linkedHashMap.put("1", "one");
linkedHashMap.put("2", "two");
linkedHashMap.put("3", "three");
linkedHashMap.put("4", "four");
linkedHashMap.put("1", "one");
Iterator iter = linkedHashMap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println("IndexActivity Value:" + entry.getValue());
}
首先设置accessOrder为false，看看打印结果
IndexActivity Value:one
IndexActivity Value:two
IndexActivity Value:three
IndexActivity Value:four
因为accessOrder为false，所以在key重复的时候只会修改它的value，并不会移动它的位置，那设置为true会是什么结果呢？我们来看看打印结果
IndexActivity Value:two
IndexActivity Value:three
IndexActivity Value:four
IndexActivity Value:one
因为key=1重复并且accessOrder为true，所以会把key=1的这个对象移动到链表的最后。
下面来验证一下accessOrder不同值get操作的情况
LinkedHashMap linkedHashMap = new LinkedHashMap(16 , 0.75f, false);
linkedHashMap.put("1", "one");
linkedHashMap.put("2", "two");
linkedHashMap.put("3", "three");
linkedHashMap.put("4", "four");
linkedHashMap.get("3");
Iterator iter = linkedHashMap.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println("IndexActivity Value:" + entry.getValue());
}
首先设置accessOrder为false，看看打印结果
IndexActivity Value:one
IndexActivity Value:two
IndexActivity Value:three
IndexActivity Value:four
还是原来的顺序，下面我们设置accessOrder为true，再看看打印结果
IndexActivity Value:one
IndexActivity Value:two
IndexActivity Value:four
IndexActivity Value:three
可以看到three被移动到了最后面。
remove方法
remove方法和hashMap的remove方法一样(remove方法的解析可以查看我文章开头的链接)，区别在于重写了remove方法当中的postRemove方法
@Override
void postRemove(HashMapEntry<K, V> e) {
LinkedEntry<K, V> le = (LinkedEntry<K, V>) e;
//把e对象的上个对象和下个对象用链表的形式关联起来
le.prv.nxt = le.nxt;
le.nxt.prv = le.prv;
//把e对象指向上个对象和下个对象的属性设置为null
le.nxt = le.prv = null; // Help the GC (for performance)
}
到此LinkedHashMap的常用方法就分析完成了，其他的方法大家可以去看源码，都很容易理解的。
总结
从上面的方法可以看出：LinkedHashMap和HashMap区别就是多了个双向链表，它是有序的，可以通过get方法改变它的顺序（前提是accessOrder=true），在put数据的同时通过removeEldestEntry方法返回的值来决定是否移除数组第一位的数据。
