//在删除节点e时，同步将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 的前置后置节点都置空 p.before = p.after = null; //如果前置节点是null，则现在的头结点应该是后置节点a if (b == null) head = a; else//否则将前置节点b的后置节点指向a b.after = a; //同理如果后置节点时null ，则尾节点应是b if (a == null) tail = b; else//否则更新后置节点a的前置节点为b a.before = b; }
查询 LinkedHashMap重写了get()和getOrDefault()方法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
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; }
public V getOrDefault(Object key, V defaultValue) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return defaultValue; if (accessOrder) afterNodeAccess(e); return e.value; }
public boolean containsValue(Object value) { //遍历一遍链表，去比较有没有value相等的节点，并返回 for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) { V v = e.value; if (v == value || (value != null && value.equals(v))) return true; } return false; }
对比HashMap，是用两个for循环遍历，相对低效。
1 2 3 4 5 6 7 8 9 10 11 12 13
public boolean containsValue(Object value) { Node<K,V>[] tab; V v; if ((tab = table) != null && size > 0) { for (int i = 0; i < tab.length; ++i) { for (Node<K,V> e = tab[i]; e != null; e = e.next) { if ((v = e.value) == value || (value != null && value.equals(v))) return true; } } } return false; }
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> { public final int size() { return size; } public final void clear() { LinkedHashMap.this.clear(); } public final Iterator<Map.Entry<K,V>> iterator() { return new LinkedEntryIterator(); } public final boolean contains(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Node<K,V> candidate = getNode(hash(key), key); return candidate != null && candidate.equals(e); } public final boolean remove(Object o) { if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>) o; Object key = e.getKey(); Object value = e.getValue(); return removeNode(hash(key), key, value, true, true) != null; } return false; } public final Spliterator<Map.Entry<K,V>> spliterator() { return Spliterators.spliterator(this, Spliterator.SIZED | Spliterator.ORDERED | Spliterator.DISTINCT); } public final void forEach(Consumer<? super Map.Entry<K,V>> action) { if (action == null) throw new NullPointerException(); int mc = modCount; for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) action.accept(e); if (modCount != mc) throw new ConcurrentModificationException(); } }
最终的的EntryIterator:
1 2 3 4
final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } }
abstract class LinkedHashIterator { //下一个节点 LinkedHashMap.Entry<K,V> next; //当前节点 LinkedHashMap.Entry<K,V> current; int expectedModCount;
LinkedHashIterator() { //初始化时，next 为 LinkedHashMap内部维护的双向链表的扁头 next = head; //记录当前modCount，以满足fail-fast expectedModCount = modCount; //当前节点为null current = null; } //判断是否还有next public final boolean hasNext() { //就是判断next是否为null，默认next是head 表头 return next != null; } //nextNode() 就是迭代器里的next()方法 。 //该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。 final LinkedHashMap.Entry<K,V> nextNode() { //记录要返回的e。 LinkedHashMap.Entry<K,V> e = next; //判断fail-fast if (modCount != expectedModCount) throw new ConcurrentModificationException(); //如果要返回的节点是null，异常 if (e == null) throw new NoSuchElementException(); //更新当前节点为e current = e; //更新下一个节点是e的后置节点 next = e.after; //返回e return e; } //删除方法 最终还是调用了HashMap的removeNode方法 public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } }