LinkedHashMap具有以下特性
- LinkedHashMap继承自HashMap, 它可以保证迭代的顺序跟插入的顺序是一致的
- 不是同步的，如果多个线程同时访问，需要从外部保持同步
- LinkedHashMap还可以按照访问顺序进行排序，如果是按照访问顺序，那么调用get以后，会将访问的元素移到链表末尾
LinkedHashMap的重要变量
/**
* 双向链表的表头
*/
private transient LinkedHashMapEntry<K,V> header;
/**
* true: 按照访问顺序; false: 按照插入顺序
*
* @serial
*/
private final boolean accessOrder;
LinkedHashMap是HashMap的子类，从而继承了HashMap中属性，另外LinkedHashMap自定义了两个变量，这两个变量也就是实现其排序的关键
1. init
init方法会在构造函数中调用，HashMap的init是一个空实现，LinkedHashMap重写了init方法
@Override
void init() {
header = new LinkedHashMapEntry<>(-1, null, null, null);
header.before = header.after = header;
}
init方法主要就是初始化了header变量，将header的beafore和after都指向header自身
2. put
LinkedHashMap没有重写put方法, 完全还是HashMap.put的逻辑
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
LinkedHashMap虽然没有重写put方法，但是其重写了两个关键方法recordAccess和addEntry, 其中recordAccess是用来记录访问顺序的方法，即更新当前entry的after,before
2.1 addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {
// removeEldestEntry(eldest)固定返回false..
LinkedHashMapEntry<K,V> eldest = header.after;
if (eldest != header) {
boolean removeEldest;
size++;
try {
removeEldest = removeEldestEntry(eldest);
} finally {
size--;
}
if (removeEldest) {
removeEntryForKey(eldest.key);
}
}
super.addEntry(hash, key, value, bucketIndex);
}
虽然在super.addEntry之前有一段逻辑，但是由于removeEldestEntry方法固定返回false，所以这一段代码执行与否都没有什么影响..., super.addEntry主要是为了执行扩容操作，HashMap.addEntry在扩容后会执行createEntry方法，而LinkedHashMap重写了createEntry方法
2.2 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;
//更新链表指针, 【2.3】
e.addBefore(header);
size++;
}
- 创建对应的Entry, 如果是要归属到同一个链表内的，将newEntry的next指针指向oldEntry, 将newEntry放置到相应的索引处
- 更新双向链表指针
2.3 LinkedHashMapEntry.addBefore
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
下面这张图显示了执行两次put操作后(假设没有hash冲突)的链表指向
3. get
public V get(Object key) {
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
}
3.1 LinkedHashMapEntry.recordAccess
void recordAccess(java.util.HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
//从双向链表中删除当前元素
remove();
//重新将元素添加到链表表头
addBefore(lm.header);
}
}
private void remove() {
before.after = after;
after.before = before;
}
如果是访问顺序进行排序,首先将当前entry从双向链表中删除，之后再重新添当前entry到表头
4.遍历
LinkedHashMap的遍历需要注意的事项跟HashMap的一致，不能在使用迭代器遍历的时候调用LinkedHashMap.remove()删除元素，其原理不变，仍然是使用expectedModCount
4.1 LinkedHashIterator.nextEntry
LinkedHashMapEntry<K,V> nextEntry = header.after;
LinkedHashMapEntry<K,V> lastReturned = null;
Map.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;
}
可以看到，迭代器迭代时，LinkedHashMap会从双向链表的header处开始向后按顺序遍历
