Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析
1.总结
1.LinkedHashMap继承自HashMap，所以HashMap有的特性LinkedHashMap都有，比如数据结构为数组+链表+红黑树，默认容量为16，负载因子为0.75等(HashMap源码分析)。
2.LinkedHashMap使用双向链表维持数据的插入顺序或访问顺序(默认是以插入顺序排序)。
3.当以访问顺序排序时，被访问的节点都要从当前位置移到链表尾部。
2.继承关系图
3.源码分析
3.1成员变量分析
// 双向链表的头结点
transient LinkedHashMap.Entry<K,V> head;
// 双向链表的尾结点
transient LinkedHashMap.Entry<K,V> tail;
// 排序方式，false：插入顺序；true：访问顺序
final boolean accessOrder;
3.2构造方法分析
/**
* 指定初始化容量和负载因子
* accessOrder：默认都为false，表示以插入顺序排序
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 指定初始化容量
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 默认构造
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 用已存在的map初始化LinkedHashMap
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder; // 指定是否以访问顺序排序
}
3.3常用方法分析
1.put方法
调用的就是HashMap的put方法，不同的是LinkedHashMap重写了newNode方法，实现了afterNodeAccess和afterNodeInsertion方法
/**
* 新建节点，新节点接在双向链表尾部
*/
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;
}
/**
* 将节点连接到链表尾部
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
// 将尾结点指向p
tail = p;
// 如果last为null，表示链表还没有建立
if (last == null)
head = p;
else {
// 将新节点接到链表尾部，新节点的前向指针指向last，last的后继指针指向新节点
p.before = last;
last.after = p;
}
}
再看看实现的两个方法：
- afterNodeAccess方法
void afterNodeAccess(Node<K,V> e) { // move node to last 将节点移到链表最后
LinkedHashMap.Entry<K,V> last;
// 当以访问顺序排序，且e不是尾结点时
if (accessOrder && (last = tail) != e) {
// p => e; b => p的前驱; a => p的后继
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null) // 表示p原先为头节点
// 将p移到链表尾部后，p的后继节点a成为头结点
head = a;
else
// 否则将b的后继指向a（此时p从链表中删除，将断开的链表重新连接起来）
b.after = a;
if (a != null)
// a不为null，则a的前驱指向b
a.before = b;
else
// 否则b成为最后一个节点
last = b;
if (last == null)
// 链表只有p节点，将头结点指向p
head = p;
else {
// 否则将p节点连接到链表尾部
p.before = last;
last.after = p;
}
// 尾结点指向p
tail = p;
++modCount;
}
}
- afterNodeInsertion方法
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;
}
从源码可以看到，需要同时满足三个条件才会才会进入if语句
1.evict为true
2.first不为null
3.removeEldestEntry(first)方法返回true
然而默认的removeEldestEntry(first)始终返回false，也就是说默认不会删除节点。removeEldestEntry(first)用于定义删除最老元素的规则。
2.get方法
public V get(Object key) {
Node<K,V> e;
// getNode()方法为查找节点的具体实现，在HashMap中已经分析过，这里不再说明
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果accessOrder为true，表示以访问顺序排序
if (accessOrder)
// 调整链表，将访问的节点移到链表尾部
afterNodeAccess(e);
return e.value;
}
3.remove方法
调用的就是HashMAp的remove方法，不同的是LinkedHashMap实现了afterNodeRemoval方法。
/**
* e：待删除节点
*/
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;
}
afterNodeRemoval()实现从双向链表中删除节点，并将断开的链表重新连接起来。
4.entrySet，keySet，values方法
entrySet，keySet，values与HashMap中的这三个方法大同小异，其中entrySet和keySet通过迭代器将键值对/键映射到entrySet和keySet上，values是一个Collection集合：
/**
* 跟HashMap的实现是一样的
*/
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new LinkedValues();
values = vs;
}
return vs;
}
