从之前的LinkedList源码分析来看,带有Linked的,其实就是和双链表相关,毫无疑问,LinkedHashMap就是HashMap再多加一个双向链表,其内部的存储规则和HashMap是一样的,但是在迭代中,HashMap是无序的,LinkedHashMap是有序的
LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序,该迭代顺序通常就是将键插入到映射中的顺序(插入顺序)。
一、LinkedHashMap的数据结构
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
LinkedHashMap继承自HashMap,因此继承了HashMap的成员变量等
//header是双链表的头结点 private transient Entry<K,V> header; //accessOrder为true时,按访问顺序排序,false时,按插入顺序排序 private final boolean accessOrder;
LinkedHashMap中有两个特有的成员变量 — header和accessOrder,接下来会讲到
public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; }
LinkedHashMap共有五个构造方法,每一个方法都是调用父类HashMap的构造方法,并且accessOrder都为false,也就是默认按插入顺序排序
LinkedHashMap的数据结构
图中,有两个比较特殊的变量,after和before,他们是Entry引用,before指向当前节点的前一个节点,after指向当前节点的后一个节点(注意绿线)
LinkedHashMap中,覆盖了Entry内部类,在原来的Entry的实现上,增加了before和after,这就是双联链表的前引用和后引用,并增加了addBefore和remove等重要方法
private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration. Entry<K,V> before, after; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); } /** * Removes this entry from the linked list. */ private void remove() { before.after = after; after.before = before; } /** * Inserts this entry before the specified existing entry in the list. */ private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }
二、LinkedHashMap的存储实现
在HashMap中,存储实现的流程是这样的:
put() -> addEntry() -> createEntry()
put()中计算当前key的hash值所在的哈希表的索引位置,并在createEntry()中完成key-value节点在该索引位置的插入
而在LinkedHashMap中,覆盖了addEntry() 和 createEntry()方法的实现,而没有覆盖put方法,因此这就证明了LinkedHashMap的存储规则是和HashMap一样的
我们来看看addEntry() 和 createEntry()方法
void addEntry(int hash, K key, V value, int bucketIndex) { //调用HashMap的addEntry() super.addEntry(hash, key, value, bucketIndex); // Remove eldest entry if instructed Entry<K,V> eldest = header.after; if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } } void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; //addBefore,其他都和HashMap的createEntry相关 e.addBefore(header); size++; }
从上面的代码看,LinkedHashMap和HashMap中,addEntry() 和 createEntry()的实现差不多,而LinkedHashMap多调用了一个新增的addBefore方法,这是LinkedHashMap存储排序最关键的地方
/** * 将当前节点插入到existingEntry的前面 */ private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }
通过addBefore,这样便形成了一个双线链表
三、HashMap和LinkedHashMap遍历
首先来看HashMap的遍历,HashMap的核心代码如下:
private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry<K,V> current; // current entry //当调用keySet().iterator()时,调用此代码 HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; //从哈希表数组从上到下,查找第一个不为null的节点,并把next引用指向该节点 while (index < t.length && (next = t[index++]) == null) ; } } public final boolean hasNext() { return next != null; } //当调用next时,会调用此代码 final Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); //如果当前节点的下一个节点为null,从节点处罚往下查找哈希表,找到第一个不为null的节点 if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } }
从这里可以看出,HashMap遍历时,按哈希表的每一个索引的链表从上往下遍历,由于HashMap的存储规则,最晚添加的节点都有可能在第一个索引的链表中,这就造成了HashMap的遍历时无序的。
然后来看LinkedHashMap的遍历:
private abstract class LinkedHashIterator<T> implements Iterator<T> { //nextEntry指向头结点的下一个节点,也就是双向链表中的第一个节点 Entry<K,V> nextEntry = header.after; Entry<K,V> lastReturned = null; /** * The modCount value that the iterator believes that the backing * List should have. If this expectation is violated, the iterator * has detected concurrent modification. */ int expectedModCount = modCount; public boolean hasNext() { return nextEntry != header; } public void remove() { if (lastReturned == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); LinkedHashMap.this.remove(lastReturned.key); lastReturned = null; expectedModCount = modCount; } //当调用next时,会调用此代码 Entry<K,V> nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (nextEntry == header) throw new NoSuchElementException(); 从第一个节点开始,依次往下遍历 Entry<K,V> e = lastReturned = nextEntry; nextEntry = e.after; return e; } }
四、总结
可见LinkedHashMap的实现原理还是比较简单的,而且LinkedHashSet的内部完全就是通过LinkedHashMap来实现的
原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/7793.html