Java容器(五):LinkedHashMap实现原理详解编程语言

  从之前的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

(0)
上一篇 2021年7月18日
下一篇 2021年7月18日

相关推荐

发表回复

登录后才能评论