1. 概述

LinkedHashMap还是比较简单的, 相对于HashMap, 它是有序的, 那么问题就来了, 它是怎么保持有序的? 它直接继承于HashMap, 重写或增加了一些新的关于保持Map有序的方法, 至于扩容或是数据结构等都于HashMap一样, 下面我们重点分析它是怎么保持有序的这问题.

此外, LinkedHashMap还提供了按照最近访问有序还是按照插入顺序有序(属性: accessOrder), 默认为false(插入顺序有序), 可以通过LinkedHashMap的构造方法将其改为true(最近访问有序).

2. 如何保证有序(敲黑板了)

想要保证有序, 那么元素之间就得有关系, 比如LinkedList, LinkedHashMap的思想也是同理, 只不过它在保证HashMap的数据结构下, 增加了元素之间的联系.

它通过以下几点保证了有序:

扩展了HashMap的Node内部类, 增加了before,after两个属性
重写了newNode方法
重写了HashMap中的三个回调方法

2-1. 扩展了HashMap的Node内部类

static class Entry<K,V> extends HashMap.Node<K,V> {
	Entry<K,V> before, after;
	Entry(int hash, K key, V value, Node<K,V> next) {
		super(hash, key, value, next);
	}
}

增加了两个属性, 使用这两个属性可以保持元素之间的关系.

有一个问题就是我们重写了HashMap的Node类, 那么HashMap在链表转为树的时候会不会出现类转换异常呢?

答案就在HashMap的TreeNode类上, 它继承了LinkedHashMap.Entry, 所以No problem.

2-2. 重写了newNode和newTreeNode方法

在HashMap的putVal方法中, 新增元素必然需要创建节点, 这里重写了HashMap的newNode方法, 并且调用了内部方法(linkNodeLast), 来维护新增元素与原集合中最后一个元素的关系.

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {

	// 创建新节点
	LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
	
	// 建立新节点与原集合中的最后一个节点之间的关系
	linkNodeLast(p);
	return p;
}

// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
	
	// 获取最后一个元素
	LinkedHashMap.Entry<K,V> last = tail;
	
	// 令最后一个元素为新元素
	tail = p;
	
	// 如果最后一个元素为null(p为集合中第一个节点)
	if (last == null) {
		// head也为p
		head = p;
	} else {
		// 使p的上一个元素为原集合中的最后一个元素
		p.before = last;
		
		// 原集合中最后一个元素的下一个元素为p
		last.after = p;
	}
}

是不是So Easy, 就是维护链表之间的关系.

2-3. 重写了HashMap中的三个回调方法

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

通过注释得知, 这方法的定义是为了让LinkedHashMap进行回调使用的.

这三个方法综合来说, 就是为了维护在发生元素的变动时, 对他们之间的关系进行维护.

2-3-1. afterNodeAccess

目的是将最后访问的元素移动到last, 注意: 只是改变Node之间的连接关系, 并不会改变元素的位置.

通过方法名可知, 这是在元素进行访问之后进行调用的.

源码如下:

void afterNodeAccess(Node<K,V> e) { // move node to last

	LinkedHashMap.Entry<K,V> last;
	
	// accessOrder默认是false, 可以通过构造方法进行设置为true.
	// 并且当前访问的元素不是last
	if (accessOrder && (last = tail) != e) {
	
		// 获取当前元素, 其前驱以及其后继
		LinkedHashMap.Entry<K,V> p =
			(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
			
		// 因为要把当前元素置为last, 所以它的after为null.
		p.after = null;
		
		// 当前元素没有前驱, 所以head为它的后继
		if (b == null)
			head = a;
		else  // 否则, 其前驱的after为其后继
			b.after = a;
			
		// 后继不为null的话, 后继的前驱即是其前驱.
		if (a != null)
			a.before = b;
		else // 既然 (last = tail) != e 成立了, 那么这里的a应该不会出现为null的情况.
			last = b;
			
		// 
		if (last == null)
			head = p;
		else {
			// 将 last 和 p 进行互换
			p.before = last;
			last.after = p;
		}
		
		// 令tail为p, 最后访问的元素
		tail = p;
		++modCount;
	}
}

2-3-2. afterNodeInsertion

这里是在put元素之后发生的调用, 似乎永远不会进行处理.

源码如下:

void afterNodeInsertion(boolean evict) { // possibly remove eldest
	LinkedHashMap.Entry<K,V> first;
	if (evict && (first = head) != null && removeEldestEntry(first)) {
		K key = first.key;
		removeNode(hash(key), key, null, false, true);
	}
}

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
	return false;
}

通过源码发现, removeEldestEntry这个方法永远返回false, 所以条件永远不会成立, 所以nothing.

2-3-3. afterNodeRemoval

在元素被移除之后发生的调用.

源码如下:

void afterNodeRemoval(Node<K,V> e) { // unlink
	LinkedHashMap.Entry<K,V> p =
		(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
	p.before = p.after = null;
	if (b == null)
		head = a;
	else
		b.after = a;
	if (a == null)
		tail = b;
	else
		a.before = b;
}

就是将其前驱的后继指向其后继, 将其后继的前驱指向为其前驱.

3. 遍历

HashMap的遍历思想和LinkedHashMap的遍历思想是不同的.

3-1. HashMap的遍历思想

在数组上从0下标开始遍历, 如果是null, 则+1, 去下一个位置查找元素; 如果不是null, 返回该元素, 然后如果该位置有链表或者红黑树时, 会进入到链表或者红黑树中查找元素返回.

3-2. LinkedHashMap的遍历思想

从head开始遍历, 也就是头结点元素, 通过元素之间的关系, 一直遍历到尾结点tail.

显然是链表的思想.

4. 总结

LinkedHashMap是对HashMap的扩展, 增加有序的实现.
提供插入顺序排序和最近访问排序