HashMap 大家知道,索引是(length-1) & hash 算出来的,是无序的,那么LinkedHashList是如何保证顺序的呢?
答案就是LInkedHashMap的一个内部类,可以看到这个是一个双向列表,那下个问题,是如何维护呢?
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里有一些未实现的方法
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
看名称其实就是在访问,插入和删除后的操作,这个其实就是为了LInkedHashMap维护链表而调用的,如果没有这些方法,LInkedHashMap就要重写putVal方法,这很没必要。挑一个方法来看。
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;
// 前驱节点为空,那么该节点的后继节点就为head
if (b == null)
head = a;
// 不为空,前驱节点的后继节点为该节点的后继节点
else
b.after = a;
// 后继节点为空,尾巴就是前驱节点
if (a == null)
tail = b;
//不为空,则后继节点的前驱节点,为该节点的前驱节点
else
a.before = b;
}
接下来就是foreach遍历了,可以看下和LInkedHashMap是重写了这个方法的,和HashMap的不同
//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;
// 是用tab循环
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();
}
}
//LInkedHashMap
public void forEach(BiConsumer<? super K, ? super V> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
//遍历的是这个双向链表,从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();
}