主要内容：
- LinkedHashMap数据结构
- 继承关系、关键属性、构造函数
- 插入、查找元素
- 扩容
- 迭代器
- 与HashMap比较
LinkedHashMap概述
- 有序的Map接口实现，有序指元素可以按照访问顺序或插入顺序迭代。内部维护了一个双向循环链表来实现有序。
- 非线程安全。
LinkedHashMap数据结构
因为LinkedHashMap继承HashMap，基本操作与HashMap相似，通过重写相关方法来实现自己的特性。LinkedHashMap底层还实现了一个双向循环链表，所以重新定义了数组中保存的Entry对象。
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;
}
/**
* 重写了HashMap 的recordAccess方法；
* 如果是按照访问顺序排序，将节点移到链表尾部(头节点之前)，否则不做操作
*/
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
/**
* LinkedHashMap中没有重写remove(Object key)方法，
* 重写了HashMap中的recordRemoval方法，在HashMap中为空方法
*/
void recordRemoval(HashMap<K,V> m) {
remove();
}
}
LinkedHashMap的Entry包含三个指针，前后元素的引用指向双向链表的连接外，还有next指针来解决hash冲突。recordAccess(HashMap<K,V> m)方法在LinkedHashMap的get方法以及继承HashMap 的put方法中调用，如果是按照访问顺序排序，将当前访问的节点放入链表尾部，所以最少访问的数据在链表头部。
源码分析
继承关系
LinkedHashMap继承关系.png
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
- 继承HashMap，基本操作与HashMap类似。
关键属性
//双向循环链表的头节点
private transient Entry<K,V> header;
//true表示按照访问顺序排序，false为按照插入顺序
private final boolean accessOrder;
构造函数
//使用指定的容量以及加载因子生成一个空的LinkedHashMap，默认按插入顺序排序
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//指定容量大小生成一个空的LinkedHashMap，默认负载因子0.75以及按照插入顺序排序
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//生成一个空的LinkedHashMap，默认容量大小16、负载因子0.75以及按照插入顺序排序
public LinkedHashMap() {
super();
accessOrder = false;
}
//根据指定的map生成一个新的LinkedHashMap，默认负载因子0.75以及按插入顺序排序
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super(m);
accessOrder = false;
}
//指定容量大小、负载因子以及排序顺序生成一个空的LinkedHashMap
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
所有构造方法都通过父类HashMap的构造函数来创建LinkedHashMap的。从这几个方法源码观察，发现没有初始化header的代码，那它又是从哪里初始化的？？观察HashMap 的构造函数可以发现有个没有实现的init()方法(这是钩子方法)，子类LinkedHashMap实现了这个方法初始化双向链表的头节点。
/**
* 覆盖HashMap的init方法，构造方法、readObject以及clone方法均有调用该方法
* 生成头节点并初始化双向循环链表
*/
@Override
void init() {
header = new Entry<>(-1, null, null, null);//hash值－1，key、value和下一个元素引用均为null
header.before = header.after = header;
}
插入
LinkedHashMap没有重写put方法，重写了addEntry和createEntry方法，且实现了Entry对象的recordAccess方法。
//创建节点插入到LinkedHashMap中。有必要的话删除最少访问的节点
void addEntry(int hash, K key, V value, int bucketIndex) {
super.addEntry(hash, key, value, bucketIndex);
Entry<K,V> eldest = header.after;//链表头部的第一个节点，即最少访问的节点或最先插入的节点
if (removeEldestEntry(eldest)) {//有必要的(如容量不够，这里默认为false)删除该节点
removeEntryForKey(eldest.key);
}
}
//创建节点，新键值对分别放在桶数组和链表尾部
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++;
}
可以继承LinkedHashMap，并重写removeEldestEntry方法自动删除链表最少访问的键值对或者最先插入的键值对，可以用来做缓存。
get方法
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);//若LinkedHashMap按访问顺序排序，将访问的当前节点移到链表尾部
return e.value;
}
扩容
LinkedHashMap没有重写resize方法，重写了HashMap的transfer方法。
//获取对象采用遍历双向循环链表的方式，而不是原先的双重循环，性能更优
@Override
void transfer(HashMap.Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//遍历旧map的键值对
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;
}
}
迭代器
LinkedHashMap自定义迭代器，通过遍历双向循环链表来完成迭代，遍历时间与键值对个数成正比。
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
int expectedModCount = modCount;//fail-fast机制
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> {//key迭代器
public K next() { return nextEntry().getKey(); }
}
private class ValueIterator extends LinkedHashIterator<V> {//value迭代器
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(); }
与HashMap比较
- 相同：都是散列表的实现；继承自HashMap，具有大部分它的特性。
- 不同：LinkedListMap内部维护了一个双向循环链表，可以按照访问顺序LRU或插入顺序排序，迭代操作是遍历hash表，而是遍历双向循环链表。LinkedHashMap=HashMap+循环链表。
网友评论