概述
在分析LinkedHashMap的源码之前先看一下LinkedHashMap的继承关系
LinkedHashMap继承关系
通过上述继承关系可以看到，LinkedHashMap继承自HashMap，也就是具有HashMap的所有功能，然后再看看源码中的注释：
- Hash table and linked list implementation of the Map interface,with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map. Note that insertion order is not affected if a key is re-inserted into the map.
- 一个实现了Map接口，并且可以知道迭代顺序的哈希表个链表。这个实现跟HashMap的区别在于它维持了一个连接所有Entry的链表。这个链表定义了迭代的顺序，默认的迭代顺序就是key被插入的顺序。注意如果一个key被重新插入是不会影响链表的插入顺序的。
从注释中可以了解到，LinkedHashMap自己维护了一个双向链表，确切地说是一个双向循环链表，下面看一下双向循环链表
- 双向循环链表的结构示意图
双向循环链表
- 双向循环链表的元素插入
双向循环链表表插入元素
正文
成员变量
private static final long serialVersionUID = 3801124242820219131L;
//双链表的头结点
private transient LinkedHashMapEntry<K,V> header;
//双链表的迭代顺序，true表示按照访问的顺序，false表示插入的顺序
private final boolean accessOrder;
LinkedHashMapEntry
private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
// before为指向上一个节点的指针，after为指向下一个节点的指针
LinkedHashMapEntry<K,V> before, after;
//构造方法
LinkedHashMapEntry(int hash, K key, V value, HashMapEntry<K,V> next) {
super(hash, key, value, next);
}
//删除某个节点，也就是将当前节点的前一个节点跟后一个节点连接在一起
private void remove() {
//将上一个节点的尾指针指向下个节点
before.after = after;
//将下一个节点的头指针指向上一个节点
after.before = before;
}
//在某个节点之前插入一个节点，结合上面你的示意图比较好理解
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
//将当前节点的after指针指向插图的节点
after = existingEntry;
//将当前节点的before指针指向existingEntry的上一个节点
before = existingEntry.before;
//before的尾节点指向当前节点
before.after = this;
//after的头结点指向当前节点
after.before = this;
}
//当一个已经存在的entry被get方法调用或者被set方法修改的时候此方法被父类(HashMap)调用，如果access-ordered为true，那么entry就会被移动到链表的尾部，否则不作处理。
void recordAccess(HashMap<K,V> m) {
//将HashMap强转成LinkedHashMap
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
//如果accessOrder为true
lm.modCount++;
//先移除此entry
remove();
//将lm添加到队尾
addBefore(lm.header);
}
}
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
构造方法
LinkedHashMap的构造方法其实就是间接调用了HashMap的构造方法，然后给迭代标志位accessOrder一个false，也就是默认按照插入的顺序进行排序，比较简单
空的构造方法
public LinkedHashMap() {
super();
accessOrder = false;
}
传入一个容量
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
传入一个容量跟负载因子
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
传入一个Map
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
get方法
public V get(Object key) {
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
//调用了get方法，就会将当前的entry放到链表的尾部，删除的时候就会最后删除
e.recordAccess(this);
return e.value;
}
put方法
通过查找发现LinkedHashMap并没有复写Get方法，只是复写了addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
//这个是Android做的一些修改，略微不同于Java的SDK
LinkedHashMapEntry<K,V> eldest = header.after;
if (eldest != header) {
boolean removeEldest;
size++;
try {
//判断是否移除最近最少使用的Entry
removeEldest = removeEldestEntry(eldest);
} finally {
size--;
}
if (removeEldest) {
//根据返回值是否移除最近最少使用的entry
removeEntryForKey(eldest.key);
}
}
//调用父类的addEntry
super.addEntry(hash, key, value, bucketIndex);
}
//removeEldestEntry的返回值总是false，这个需要根据实际情况来复写，默认不移除
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
containsValue
HashMap
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
HashMapEntry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (HashMapEntry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
private boolean containsNullValue() {
HashMapEntry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (HashMapEntry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}
LinkedHashMap
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
if (e.value==null)
return true;
} else {
for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}
仔细观察一下发现，LinkedHashMap用双链表自身的特性去遍历了整个链表，从而替换了HashMap中的循环遍历，这个是因为链表遍历的效率更高。
- HashMap底层是Entry数组，所以循环遍历效率高，通过下标可以直接拿到对应的元素
- LinkedHashMap底层是链表，无法通过下标拿到对应的元素，所以只能挨个遍历，效率较低，所以通过指针遍历效率会高一些
transfer方法:扩容
HashMap
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K, V> e : table) {
while (null != e) {
HashMapEntry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
LinkedHashMap
@Override
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (LinkedHashMapEntry<K,V> e = header.after; e != header; e = e.after) {
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
其实跟containsValue一样，用自身的链表特性进行迭代，提高效率
createEntry
插入一个元素，默认是插入到队列的尾部
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> old = table[bucketIndex];
LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
}
迭代
LinkedHashMap完全重写了HashMap的迭代器
LinkedHashIterator
private abstract class LinkedHashIterator<T> implements Iterator<T> {
//默认的下个entry指的是链表的第1个entry节点
LinkedHashMapEntry<K,V> nextEntry = header.after;
//上一次返回的entry，也就是当前节点
LinkedHashMapEntry<K,V> lastReturned = null;
//用来判断是否是多线程并发
int expectedModCount = modCount;
//是否还有下一个节点
public boolean hasNext() {
return nextEntry != header;
}
//移除掉某个entry节点
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//移除当前entry节点
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
LinkedHashMapEntry<K,V> e = lastReturned = nextEntry;
//返回当前节点的下一个节点
nextEntry = e.after;
return e;
}
}
KeyIterator
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
ValueIterator
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().getValue(); }
}
EntryIterator
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
}
Key,Value,Entry分别复写了next方法
到此为止，基本上已经分析完成了LinkedHashedMap源码的基本分析，主要还是需要对双向循环链表比较熟悉，它本身实际上也只是循环链表的一个实现类
总结
- LinkedHashMap继承自HashMap，非线程安全
- LinkedHashMap自己维护了一个双向循环链表，有一个head指针，通过将最近最少使用的元素放到队列的头部，新插入的以及经常使用的元素放到尾部来帮助实现LRU算法
- LinkedHashMap有一个排序的标志位accessOrder，默认为false，即按照插入的顺序进行排序，如果为true,就将该元素放到队列尾部
- 虽然LinkedHashMap并没有实现put方法，但是覆盖了addEntry方法，实际上并没有什么用
- LRU算法的实现也是利用了LinkedHashMap的accessOrder标志位，同时也必须复写removeEldestEntry方法，根据实际需求决定是否删除最近最少使用的元素。
