# JDK源码-常用Collection
# LinkedList
LinkedList同时实现了List和Deque两个接口,考虑到底层用链表实现,因此插入效率高,随机查询效率低。
LinkedList底层为双向链表,每个节点为Node对象,内部分别有Prev和Next两个指针指向前后节点
# LinkedHashMap
LinkedHashMap
是HashMap
的子类,这意味着其也是基于Node数组进行存储,在根据Key进行查找时,同样基于key的hash值进行寻址。
但是两者不同的是LinkedHashMap
的Node节点进行了改造,除了保存key-value信息外,还保存了两个指针before和after,分别指向序列前后两个Node,整体结构如下:
默认情况下,before和after指针串联的列表维持对象放入的顺序,但是可以通过下面的构造器,在构造LinkedHashMap时指定参数accessOrder=true
,来使这个顺序变为访问顺序:
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
1
2
3
4
5
6
2
3
4
5
6
原理是在每次调用get(key)
及相关方法时,调整顺序
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e); // <-- 这里调整顺序
return e.value;
}
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
通过上述特性可以快速构造LRU缓存