熱點推薦：
您现在的位置： 電腦知識網 >> 編程 >> Java編程 >> Javascript >> 正文

java源碼分析之LinkedHashMap

2022-06-13   來源: Javascript 
      LinkedHashMap類似於HashMap但是迭代遍歷它時取得鍵值對的順序是插入次序或者是最近最少使用（LRU）的次序只比HashMap慢一點而在迭代訪問時反而更快因為它使用鏈表維護內部次序（HashMap是基於散列表實現的相關HashMap的內容可以看《Java集合類》和《HashMap源碼分析》）
 
public class LinkedHashMap<KV> extends HashMap<KV> implements Map<KV>
     LinkedHashMap繼承自HashMap並實現了Map接口
 
LinkedHashMap只定義了兩個屬性
 
 
  /**
       * The head of the doubly linked list
       * 雙向鏈表的頭節點
       */
      private transient Entry<KV> header;
      /**
       * The iteration ordering method for this linked hash map: true
       * for accessorder false for insertionorder
       * true表示最近最少使用次序false表示插入順序
     */
    private final boolean accessOrder;
 
LinkedList一共提供了五個構造方法
 
 
  // 構造方法構造一個指定初始容量和負載因子的按照插入順序的LinkedList
  public LinkedHashMap(int initialCapacity float loadFactor) {
      super(initialCapacity loadFactor);
      accessOrder = false;
  }
  // 構造方法構造一個指定初始容量的LinkedHashMap取得鍵值對的順序是插入順序
  public LinkedHashMap(int initialCapacity) {
      super(initialCapacity);
      accessOrder = false;
}
// 構造方法用默認的初始化容量和負載因子創建一個LinkedHashMap取得鍵值對的順序是插入順序
public LinkedHashMap() {
    super();
    accessOrder = false;
}
// 構造方法通過傳入的map創建一個LinkedHashMap容量為默認容量（）和(mapzise()/DEFAULT_LOAD_FACTORY)+的較大者裝載因子為默認值
public LinkedHashMap(Map<? extends K ? extends V> m) {
    super(m);
    accessOrder = false;
}
// 構造方法根據指定容量裝載因子和鍵值對保持順序創建一個LinkedHashMap
public LinkedHashMap(int initialCapacity
             float loadFactor
                         boolean accessOrder) {
    super(initialCapacity loadFactor);
    thisaccessOrder = accessOrder;
}
 
     從構造方法中可以看出默認都采用插入順序來維持取出鍵值對的次序所有構造方法都是通過調用父類的構造方法來創建對象的


 
 
     LinkedHashMap是基於雙向鏈表的而且屬性中定了一個header節點為什麼構造方法都沒有對其進行初始化呢？
 
     注意LinkedHashMap中有一個init()方法 HashMap的構造方法都調用了init()方法這裡LinkedHashMap的構造方法在調用父類構造方法後將從父類構造方法中調用init()方法（這也解釋了為什麼HashMap中會有一個沒有內容的init()方法）
 
void init() {
        header = new Entry<KV>( null null null);
        headerbefore = headerafter = header;
}
     看init()方法的確是對header進行了初始化並構造成一個雙向循環鏈表（和LinkedList的存儲結構是一樣的）
 
     transfer(HashMapEntry[] newTable)方法和init()方法一樣也在HashTable中被調用transfer(HashMapEntry[] newTable)方法在HashMap調用resize(int newCapacity)方法的時候被調用
 
 
void transfer(HashMapEntry[] newTable) {
    int newCapacity = newTablelength;
    for (Entry<KV> e = headerafter; e != header; e = eafter) {
        int index = indexFor(ehash newCapacity);
        enext = newTable[index];
        newTable[index] = e;
    }
}
 
     根據鏈表節點e的哈希值計算e在新容量的table數組中的索引並將e插入到計算出的索引所引用的鏈表中
 
containsValue(Object value) 
 
 
  public boolean containsValue(Object value) {
      // Overridden to take advantage of faster iterator
      if (value==null) {
          for (Entry e = headerafter; e != header; e = eafter)
              if (evalue==null)
                  return true;
      } else {
          for (Entry e = headerafter; e != header; e = eafter)
                  if (valueequals(evalue))
                    return true;
    }
    return false;
}
 
     重寫父類的containsValue(Object value)方法直接通過header遍歷鏈表判斷是否有值和value相等而不用查詢table數組
 
