LinkedHashMap继承自HashMap,除了提供HashMap的功能外,LinkedHashMap还是维护一个双向链表(实际为带头结点的双向循环链表),持有所有的键值对的引用:
- 这个双向链表定义了迭代器的迭代顺序，默认按
插入顺序迭代; - 也可以在构造时设置为按照
LRU方式(访问顺序)迭代(from least-recently accessed to most-recently access-order),最近最少访问的键值对放在链表最前(头结点之后的第一个结点);
废话不多说,直接看源码:
// @since 1.4
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
private static final long serialVersionUID = 3801124242820219131L;
// 双向循环链表的头结点
private transient Entry<K,V> header;
// 迭代的顺序,按访问顺序(access-order)时为true,按插入顺序(insertion-order)时为false
private final boolean accessOrder;
public LinkedHashMap(int initialCapacity,float loadFactor){
super(initialCapacity,loadFactor);
// 默认为按插入顺序
accessOrder = false;
}
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder){
super(initialCapacity,loadFactor);
this.accessOrder = accessOrder;
}
// 各种构造方法,省略...
// 构造器和伪构造器(包括clone(),readObject())中会调用该方法
void init(){
// 头结点
header = new Entry<>(-1,null,null,null);
header.before = header.after = header;
}
// 扩容时会调用该方法
void transfer(HashMap.Entry[] newTable,boolean rehash){
int newCapacity = newTable.length;
// 这里通过链表遍历,重新计算每个的hash值,而不是遍历hash表;
// 在扩容时,链表并没有发生变化;
for(Entry<K,V> e = header.after;e != header;e = e.after){
if(rehash){
e.hash = (e.key == null) ? 0 : hash(e.key);
}
int index = indexFor(e.hash,newCapacity);
e.next = newTable[index];
newTable[index] = e;
}
}
// 通过链表来查找是否存在指定元素,这样更快一点
public boolean containsValue(Object value){
if(value == null){
for(Entry e = header.after;e != header;e = e.after)
if(e.value == null){
return true;
}
}else{
for(Entry e = header.after;e != header;e = e.after)
if(value.equals(e.value)){
return true;
}
}
return false;
}
public V get(Object key){
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if(e == null){
return null;
}
// 被访问的entry,在链表中排序
e.recordAccess(this);
return e.value;
}
// 清除所有元素时,也要将所有的entry从链表中删除,不再持有这些entry的引用
public void clear(){
super.clear();
header.before = header.after = header;
}
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;
}
// 在双向链表中指定结点之前插入当前结点
private void addBefore(Entry<K,V> existingEntry){
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
// 当map中的一个已有的entry的值被访问(get())或修改(put()修改已有key的value)时被调用
void recordAccess(HashMap<K,V> m){
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果LinkedHashMao是按访问顺序,这里会将被修改的entry移到链表最后面(头结点的前面);
// 否则什么都不干;
// 也就是最近被访问的,放在链表的最后;最近最少访问的(LRU),放在链表最前;
if(lm.accessOrder){
lm.modCount++;
remove();
addBefore(lm.header);
}
}
// 当前entry被从map中移除时被调用,在这里将当前结点从双向链表中移除
void recordRemoval(HashMap<K,V> m){
remove();
}
}
private abstract class LinkedHashIterator<T> implements Iterator<T>{
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
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();
}
Entry<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().value; }
}
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>>{
public Map.Entry<K,V> next(){ return nextEntry(); }
}
Iterator<K> newKeyIterator(){ return new KeyIterator(); }
Iterator<V> newValueIterator(){ return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator(){ return new EntryIterator(); }
// put()会调用该方法
void addEntry(int hash,K key,V value,int bucketIndex){
super.addEntry(hash,key,value,bucketIndex);
Entry<K,V> eldest = header.after;
// 判断是否移除"最老"的元素;可以通过修改removeEldestEntry()的返回值来改变这一特性
// 默认不移除
if(removeEldestEntry(eldest)){
removeEntryForKey(eldest.key);
}
}
// put()中的addEntry()会调用该方法,将添加的entry放到链表尾
// 不管是按什么顺序(accessOrder),添加一个新entry时,都会将添加的entry放到链表尾,
// 因为新添加的entry即是最后插入的,也是是最近访问的
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++;
}
// 如果希望每次put()时,移除"最老"的结点,返回true,默认返回false
// "最老"的结点:如果为访问顺序,则为最久没被访问的结点;如果为插入顺序,则为最早被添加的元素;
protected boolean removeEldestEntry(Map.Entry<K,V> eldest){
return false;
}
}
有上述源码可以看出,LinkedHashMap在HashMap的基础上,添加了如下特点:
- 插入的元素保持有序,使得遍历时是有序的;且这种顺序可以按照需要,配置为如下2种之一:
-
按
访问顺序:最近最少访问的在最前,最近访问的元素在最后; -
按
插入顺序:最早插入的元素在最前,最后添加的元素在最后;默认为按
插入顺序;
- 因为可以按照
访问顺序有序,所以可以用来支持LRU算法; - 可配置删除
最老的结点,在每次添加结点的时候,判断是否将链表最前的结点删除;