转载请声明出处：http://blog.csdn.net/qq_24692041/article/details/64904806
LinkedHashMap简介
LinkedHashMap继承了HashMap，所以，基本上HashMap有的属性和功能，它都有，只是在这个基础上维护了一个自己的双向循环链表，并且新维护了一个变量accessOrder，用于决定LinkedHashMap的排序方式。
上图就是LinkedHashMap的结构，其实就是在HashMap的基础上多维护了一个双向循环链表，这个链表的头结点不会存放数据，后面的节点中存放的是整个hash表中所有单链表中的节点的引用。在需要操作这些节点的时候，比如containsValue和transfer方法中，HashMap时通过循环hash数组table，得到这些节点的引用。在LinkedHashMap中直接通过迭代双向循环链表得到这些节点的引用，在性能上来说，速度会比HashMap有所提升。
LinkedHashMap可以用来实现LRU算法（这会在下面的源码中进行分析）。
LinkedHashMap同样是非线程安全的，只在单线程环境下使用。
LinkedHashMap源码剖析:
来看看源码：
public class LinkedHashMap<K, V>
extends HashMap<K, V>
implements Map<K, V> {
private static final long serialVersionUID = 3801124242820219131L;
/**
* 私有维护的一个双向循环链表的头结点，将所有的节点的引用都放在这个链表中
* 每次调用get和set方法的时候都会将当前操作的节点移动到该链表的尾部
* 保证操作顺序
*/
private transient LinkedHashMapEntry<K, V> header;
/**
* 代表着当前LinkedHashMap的排序方式
*如果为false，则按插入也即是put的时间排序
* 如果为true则根据取出也即是get的时间的排序
*
* @serial
*/
private final boolean accessOrder;
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and load factor.
*
* @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;
}
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and a default load factor (0.75).
*
* @param initialCapacity the initial capacity
* @throws IllegalArgumentException if the initial capacity is negative
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 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;
}
/**
* Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with
* the same mappings as the specified map. The <tt>LinkedHashMap</tt>
* instance is created with a default load factor (0.75) and an initial
* capacity sufficient to hold the mappings in the specified map.
*
* @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(m);
accessOrder = false;
}
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @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;
}
/**
* Called by superclass constructors and pseudoconstructors (clone,
* readObject) before any entries are inserted into the map. Initializes
* the chain.
*/
@Override
void init() {
header = new LinkedHashMapEntry<>(-1, null, null, null);
header.before = header.after = header;
}
/**
* 覆写父类父方法，在扩大hash数组的resize方法中调用，
* HashMap中通过循环hash数组，取出table中的链表，再取出链表中的节点进行复制。
* 这儿直接通过循环双向循环链表，得到节点的引用，通过引用操作该节点，进行复制。
* 性能上来说，不用去循环操作hash数组，而是迭代链表，速度上得到了提升。
*/
@Override
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
//迭代链表直接拿到节点的引用
for (LinkedHashMapEntry<K, V> e = header.after; e != header; e = e.after) {
/**
* 通过引用取得hash值，直接进行复制操作
*/
int index = indexFor(e.hash, newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
/**
* 覆写父类的该方法，跟父类的实现完全不一样，
* 因为自己维护了一个双向循环链表，将所有的节点的引用都放在了这个双向循环链表中
* 所以直接迭代双向循环链表，通过操作信用，得出是否包含当前查询的value
*/
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value == null) {
//遍历双向循环链表查找是否包含value为null的节点
for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
if (e.value == null)
return true;
} else {
//遍历双向循环链表查找是否包含该value值的节点
for (LinkedHashMapEntry e = header.after; e != header; e = e.after)
if (value.equals(e.value))
return true;
}
return false;
}
/**
* 重写HashMap的get方法，其实跟父类的get方法功能上是一样的
* 只不过是多调用了一下recordAccess方法，将当前操作的节点
* 移动到双向循环链表的尾部
*/
public V get(Object key) {
//调用父类中的方法，将key所在节点取出来
LinkedHashMapEntry<K, V> e = (LinkedHashMapEntry<K, V>) getEntry(key);
if (e == null)
return null;
//移动当前节点到双向循环链表的尾部
e.recordAccess(this);
return e.value;
}
/**
* 用于清空map集合
* 在调用HashMap中clear方法的基础上，对自己维护的双向循环链表操作
*/
public void clear() {
//调用父类的方法，清空map中的所有数据
super.clear();
//维护私有的双向循环链表，成为一个单一null节点
header.before = header.after = header;
}
/**
* 继承了父类中的HashMapEntry，增加了私有属性before，after，这个类不保存真正的节点数据，
* 只是将这些节点的引用保存，然后连成一个双向循环链表，用于保证LinkedHashMap的操作排序功能
*/
private static class LinkedHashMapEntry<K, V> extends HashMapEntry<K, V> {
// These fields comprise the doubly linked list used for iteration.
//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 = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
/**
* 当父类HashMap在调用get或者set方法来修改当前map的时候，就会调用这个方法，
* 将当前节点放到双向循环链表的尾部
*/
void recordAccess(HashMap<K, V> m) {
LinkedHashMap<K, V> lm = (LinkedHashMap<K, V>) m;
if (lm.accessOrder) {
lm.modCount++;
//如果当前链表中已经存在该节点，先将该节点移除掉
remove();
//在末尾将该节点不上，就相当于是将当前节点移动到了尾部
addBefore(lm.header);
}
}
/**
* 移除map中的元素的时候调用该方法，移除双向循环链表中的该节点
*
* @param m
*/
void recordRemoval(HashMap<K, V> m) {
remove();
}
}
private abstract class LinkedHashIterator<T> implements Iterator<T> {
LinkedHashMapEntry<K, V> nextEntry = header.after;
LinkedHashMapEntry<K, V> lastReturned = null;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return nextEntry != header;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
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;
}
}
private class KeyIterator extends LinkedHashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private class ValueIterator extends LinkedHashIterator<V> {
public V next() {
return nextEntry().getValue();
}
}
private class EntryIterator extends LinkedHashIterator<Map.Entry<K, V>> {
public Map.Entry<K, V> next() {
return nextEntry();
}
}
// These Overrides alter the behavior of superclass view iterator() methods
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K, V>> newEntryIterator() {
return new EntryIterator();
}
/**
* 覆写父类的方法，用于新增一个节点，跟父类不同的是，这儿会多调用一个removeEldestEntry方法
* 这个方法默认返回false，如果有跟Lru算法相同的需求的时候，就覆写该方法，实现内存过多的时候
* 删除很久没有被访问的元素
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
/**
* 通过算法，判断是否需要将当前链表中很久没有用的元素移除掉
* Lru的实现就是通过这种形式
*/
LinkedHashMapEntry<K, V> eldest = header.after;
if (eldest != header) {
boolean removeEldest;
size++;
try {
//覆写该方法，如果内存吃紧该方法返回true，就可以删除很久没有访问的数据
removeEldest = removeEldestEntry(eldest);
} finally {
size--;
}
//如果计算出来需要移除，就调用父类的方法将该节点数据移除
if (removeEldest) {
//该方法在HashMap中
removeEntryForKey(eldest.key);
}
}
//调用父类的方法新增一个节点
super.addEntry(hash, key, value, bucketIndex);
}
/**
* 返回链表中被访问时间最远的一个节点
*
* @hide
*/
public Map.Entry<K, V> eldest() {
Entry<K, V> eldest = header.after;
return eldest != header ? eldest : null;
}
/**
* 覆写父类的方法，创建一个新的节点，这儿比父类多做了一个操作
* 将新创建的节点放在链表的头部
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K, V> old = table[bucketIndex];
//创建出一个新的节点，LinkedHashMapEntry继承HashMapEntry，并调用了父类构造方法
LinkedHashMapEntry<K, V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
//将新建的节点放在链表的头部
e.addBefore(header);
size++;
}
......
}
好了，源码差不多搞完。现在我们对几个特殊的方法拿出来，做重点讲解。
addEntry：覆写父类方法，就只是比父类方法多调用了removeEldestEntry方法，这个方法的返回值决定了是否会删除掉当前集合
中被访问时间最久远的一个节点数据。这个方法默认返回false，如果有跟Lru算法相同的需求的时候，就覆写该方法，在内存紧张
的时候返回true，就可以删除很久没有被访问的元素.
/**
* 覆写父类的方法，用于新增一个节点，跟父类不同的是，这儿会多调用一个removeEldestEntry方法
* 这个方法默认返回false，如果有跟Lru算法相同的需求的时候，就覆写该方法，实现内存过多的时候
* 删除很久没有被访问的元素
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
/**
* 通过算法，判断是否需要将当前链表中很久没有用的元素移除掉
* Lru的实现就是通过这种形式
*/
LinkedHashMapEntry<K, V> eldest = header.after;
if (eldest != header) {
boolean removeEldest;
size++;
try {
//覆写该方法，如果内存吃紧该方法返回true，就可以删除很久没有访问的数据
removeEldest = removeEldestEntry(eldest);
} finally {
size--;
}
//如果计算出来需要移除，就调用父类的方法将该节点数据移除
if (removeEldest) {
//该方法在HashMap中
removeEntryForKey(eldest.key);
}
}
//调用父类的方法新增一个节点
super.addEntry(hash, key, value, bucketIndex);
}
createEntry：这个方法也是覆写父类的方法，这个方法中跟父类不一样的是，直接做了一个操作，无论accessOrder
是true还是false都直接调用addBefore方法将当前插入的节点，放到了循环链表的尾部。这样就保证了根据插入排序的特性。
/**
* 覆写父类的方法，创建一个新的节点，这儿比父类多做了一个操作
* 将新创建的节点放在链表的头部
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K, V> old = table[bucketIndex];
//创建出一个新的节点，LinkedHashMapEntry继承HashMapEntry，并调用了父类构造方法
LinkedHashMapEntry<K, V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
//将新建的节点放在链表的头部
e.addBefore(header);
size++;
}
LinkedHashMap并没有覆写HashMap的put方法，而是覆写了addEntry方法和createEntry方法。这两个方法是用于新增节点的。也就是说是在插入新的key值的时候才会调用，覆写这两个方法，就拓展了按插入排序的功能，并且为调用者留下了Lru算法写发的口。
get方法：这个方法覆写了父类的方法，在这个方法中调用了recordAccess方法，这个方法中会判断accessOrder是否为true，如
果为true，就会调用addBefore方法，将当前get操作的节点放到双向循环链表的尾部，保证了按操作排序的特性。如果为false
不做任何处理，依然保持put的时候的插入排序特性。
/**
* 重写HashMap的get方法，其实跟父类的get方法功能上是一样的
* 只不过是多调用了一下recordAccess方法，将当前操作的节点
* 移动到双向循环链表的尾部
*/
public V get(Object key) {
//调用父类中的方法，将key所在节点取出来
LinkedHashMapEntry<K, V> e = (LinkedHashMapEntry<K, V>) getEntry(key);
if (e == null)
return null;
//移动当前节点到双向循环链表的尾部
e.recordAccess(this);
return e.value;
}
eldest：该方法用于取出hearder的下一个节点，因为hearder是头结点，不会存放数据吗，所以他的下一个节点可以说是数据节点的头结点，因为在put的时
候会无条件将当前插入的节点放到双向循环链表的尾部，所以header.after 就是操作时间最久远的一个元素节点，并且通过配合removeEldestEntry方法实现
Lru算法的实现。
/**
* 返回链表中被访问时间最远的一个节点
*
* @hide
*/
public Map.Entry<K, V> eldest() {
Entry<K, V> eldest = header.after;
return eldest != header ? eldest : null;
}
打完收工，LinkedHashMap也就这么些东西了！其他的似乎没什么可将的。那这篇文章就到这儿结束了。