LinkedHashMap源码分析
2021-10-01 本文已影响0人
gcno93
简单描述
LinkedHashMap实现了Map接口，是HashMap的直接子类，即允许放入key为null的元素，也允许插入value为null。
采用双向链表(doubly-linked list)的形式将所有entry连接起来 ,这样是为保证元素的迭代顺序跟插入顺序相同。
初始化跟map差不多，实际上就是为了初始化化父类hashmap 初始化初始容量(inital capacity)和负载系数(load factor)，初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。
内部维护了一个双向链表(定义了head，tail)，迭代LinkedHashMap时不需要像HashMap那样遍历整个table，而只需要直接遍历header指向的双向链表即可。
hashCode()方法决定了对象会被放到哪个bucket里，当多个对象的哈希值冲突时，equals()方法决定了这些对象是否是“同一个对象。
主要的属性
transient LinkedHashMap.Entry<K,V> head; //链表头
transient LinkedHashMap.Entry<K,V> tail;//链表尾
构造函数
public LinkedHashMap() {
super();
accessOrder = false;
}
//super()
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
// super(initialCapacity);
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//accessOrder—排序模式—访问顺序为true，插入顺序为false
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//super(initialCapacity, loadFactor)
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;
this.threshold = tableSizeFor(initialCapacity);
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
Entry元素
//Entry 添加了before, after;进行记录链表，此外hashmap的TreeEntry 继承了此Entry
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);
}
}
迭代
LinkedMap 跟HashMap的遍历不一样，因为LinkedMap维护了自己的一个链表，所以，可以很轻松的进行迭代，而不会像HashMap那样，先遍历table,再遍历链表，或者红黑树
//LinkedMap
public void forEach(BiConsumer<? super K, ? super V> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
//LinkedMap 直接遍历内置的head（链表） 即可完成遍历
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e.key, e.value);
if (modCount != mc)
throw new ConcurrentModificationException();
}
//hashmap的
public void forEach(BiConsumer<? super K, ? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
//hashmap的两层循环,先循环tab ,在循环tab[i]里的链表或者红黑树
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
public V get(Object key)
public V get(Object key) {
Node<K,V> e;
//调用HashMap的实现
if ((e = getNode(hash(key), key)) == null)
return null;
// accessOrder 访问顺序为true，插入顺序为false 这个值说的是：访问是否把值放到最后，还是插入的时候放到最后
// 默认构造器是插入顺序，也可以使用构造器传递true
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
//因为e修改过其值，所以把这个元素放到链表的最后一个元素
// b->p->a
//先判断执行条件
// accessOrder 访问顺序为true，插入顺序为false 这个值说的是：访问是否把值放到最后，还是插入的时候放到最后
// 默认构造器是插入顺序，也可以使用构造器传递true
//(last = tail) != e e不是尾部元素
//先把e的after设置为空
//然后就是想办法把b->a关联
//判断b == null ，因为b = p.before,如果b == null，则说明p是头节点
//如果b为空，p->a,因为p需要移动到尾部，a自然就是头节点
//如果b不是空，b.after = a;
//判断a是否是空的
//如果a不是空的， a.before = b;
//如果a是空的 b->p ,因为a = p.after，如果a = null,说明p就是末端节点 ,last=b
//如果last==null ,那说明链表只有p一个元素，所以head=p tail = p;
//则设 last->p,p<-last tail = p;
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//last = 尾部tail
if (accessOrder && (last = tail) != e) {
// h t
// b->p->a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null; //b->p
if (b == null)//p b == null，说明p就是head
head = a;//设置新的头部为a
else//b->p
b.after = a; //b->a
if (a != null) //a不是空
a.before = b; //b<-a
else //a 是空的
last = b; //last = b
if (last == null) //b 是空的或者尾部是空的
head = p; //head = p
else {
p.before = last; //last<-p
last.after = p;//last->p
}
tail = p; //新的尾部为p
++modCount;
}
}
public V put(K key, V value)
调用的是HashMap的put，只是在put里面调用了子类覆盖的方法，用于调整内置的head tail
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//-----------------------------linkedList实现--------------------
afterNodeAccess(e);
//-----------------------------linkedList实现--------------------
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
//-----------------------------linkedList实现--------------------
afterNodeInsertion(evict);
//-----------------------------linkedList实现--------------------
return null;
}
//新建一个节点都会向linked的链表中设置
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;
}
//新建一个节点都会向linked的链表中设置
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
//把插入的元素设置到尾部调整链表
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail; //记录链表的尾部
tail = p;//尾部设置为p
if (last == null) //如果之前的尾部是空的，说明之前没有数组
head = p;//数组的头部 = p
else {
//绑定last 和 p的关系
p.before = last;
last.after = p;
}
}
//因为e修改过其值，所以把这个元素放到链表的最后一个元素
// b->p->a
//先判断执行条件
// accessOrder 访问顺序为true，插入顺序为false 这个值说的是：访问是否把值放到最后，还是插入的时候放到最后
// 默认构造器是插入顺序，也可以使用构造器传递true
//(last = tail) != e e不是尾部元素
//先把e的after设置为空
//然后就是想办法把b->a关联
//判断b == null ，因为b = p.before,如果b == null，则说明p是头节点
//如果b为空，p->a,因为p需要移动到尾部，a自然就是头节点
//如果b不是空，b.after = a;
//判断a是否是空的
//如果a不是空的， a.before = b;
//如果a是空的 b->p ,因为a = p.after，如果a = null,说明p就是末端节点 ,last=b
//如果last==null ,那说明链表只有p一个元素，所以head=p tail = p;
//则设 last->p,p<-last tail = p;
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//last = 尾部tail
if (accessOrder && (last = tail) != e) {
// h t
// b->p->a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null; //b->p
if (b == null)//p b == null，说明p就是head
head = a;//设置新的头部为a
else//b->p
b.after = a; //b->a
if (a != null) //a不是空
a.before = b; //b<-a
else //a 是空的
last = b; //last = b
if (last == null) //b 是空的或者尾部是空的
head = p; //head = p
else {
p.before = last; //last<-p
last.after = p;//last->p
}
tail = p; //新的尾部为p
++modCount;
}
}
//这个方法可以删除最古老的元素(就是链表的头元素head) removeEldestEntry 返回true
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); //删除最老的元素
}
}
//linked的实现是返回false
//如果该映射应该删除其最老的条目，则返回true。
//在映射中插入新条目后，put和putAll调用此方法。
//它为实现者提供了在每次添加新条目时删除最老条目的机会。
//如果映射表示缓存，这是有用的:它允许映射通过删除陈旧的条目来减少内存消耗。
// 示例使用:这个覆盖将允许映射增加到100个条目，然后在每次添加新条目时删除最老的条目，保持100个条目的稳定状态。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; //LinkedHashMap的Entry
TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next); //转成树节点，主要是给hashmap用的
transferLinks(q, t);//LinkedHashMap的主要工作
return t;
}
//把src替换为dst
//b->src->a
//如果 b == null ，那么src为头部节点head head = dst;
//如果 b不是空 b.after = dst;
// 如果a == null 那么src为尾部节点tail tail = dst;
//如果a不是空 a.before = dst;
private void transferLinks(LinkedHashMap.Entry<K,V> src,
LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
public V remove(Object key)
调用的是HashMap的remove，只是在remove里面调用了子类覆盖的方法，用于调整内置的head tail
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
//-----------------------------linkedList实现--------------------
afterNodeRemoval(node);
//-----------------------------linkedList实现--------------------
return node;
}
}
return null;
}
//调整链表，把e删除
//b -> p -> a
//最终搞成这样 b->a b<-a
//先清空 p.before = p.after = null;
//如果b == null 那说明p就是head 那删掉p a不就是head
//b不是空 b.after = a;
//如果a==null 那说明p就是tail，删除a后 不就是b就是最后一个 tail = b;
//a不是空 a.before = b;
void afterNodeRemoval(Node<K,V> e) { // unlink
//b -> p -> a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//清空引用
p.before = p.after = null;
//如果b == null 那说明p就是head 那删掉p a不就是head
if (b == null)
head = a;
else //b不是空 b.after = a;
b.after = a;
//如果a==null 那说明p就是tail，删除a后 不就是b就是最后一个 tail = b;
if (a == null)
tail = b;
else
a.before = b;
}
