LinkedHashMap

具有顺序的LinkedHashMap底层是继承于HashMap实现的,由一个双向链表所构成。

LinkedHashMap的排序方式有两种:

  • 根据写入顺序排序。
  • 根据访问顺序排序。

其中根据访问顺序排序时,每次get都会将访问的值移动到链表末尾,这样重复操作就能得到一个按照访问顺序排序的链表。

数据结构

private transient Entry<K,V> header; // 是这个双向链表的头结点
private final boolean accessOrder; // 默认按照插入顺序排序,为 true 时按照访问顺序排序
 
private static class Entry<K,V> extends HashMap.Entry<K,V> {
	// These fields comprise the doubly linked list used for iteration.
	Entry<K,V> before, after;

	Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
		super(hash, key, value, next);
	}
	...
}

其中Entry继承于HashMapEntry,并新增了上下节点的指针,也就形成了双向链表。利用了头节点和其余的各个节点之间通过Entry中的afterbefore指针进行关联。

https://www.wailian.work/images/2018/10/19/LinkedHashMap-min.jpgLinkedHashMap-min

https://s1.wailian.download/2019/12/31/LinkedHashMap2-min.pngLinkedHashMap2

构造方法

LinkedHashMap的构造方法:

public LinkedHashMap() {
	super();
	accessOrder = false;
}

HashMap实现:

public HashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;
	if (loadFactor <= 0 || Float.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
	this.loadFactor = loadFactor;
	threshold = initialCapacity;
	init();
}

init()LinkedHashMap来实现:

// 对 header 进行了初始化。
void init() {
	header = new Entry<>(-1, null, null, null);
	header.before = header.after = header;
}

put 方法

主体的实现都是借助于HashMap来完成的,只是对其中的recordAccess(),addEntry(),createEntry()进行了重写。LinkedHashMap的实现:

// 就是判断是否是根据访问顺序排序,如果是则需要将当前这个 Entry 移动到链表的末尾
void recordAccess(HashMap<K,V> m) {
	LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
	if (lm.accessOrder) {
		lm.modCount++;
		remove();
		addBefore(lm.header);
	}
}
// 调用了 HashMap 的实现,并判断是否需要删除最少使用的 Entry(默认不删除)
void addEntry(int hash, K key, V value, int bucketIndex) {
	super.addEntry(hash, key, value, bucketIndex);

	// Remove eldest entry if instructed
	Entry<K,V> eldest = header.after;
	if (removeEldestEntry(eldest)) {
		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);
	// 就多了这一步,将新增的 Entry 加入到 header 双向链表中
	table[bucketIndex] = e;
	e.addBefore(header);
	size++;
}
// 写入到双向链表中
private void addBefore(Entry<K,V> existingEntry) {
	after  = existingEntry;
	before = existingEntry.before;
	before.after = this;
	after.before = this;
}

get 方法

public V get(Object key) {
	Entry<K,V> e = (Entry<K,V>)getEntry(key);
	if (e == null)
		return null;
	e.recordAccess(this);
	return e.value;
}
void recordAccess(HashMap<K,V> m) {
	LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
	if (lm.accessOrder) {
		lm.modCount++;
		remove();
		addBefore(lm.header);
	}
}

clear()清空:

// 只需要把指针都指向自己即可,原本那些 Entry 没有引用之后就会被 JVM 自动回收。
public void clear() {
	super.clear();
	header.before = header.after = header;
}

示例

  • LinkedHashMapTestLinkedHashMapDemo

总结

总的来说LinkedHashMap其实就是对HashMap进行了拓展,使用了双向链表来保证顺序性。