get(Object key)
 
 
public V get(Object key) {
    Entry<KV> e = (Entry<KV>)getEntry(key);
    if (e == null)
        return null;
    erecordAccess(this);
    return evalue;
}
 
     get(Object key)方法通過HashMap的getEntry(Object key)方法獲取節點並返回該節點的value值獲取節點如果為null則返回nullrecordAccess(HashMap<KV> m)是LinkedHashMap的內部類Entry的一個方法將在介紹Entry的時候進行詳細的介紹
 
clear() 
 
public void clear() {
    superclear();
    headerbefore = headerafter = header;
}
     clear()方法先調用父類的方法clear()方法之後將鏈表的header節點的before和after引用都指向header自身即header節點就是一個雙向循環鏈表這樣就無法訪問到原鏈表中剩余的其他節點他們都將被GC回收


 
 
     以上的內容多多少少都涉及到了LinkedHashMap的內部類Entry<KV>下面詳細介紹這個內部類
 
 
  // 這是一個私有的靜態的內部類繼承自HashMap的Entry
  private static class Entry<KV> extends HashMapEntry<KV> {
          // 對前後節點的引用
          Entry<KV> before after;
      // 構造方法直接調用父類的構造方法
      Entry(int hash K key V value HashMapEntry<KV> next) {
          super(hash key value next);
      }
  
    // 移除該節點只需修改前一節點的after引用和後一節點的before引用
private void remove() {
    // 修改後該節點服務再被訪問會被GC回收
        beforeafter = after;
        afterbefore = before;
    }
 
    // 在指定節點之前插入當前節點（雙向鏈表插入節點的過程）
private void addBefore(Entry<KV> existingEntry) {
    // 將當前節點的after引用指向existingEntry
        after  = existingEntry;
        // 將before的引用指向existingEntry節點的前一節點
before = existingEntrybefore;
        // 將原先existingEntry節點的前一節點的after引用指向當前節點
beforeafter = this; 
        // 將原先existingEntry節點的後一節點的before引用指向當前節點
        afterbefore = this;
    }
 
// 當調用此類的get方法或put方法（put方法將調用到父類HashMapEntry的put
// 方法）都將調用到recordAccess(HashMap<KV> m)方法
// 如果accessOrder為true即使用的是最近最少使用的次序則將當前被修改的
// 節點移動到header節點之前即鏈表的尾部
// 這也是為什麼在HashMapEntry中有一個空的
// recordAccess(HashMap<KV> m)方法的原因
    void recordAccess(HashMap<KV> m) {
        LinkedHashMap<KV> lm = (LinkedHashMap<KV>)m;
        if (lmaccessOrder) {
            lmmodCount++;
            remove();
            addBefore(lmheader);
        }
    }
    // 和recordAccess(HashMap<KV> m)方法一樣在HashMapEntry中同樣有一個對應的空方法當進行刪除（remove）操作的時候會被調用
    void recordRemoval(HashMap<KV> m) {
        remove();
    }
}
 
     介紹完了內部類Entry下面是創建一個Entry節點和添加一個Entry的兩個方法 
 
     createEntry(int hashK keyV valueint bucketIndex)
 
 
void createEntry(int hash K key V value int bucketIndex) {
    HashMapEntry<KV> old = table[bucketIndex];
    Entry<KV> e = new Entry<KV>(hash key value old);
    table[bucketIndex] = e;
    eaddBefore(header);
    size++;
}
 
     createEntry(int hashK keyV valueint bucketIndex)方法覆蓋了父類HashMap中的方法這個方法不會拓展table數組的大小該方法首先保留table中bucketIndex處的節點然後調用Entry的構造方法（將調用到父類HashMapEntry的構造方法）添加一個節點即將當前節點的next引用指向table[bucketIndex] 的節點之後調用的eaddBefore(header)是修改鏈表將e節點添加到header節點之前
 
     該方法同時在table[bucketIndex]的鏈表中添加了節點也在LinkedHashMap自身的鏈表中添加了節點
 
