LinkedHashMap类似于HashMap
但是迭代遍历它时
取得
键值对
的顺序是插入次序
或者是最近最少使用（LRU）的次序
只比HashMap慢一点
而在迭代访问时反而更快
因为它使用链表维护内部次序（HashMap是基于散列表实现的
相关HashMap的内容可以看《Java集合类》和《HashMap源码分析》）
public class LinkedHashMap<KV> extends HashMap<KV> implements Map<KV>
LinkedHashMap继承自HashMap并实现了Map接口
LinkedHashMap只定义了两个属性
/**
* The head of the doubly linked list
* 双向链表的头节点
*/
private transient Entry<KV> header;
/**
* The iteration ordering method for this linked hash map: true
* for accessorder false for insertionorder
* true表示最近最少使用次序false表示插入顺序
*/
private final boolean accessOrder;
LinkedList一共提供了五个构造方法
// 构造方法构造一个指定初始容量和负载因子的按照插入顺序的LinkedList
public LinkedHashMap(int initialCapacity float loadFactor) {
super(initialCapacity loadFactor);
accessOrder = false;
}
// 构造方法构造一个指定初始容量的LinkedHashMap取得键值对的顺序是插入顺序
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
// 构造方法用默认的初始化容量和负载因子创建一个LinkedHashMap取得键值对的顺序是插入顺序
public LinkedHashMap() {
super();
accessOrder = false;
}
// 构造方法通过传入的map创建一个LinkedHashMap容量为默认容量（）和(mapzise()/DEFAULT_LOAD_FACTORY)+的较大者装载因子为默认值
public LinkedHashMap(Map<? extends K ? extends V> m) {
super(m);
accessOrder = false;
}
// 构造方法根据指定容量装载因子和键值对保持顺序创建一个LinkedHashMap
public LinkedHashMap(int initialCapacity
float loadFactor
boolean accessOrder) {
super(initialCapacity loadFactor);
thisaccessOrder = accessOrder;
}
从构造方法中可以看出默认都采用插入顺序来维持取出键值对的次序所有构造方法都是通过调用父类的构造方法来创建对象的
LinkedHashMap是基于双向链表的而且属性中定了一个header节点为什么构造方法都没有对其进行初始化呢？
注意LinkedHashMap中有一个init()方法 HashMap的构造方法都调用了init()方法这里LinkedHashMap的构造方法在调用父类构造方法后将从父类构造方法中调用init()方法（这也解释了为什么HashMap中会有一个没有内容的init()方法）
void init() {
header = new Entry<KV>( null null null);
headerbefore = headerafter = header;
}
看init()方法的确是对header进行了初始化并构造成一个双向循环链表（和LinkedList的存储结构是一样的）
transfer(HashMapEntry[] newTable)方法和init()方法一样也在HashTable中被调用transfer(HashMapEntry[] newTable)方法在HashMap调用resize(int newCapacity)方法的时候被调用
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTablelength;
for (Entry<KV> e = headerafter; e != header; e = eafter) {
int index = indexFor(ehash newCapacity);
enext = newTable[index];
newTable[index] = e;
}
}
根据链表节点e的哈希值计算e在新容量的table数组中的索引并将e插入到计算出的索引所引用的链表中
containsValue(Object value)
public boolean containsValue(Object value) {
// Overridden to take advantage of faster iterator
if (value==null) {
for (Entry e = headerafter; e != header; e = eafter)
if (evalue==null)
return true;
} else {
for (Entry e = headerafter; e != header; e = eafter)
if (valueequals(evalue))
return true;
}
return false;
}
重写父类的containsValue(Object value)方法直接通过header遍历链表判断是否有值和value相等而不用查询table数组
get(Object key)
public V get(Object key) {
Entry<KV> e = (Entry<KV>)getEntry(key);
if (e == null)
return null;
erecordAccess(this);
return evalue;
}
get(Object key)方法通过HashMap的getEntry(Object key)方法获取节点并返回该节点的value值获取节点如果为null则返回nullrecordAccess(HashMap<KV> m)是LinkedHashMap的内部类Entry的一个方法将在介绍Entry的时候进行详细的介绍
clear()
public void clear() {
superclear();
headerbefore = headerafter = header;
}
clear()方法先调用父类的方法clear()方法之后将链表的header节点的before和after引用都指向header自身即header节点就是一个双向循环链表这样就无法访问到原链表中剩余的其他节点他们都将被GC回收
以上的内容多多少少都涉及到了LinkedHashMap的内部类Entry<KV>下面详细介绍这个内部类
// 这是一个私有的静态的内部类继承自HashMap的Entry
private static class Entry<KV> extends HashMapEntry<KV> {
// 对前后节点的引用
Entry<KV> before after;
// 构造方法直接调用父类的构造方法
Entry(int hash K key V value HashMapEntry<KV> next) {
super(hash key value next);
}
// 移除该节点只需修改前一节点的after引用和后一节点的before引用
private void remove() {
// 修改后该节点服务再被访问会被GC回收
beforeafter = after;
afterbefore = before;
}
// 在指定节点之前插入当前节点（双向链表插入节点的过程）
private void addBefore(Entry<KV> existingEntry) {
// 将当前节点的after引用指向existingEntry
after = existingEntry;
// 将before的引用指向existingEntry节点的前一节点
before = existingEntrybefore;
// 将原先existingEntry节点的前一节点的after引用指向当前节点
beforeafter = this;
// 将原先existingEntry节点的后一节点的before引用指向当前节点
afterbefore = this;
}
// 当调用此类的get方法或put方法（put方法将调用到父类HashMapEntry的put
// 方法）都将调用到recordAccess(HashMap<KV> m)方法
// 如果accessOrder为true即使用的是最近最少使用的次序则将当前被修改的
// 节点移动到header节点之前即链表的尾部
// 这也是为什么在HashMapEntry中有一个空的
// recordAccess(HashMap<KV> m)方法的原因
void recordAccess(HashMap<KV> m) {
LinkedHashMap<KV> lm = (LinkedHashMap<KV>)m;
if (lmaccessOrder) {
lmmodCount++;
remove();
addBefore(lmheader);
}
}
// 和recordAccess(HashMap<KV> m)方法一样在HashMapEntry中同样有一个对应的空方法当进行删除（remove）操作的时候会被调用
void recordRemoval(HashMap<KV> m) {
remove();
}
}
介绍完了内部类Entry下面是创建一个Entry节点和添加一个Entry的两个方法
createEntry(int hashK keyV valueint bucketIndex)
void createEntry(int hash K key V value int bucketIndex) {
HashMapEntry<KV> old = table[bucketIndex];
Entry<KV> e = new Entry<KV>(hash key value old);
table[bucketIndex] = e;
eaddBefore(header);
size++;
}
createEntry(int hashK keyV valueint bucketIndex)方法覆盖了父类HashMap中的方法这个方法不会拓展table数组的大小该方法首先保留table中bucketIndex处的节点然后调用Entry的构造方法（将调用到父类HashMapEntry的构造方法）添加一个节点即将当前节点的next引用指向table[bucketIndex] 的节点之后调用的eaddBefore(header)是修改链表将e节点添加到header节点之前
该方法同时在table[bucketIndex]的链表中添加了节点也在LinkedHashMap自身的链表中添加了节点
addEntry(int hash K key V value int bucketIndex)
void addEntry(int hash K key V value int bucketIndex) {
createEntry(hash key value bucketIndex);
Entry<KV> eldest = headerafter;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldestkey);
} else {
if (size >= threshold)
resize( * tablelength);
}
}
首先调用createEntry(int hashK keyV valueint bucketIndex)方法之后获取LinkedHashMap中最老（最近最少使用）的节点接着涉及到了removeEldestEntry(Entry<KV> eldest)方法来看一下
protected boolean removeEldestEntry(MapEntry<KV> eldest) {
return false;
}
为什么这个方法始终返回false？
结合上面的addEntry(int hashK keyV valueint bucketIndex)方法这样设计可以使LinkedHashMap成为一个正常的Map不会去移除最老的节点
为什么不在代码中直接去除这部分逻辑而是设计成这样呢？
这为开发者提供了方便若希望将Map当做Cache来使用并且限制大小只需继承LinkedHashMap并重写removeEldestEntry(Entry<KV> eldest)方法像这样
private static final int MAX_ENTRIES = ;
protected boolean removeEldestEntry(MapEntry eldest) {
return size() > MAX_ENTRIES;
}
LinkedHashMap除了以上内容外还有和迭代相关的三个方法及三个内部类以及一个抽象内部类分别是newKeyIterator()newValueIterator()newEntryIterator()和KeyIterator类ValueIterator类EntryIterator类以及LinkedHashIterator类
三个new方法分别返回对应的三个类的实例而三个类都继承自抽象类LinkedHashIterator下面看迭代相关的三个类
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry()getKey(); }
}
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry()value; }
}
private class EntryIterator extends LinkedHashIterator<MapEntry<KV>> {
public MapEntry<KV> next() { return nextEntry(); }
}
从上面可以看出这三个类都很简单只有一个next()方法next()方法也只是去调用LinkedHashIterator类中相应的方法 和KeyIterator类ValueIterator类EntryIterator类以及LinkedHashIterator类
下面是LinkedHashIterator类的内容
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<KV> nextEntry = headerafter;
Entry<KV> lastReturned = null;
// 和LinkedList中ListItr类定义了expectedModCount用途一致
int expectedModCount = modCount;
// 下一个节点如果是header节点说明当前节点是链表的最后一个节点即已经遍历完链表了没有下一个节点了
public boolean hasNext() {
return nextEntry != header;
}
//移除上一次被返回的节点lastReturned
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMapthisremove(lastReturnedkey);
lastReturned = null;
expectedModCount = modCount;
}
// 返回下一个节点
Entry<KV> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
// 获取并记录返回的节点
Entry<KV> e = lastReturned = nextEntry;
// 保存对下一个节点的引用
nextEntry = eafter;
return e;
}
}
LinkedHashMap本应和HashMap及LinkedList一起分析比较他们的异同为了弥补这里简单的总结一些他们之间的异同
HashMap使用哈希表来存储数据并用拉链法来处理沖突LinkedHashMap继承自HashMap同时自身有一个链表使用链表存储数据不存在沖突LinkedList和LinkedHashMap一样使用一个双向循环链表但存储的是简单的数据并不是键值对所以HashMap和LinkedHashMap是Map而LinkedList是一个List这是他们本质的区别LinkedList和LinkedHashMap都可以维护内容的顺序但HashMap不维护顺序
