Introduction
LinkedHashMap 继承了 HashMap 与HashMap不同的是,它维护一个贯穿所有entries的双向链表,这个双向链表定义了迭代顺序(通常是key插入到map的顺序)。
有序:此实现使客户免于HashMap和Hashtable提供的未指定的,通常混乱的排序,而不会增加与treeMap相关的成本。他可以被用来制造一个map的副本,这个副本和原来的map顺序相同,不管这个map是如何实现的。这种技术在客户端传入map进行处理,并且希望返回结果有同样的顺序的时候非常有用。
1
2
3
4void fool(Map m){
Map copy = new LinkedHashMap(m);
...
}此实现有一个特殊的构造函数
LinkedHashMap(int,float,boolean)
,通过指定accessOrder
的值可以获得两种维护链表顺序的方式.accessOrder=true
按照最近访问来维护顺序,非常适合用于构建LRU caches。accessOrder=false
按照最近插入来维护顺序.
性能: 此实现提供map接口的所有功能,不允许null元素。和HashMap一样,它提供O(1)复杂度的基本操作:
add()
,contains()
,remove()
,假设hash函数将元素均匀的分布于buckets内。由于维护链表增加了额外的开销,性能轻微比HashMap更差;但是LinkedHashMap的迭代时间只与map的size有关,与capacity无关,相比之下HashMap更加昂贵,它的迭代时间与capacity有关。参数:初始容量 和负载系数。 它们的定义与 HashMap完全相同。 但是,与HashMap相比,此类为初始容量选择过高的值的惩罚不那么严重,因为此类的迭代时间不受容量的影响。
安全: 此实现非线程安全,需要在外部进行同步。通常通过对封装这个map的对象进行同步来实现,也可以使用
Collections.synchronizedMap
来包装,使得在创建时就避免的非同步的操作。1
Map m = Collections.synchronizedMap(new LinkedHashMap(...));
Important Variables
1
2
3
4
5
6
7
8
9
10
11
12
13// 链表头,更老的元素
transient LinkedHashMap.Entry<K,V> head;
// 链表尾,更新的元素
transient LinkedHashMap.Entry<K,V> tail;
// true:获取顺序,false:插入顺序
final boolean accessOrder;
// 继承,并增加节点的链表特性
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);
}
}Main Methods
由于继承了HashMap,LinkedHashMap并未直接实现put等接口方法,而是通过实现在HashMap里边定义回调(多态)来实现。
get()
get调用在hashMap中实现的getNode
实现.1
2
3
4
5
6
7
8public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}put()
put时,如果存在entry与put的对象相同,这时在HashMap实现的put中回调afterNodeAccess
用来将最近访问的节点移动到链表的最后.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 去除p向后的链接;
p.after = null;
if (b == null)
head = a; // p是头节点,指定a为头节点
else
b.after = a;
if (a != null)
a.before = b;
else
last = b; // last表示未来的倒数第二个节点,a为null,则指向b;否则用原来的tail
if (last == null) // 只有一种情况,p既是head又是tail,a和b都为null
head = p;
else {
p.before = last;
last.after = p;
}
// 设置p为尾节点
tail = p;
++modCount;
}
}需要注意的是,如果一个key被重复插入到map,插入顺序不会受到影响,在这种个情况
linkedHashMap
利用了afterNodeAccess
进行HashMap
处理完之后的处理,在这个方法中,并未对插入顺序进行调整。1
2
3
4
5
6
7
8
9
10// evict=false, table 处于创建模式.
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// removeEldestEntry 提供对外接口
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 调用hashMap中实现的方法
removeNode(hash(key), key, null, false, true);
}
}remove()
remove接口回调了 afterNodeRemoval 实现删除hash表中entry之后链表对应的处理.1
2
3
4
5
6
7
8
9
10
11
12
13
14void afterNodeRemoval(Node<K,V> e) {
// 获取前后的节点
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;
}除此之外还有多个方法,主要是通过
hashMap
中的函数回调,在LinkedHashMap
主要对hash表修改之后的链表进行维护.Demo
public static void main(String[] args) { // 修改第三个参数,进行试验 Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true); map.put("1", "a"); map.put("2", "b"); map.put("3", "c"); map.put("4", "e"); for (String name : map.values()) { System.out.print(name);
若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏
扫描二维码,分享此文章