addEntry(int hash K key V value int bucketIndex)
 
 
  void addEntry(int hash K key V value int bucketIndex) {
      createEntry(hash key value bucketIndex);
      Entry<KV> eldest = headerafter;
      if (removeEldestEntry(eldest)) {
          removeEntryForKey(eldestkey);
      } else {
          if (size >= threshold)
              resize( * tablelength);
      }
}
 
     首先調用createEntry(int hashK keyV valueint bucketIndex)方法之後獲取LinkedHashMap中最老（最近最少使用）的節點接著涉及到了removeEldestEntry(Entry<KV> eldest)方法來看一下
 
protected boolean removeEldestEntry(MapEntry<KV> eldest) {
    return false;
}
為什麼這個方法始終返回false？ 
 
     結合上面的addEntry(int hashK keyV valueint bucketIndex)方法這樣設計可以使LinkedHashMap成為一個正常的Map不會去移除最老的節點 
 
     為什麼不在代碼中直接去除這部分邏輯而是設計成這樣呢？ 
 
     這為開發者提供了方便若希望將Map當做Cache來使用並且限制大小只需繼承LinkedHashMap並重寫removeEldestEntry(Entry<KV> eldest)方法像這樣 
 
private static final int MAX_ENTRIES = ;
protected boolean removeEldestEntry(MapEntry eldest) {
     return size() > MAX_ENTRIES;
}
     LinkedHashMap除了以上內容外還有和迭代相關的三個方法及三個內部類以及一個抽象內部類分別是newKeyIterator()newValueIterator()newEntryIterator()和KeyIterator類ValueIterator類EntryIterator類以及LinkedHashIterator類
 
     三個new方法分別返回對應的三個類的實例而三個類都繼承自抽象類LinkedHashIterator下面看迭代相關的三個類
 
 
private class KeyIterator extends LinkedHashIterator<K> {
    public K next() { return nextEntry()getKey(); }
}
private class ValueIterator extends LinkedHashIterator<V> {
    public V next() { return nextEntry()value; }
}
private class EntryIterator extends LinkedHashIterator<MapEntry<KV>> {
    public MapEntry<KV> next() { return nextEntry(); }
}
 
     從上面可以看出這三個類都很簡單只有一個next()方法next()方法也只是去調用LinkedHashIterator類中相應的方法 和KeyIterator類ValueIterator類EntryIterator類以及LinkedHashIterator類
 
下面是LinkedHashIterator類的內容
 
 
  private abstract class LinkedHashIterator<T> implements Iterator<T> {
      Entry<KV> nextEntry    = headerafter;
      Entry<KV> lastReturned = null;
      // 和LinkedList中ListItr類定義了expectedModCount用途一致
      int expectedModCount = modCount;
      // 下一個節點如果是header節點說明當前節點是鏈表的最後一個節點即已經遍歷完鏈表了沒有下一個節點了
      public boolean hasNext() {
          return nextEntry != header;
      }
    //移除上一次被返回的節點lastReturned 
    public void remove() {
        if (lastReturned == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        LinkedHashMapthisremove(lastReturnedkey);
        lastReturned = null;
        expectedModCount = modCount;
    }
    // 返回下一個節點
    Entry<KV> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (nextEntry == header)
            throw new NoSuchElementException();
        // 獲取並記錄返回的節點
        Entry<KV> e = lastReturned = nextEntry;
        // 保存對下一個節點的引用
        nextEntry = eafter;
        return e;
    }
}
 
     LinkedHashMap本應和HashMap及LinkedList一起分析比較他們的異同為了彌補這裡簡單的總結一些他們之間的異同
 
     HashMap使用哈希表來存儲數據並用拉鏈法來處理沖突LinkedHashMap繼承自HashMap同時自身有一個鏈表使用鏈表存儲數據不存在沖突LinkedList和LinkedHashMap一樣使用一個雙向循環鏈表但存儲的是簡單的數據並不是鍵值對所以HashMap和LinkedHashMap是Map而LinkedList是一個List這是他們本質的區別LinkedList和LinkedHashMap都可以維護內容的順序但HashMap不維護順序


From:http://tw.wingwit.com/Article/program/Java/Javascript/201311/25431.html
    《java源碼分析之LinkedHashMap》本文是由Javascript免費提供，內容來源於互聯網,本文歸原作者所有。
  • 上一篇文章：

  • 下一篇文章：
    • 相關文章
    主板 CPU 硬盤 內存 顯卡 聲卡 顯示器 光驅 死機
    推薦文章
    Copyright © 2005-2022 電腦知識網 Computer Knowledge   All rights reserved.