天天看點
傳回

java基礎-Java集合架構-Map接口-HashMap原理（jdk1.7和jdk1.8）Java集合架構-Map接口-HashMap原理和源碼

Java集合架構-Map接口-HashMap原理和源碼

HashMap底層實作原理

  • HashMap的put操作以jdk7為例說明
    • HashMap map = new HashMap():
    • 在執行個體化之後，底層建立了一個長度為16的一維數組Entry[] table。
    • …可能已經執行過多次put…
    • map.put(key1,value1);
    • 步驟：
      • 首先調用，調用key1所在類的hashCode()計算key1哈希值，此哈希值經過某種算法計算後，得到在Entry數組中的存放位置。
      • 如果此位置上的資料為空，此時key1-value1添加成功。—情況1
      • 如果此位之上的資料不為空，（意味着此位置上存在一個或多個資料（以連結清單形式存在）），則比較key1和已經存在的一個或多個資料的哈希值（逐個比較連結清單上的key）：
        • 如果key1的哈希值與已經存在的資料的哈希值都不同，此時key1-value1添加成功。—情況2
        • 如果key1的哈希值和已經存在的某一個書序的哈希值相同，則繼續比較：調用key1所在類的equals()方法，比較：
          • 如果equals()方法傳回false，則key1-value1添加成功.—情況3
          • 如果equals()方法傳回true，則将value1去替換相同key的vlaue值（修改操作了）
      • 補充：關于情況2和情況3，此時key1-value1和原來的資料以連結清單的方式存儲
      • 在不斷的添加過程中，會涉及到擴容問題，預設的擴容方式：擴容為原來容量的2倍，并将原有的資料複制過來
  • jdk8相較于jdk7在底層實作方面的不同：
    • new HashMap()：底層沒有建立一個長度為16的數組
    • jdk 8 底層的資料時：Node[],而非Entry();
    • 首次調用put()方法時，底層建立長度為16的數組
    • jdk7底層結構隻有：數組+連結清單。jdk8中底層結構：資料+連結清單+紅黑樹。
      • 當數組的某一個索引位置上的元素以連結清單形式存在的資料個數大于8
      • 且目前數組長度大于64時
        • 此時索引位置上的所有資料改為使用紅黑樹存儲

HashMap的源碼

HashMap源碼中的重要常量

  • DEFAULT_INITIAL_CAPACITY:HashMap的預設容量，16
  • MAXIMUM_CAPACITY：HashMap的最大支援容量，2^30
  • DEFAULT_LOAD_FACTOR：HashMap的預設加載因子
  • TREEIFY_THRESHOLD：Buck中連結清單長度大于該預設值，轉化為紅黑樹（樹化門檻值）
  • UNTREEIFY_THRESHOLD：Buck中紅黑樹存儲的Node小于該預設值，轉化為連結清單（去樹化門檻值）
  • MIN_TREEIFY_CAPACITY：桶中的Node被樹化時最小的hash表容量。（當桶中Node的數量大到需要變紅黑樹時，若hash表容量小于MIN_TREEIFY_CAPACITY時，此時應執行resize擴容操作。這個MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍）
  • table：存儲元素的數組，總是2的n次幂
  • entrySet：存儲具體元素的集
  • size：HashMap中存儲的鍵值對的數量
  • modCount：HashMap擴容和結構改變的次數。
  • threshold：擴容的臨界值，=“容量”填充因子
  • loadFactor：填充因子

具體構造器源碼

  • jdk1.7 
  • /**
 * hashMap底層數組預設的初始化長度-必須是2的幾次幂
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * hashMap底層數組的最大長度，取值範圍在 2 - 2^30之間
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 預設負載因子值，用于計算hashMap底層數組擴容的擴容門檻值，擴容門檻值=數組長度*負載因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 常量，一個空的長度為0的Entry數組
 */
static final Entry<?,?>[] EMPTY_TABLE = {};

/**
 * hashMap用于存儲元素的底層數組，數組元素類為Entry<?,?>,數組長度必須，在HashMap類加載時
 * table初始化為EMPTY_TABLE,初始化是一個空的長度為0的Entry數組
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

/**
 * map中的元素總個數
 */
transient int size;

/**
 * 擴容門檻值，擴容門檻值=負載因子*HashMap底層數組的長度 threshold=loadFactor * capacity
 */
int threshold;

/**
 * 負載因子，用于計算擴容門檻值
 */
final float loadFactor;

/**
 * 表示hashmap擴容和結構改變次數
 */
transient int modCount;

/**
 *
 */
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
  • jdk1.8 
  • /**
     * hashMap底層數組預設的初始化長度-必須是2的幾次幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * hashMap底層數組的最大長度，取值範圍在 2 - 2^30之間
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 預設負載因子值，用于計算hashMap底層數組擴容的擴容門檻值，擴容門檻值=數組長度*負載因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 連結清單樹化的門檻值
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 紅黑樹退化成連結清單的門檻值
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * HashMap中被樹化時Node的最小容量
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * hashMap的底層數組，用于存儲key-value對，在jdk1.8中用Node作為table的元素類型
     */
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * map中的元素總個數
     */
    transient int size;

    /**
     * 表示hashmap擴容和結構改變次數
     */
    transient int modCount;

    /**
     * 擴容門檻值，擴容門檻值=負載因子*HashMap底層數組的長度 threshold=loadFactor * capacity
     */
    int threshold;

    /**
     * 負載因子，用于計算擴容門檻值
     */
    final float loadFactor;
  • HashMap的構造器
    • jdk1.7 
    • public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}


public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}


public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);

    putAllForCreate(m);
}
    • jdk1.8 
    • public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

HashMap的對象建立和調用put方法源碼流程

  • hashMap在jdk1.7版本下的對象建立和調用put方法的流程及源碼
    • 建立HashMap對象
      • HashMap map = new HashMap<>();//使用空參的構造器建立 
      • public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
      • hashmap空參的構造器會調用HashMap(int initialCapacity, float loadFactor)構造器，傳入的值為initialCapacity=DEFAULT_INITIAL_CAPACITY=16， loadFactor=DEFAULT_LOAD_FACTOR=0.75f
      • 在HashMap(int initialCapacity, float loadFactor)構造器中會先判斷底層數組初始化容量initialCapacity是否小于0，如果小于0則抛出異常IllegalArgumentException("Illegal initial capacity: " +initialCapacity)
      • 然後判斷初始化容量是否大于HashMap最大支援容量2^30，如果大于則将最大容量MAXIMUM_CAPACITY指派給初始化容量initialCapacity
      • 接下來判斷負載因子是否小于0，且是Float類型，如果不滿足條件則抛出異常new IllegalArgumentException("Illegal load factor: " + loadFactor);
      • 然後将入參負載因子的指派給屬性loadFactor
      • 屬性threshold擴容門檻值為初始化容量initialCapacity
      • 接着調用init()方法，該方法在HashMap中為空方法 
      • public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);

    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}
    • 調用put(K key, V value)調用邏輯
    • put方法調用鍊：
      • put(K key, V value)-> inflateTable(int toSize)->roundUpToPowerOf2(int number)->initHashSeedAsNeeded(int capacity)
      • put(K key, V value)->putForNullKey(V value)->addEntry(int hash, K key, V value, int bucketIndex)
      • put(K key, V value)->hash(Object k)->indexFor(int h, int length)->addEntry(int hash, K key, V value, int bucketIndex)
    • 步驟解析：
      • 調用put(K key,V value)方法，先判斷目前底層數組是否為空
        • 如果為空則調用 inflateTable(int toSize)方法擴容底層數組
        • 在inflateTable(int toSize)方法内，
          • 先調用roundUpToPowerOf2(int number)，這裡計算一個2的n次方的數組容量，預設為2的4次方，為16。指派為capacity
          • 然後設定擴容門檻值threshold為capacity * loadFactor, MAXIMUM_CAPACITY + 1兩者的較小數，初始化hashmap底層數組table為new Entry[capacity]
          • 最後在inflateTable方法内調用initHashSeedAsNeeded()初始化hashSeed，用于計算hash值
        • 然後判斷所添加的key-value鍵值對的key是否為null
          • 如果為null則調用putForNullKey(V value)方法
            • 在putForNullKey(V value)方法中，周遊hashmap數組索引0的位置下的連結清單（預設key=null的鍵值對，由于null無法調用hashcode取hash值，是以将0作為null的哈希值），存在table[0]的位置，循環連結清單下的元素，如果對比key是否等于null
            • 如果在table[0]下找到key==null的元素則，将新的value替換原來的值。傳回舊值
            • 如果在table[0]下未找到key == null的元素，則調用addEntry(0,null,value,0);方法将新的key=null的Entry添加到table[0]的數組索引處
              • addEntry(int hash, K key, V value, int bucketIndex)方法中，先判斷目前元素數量是否大于等于擴容門檻值threshold，并且判斷目前要添加的table[bucketIndex]位置上的元素是否不為空（如果不為空，則表示存在hash沖突），如果兩個條件都滿足調用resize(2 * table.length)将hashmap底層數組擴容原來的兩倍
              • 在resize(int newCapacity)方法中先擷取舊底層數組table指派給變量Entry[] oldTable
              • 擷取oldTable的長度，指派給oldCapacity作為舊底層數組的長度，如果oldCapacity等于MAXIMUM_CAPACITY（hashmap的最大容量），則将擴容門檻值指派成Integer.MAX_VALUE，直接傳回不進行擴容了。
              • 如果oldCapacity不等于MAXIMUM_CAPACITY，繼續接下去的邏輯根據newCapacity建立新的Entry數組指派給newTable變量
              • 接着調用transfer(Entry[] newTable, boolean rehash) 方法
              • 在transfer(Entry[] newTable, boolean rehash) 方法中兩層循環周遊舊的hashmap底層數組，将舊數組+連結清單下的所有元素重新根據hash值調用indexFor(int h, int length) 方法，
              • indexFor(int h, int length) 方法内部是h & (length -1) 等同于h%length取餘運算，目的是擷取将不同哈希值都能映射到數組上
              • 将舊元素指派到新元素後，将newTable變量指派給hashmap對象的table作為新的hashmap，并且根據newCapacity * loaderFactor計算新的擴容門檻值
              • 傳回到addEntry方法的if ((size >= threshold) && (null != table[bucketIndex]))邏輯塊中，根據key，調用hash(Object k)擷取新的hash值,調用indexFor(int h, int length)計算key在新的bucket中的位置
              • 接着調用createEntry(int hash, K key, V value, int bucketIndex) 方法，
              • 在jdk7中createEntry(int hash, K key, V value, int bucketIndex使用頭插法，将新元素Entry放入table[bucketIndex]位置，新元素Entry的next屬性指向原來的table[bucketIndex]下的Entry。
        • 傳回到put(K key, V value)方法中，如果key != null，則調用hash(Object o)方法計算key的hash值指派給hash變量
        • 然後調用indexFor(int h, int length) 計算key在bucket中的位置。指派給i
        • 循環hashmap底層數組table[i]的位置下的所有元素
          • 如果table[i]下沒有元素，則跳出循環
          • 如果table[i]下有一個或多個元素，則周遊對比table[i]下的所有元素的key與添加的key是否相等
            • 循環中判斷表中的元素e的hash值是否與添加的key的hash值相等，如果相等再判斷兩個key的值是否相等，如果key相等，則表示這是一次修改操作，将新的value值替換原來的value 值，最後傳回oldValue結束
        • 如果在table[i]位置下未找到相同的key，則調用addEntry(hash, key, value, i);把新元素Entry放置到table[i]的位置
        • addEntry(int hash, K key, V value, int bucketIndex)方法中，先判斷目前元素數量是否大于等于擴容門檻值threshold，并且判斷目前要添加的table[bucketIndex]位置上的元素是否不為空（如果不為空，則表示存在hash沖突），如果兩個條件都滿足調用resize(2 * table.length)将hashmap底層數組擴容原來的2倍
          • 在resize(int newCapacity)方法中先擷取舊底層數組table指派給變量Entry[] oldTable
          • 擷取oldTable的長度，指派給oldCapacity作為舊底層數組的長度，如果oldCapacity等于MAXIMUM_CAPACITY（hashmap的最大容量），則将擴容門檻值指派成Integer.MAX_VALUE，直接傳回不進行擴容了。
          • 如果oldCapacity不等于MAXIMUM_CAPACITY，繼續接下去的邏輯根據newCapacity建立新的Entry數組指派給newTable變量
          • 接着調用transfer(Entry[] newTable, boolean rehash) 方法
          • 在transfer(Entry[] newTable, boolean rehash) 方法中兩層循環周遊舊的hashmap底層數組，将舊數組+連結清單下的所有元素重新根據hash值調用indexFor(int h, int length) 方法，
          • indexFor(int h, int length) 方法内部是h & (length -1) 等同于h%length取餘運算，目的是擷取将不同哈希值都能映射到數組上
          • 将舊元素指派到新元素後，将newTable變量指派給hashmap對象的table作為新的hashmap，并且根據newCapacity * loaderFactor計算新的擴容門檻值
          • 傳回到addEntry方法的if ((size >= threshold) && (null != table[bucketIndex]))邏輯塊中，根據key，調用hash(Object k)擷取新的hash值,調用indexFor(int h, int length)計算key在新的bucket中的位置
          • 接着調用createEntry(int hash, K key, V value, int bucketIndex) 方法，
          • 在jdk7中createEntry(int hash, K key, V value, int bucketIndex使用頭插法，将新元素Entry放入table[bucketIndex]位置，新元素Entry的next屬性指向原來的table[bucketIndex]下的Entry。
    • 源碼 
      • public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

private static int roundUpToPowerOf2(int number) {
    // assert number >= 0 : "number must be non-negative";
    return number >= MAXIMUM_CAPACITY
        ? MAXIMUM_CAPACITY
        : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
    • 總結hashMap在jdk1.7版本下的對象建立和調用put方法的總結
      • 在jdk1.7下，HashMap空參構造器調用HashMap(initialCapacity,loadFactor)構造器，初始化容量預設initialCapacity為16，loadFactor使用預設為0.75，threshold擴容門檻值預設為16*0.75=12
      • 在jdk1.7下對hashMap的數組做了懶加載機制，建立hashmap對象的時候，其table屬性值為長度為0的空的Entry[]數組
      • jdk1.7下的hashmap的put流程總結
        • 第一次put鍵值對會判斷，hashmap的table是否為空，為空則初始化。預設初始化成長度為16的Entry[]數組，并且計算擴容門檻值為loadfactor*capacity,預設為12
        • 接下去是判斷key==null的情況的鍵值對插入或修改操作，如果key為null，由于null無法調用hashcode是以将null放在table[0]位置，如果此時table[0]不存在元素，則将新Entry放在table[0]位置上，如果此時table[0]已存在元素或元素連結清單，則循環對比連結清單中的Entry的key和添加的Entry的key的hashcode是否相同，如果相同則進行一次修改操作，如果不同則使用頭插法，将添加的entry加載table[0]的位置，将新entry的next指向舊的連結清單的頭節點
        • 在添加過程中會有是否需要擴容的判斷，如果目前hashmap中的元素數量大于擴容門檻值threshold，并且目前要插入的位置的table[index]的位置是否已存在Entry，如果不存在則不進行擴容，如果已存在則需要擴容，擴容操作是将hashmap擴容至目前table長度的兩倍，并且将舊map中的元素根據hashcode重寫計算在bucket中的位置，并将這些元素指派到新的table中
        • 如果key!=null，則根據key的hashcode，使用算法計算新的hash值，然後根據hash值&數組長度-1，實際就是hash值與數組長度取餘，這樣能擷取到hash值映射到數組中的位置i
        • 然後根據key最後得到的在數組中的位置i，判斷table[i]是否已有元素存在，如果有則逐個周遊，對比已有元素和新添加元素的key的hashCode和key本身是否相同如果相同則是一次修改操作将新的值value替換舊的值oldValue，傳回oldValue。如果不存在相同key，則新的Entry指派到table[i]的位置，并将新元素Entry的next屬性指向舊元素的連結清單首節點（頭插法）
        • 添加新元素的方法中也會判斷是否需要擴容
  • hashMap在jdk1.8版本下的對象建立和調用put方法的流程及源碼
    • 在jdk1.8的hashMap中，使用Node表示key-value鍵值對
    • 建立HashMap對象
    • HashMap map = new HashMap<>();//使用空參的構造器建立
    • 在jdk1.8中如果調用無參的構造函數，則直接叫負載因子初始化為預設值DEFAULT_LOAD_FACTOR=0.75
    • 其他的屬性都會在第一次put的時候初始化 
    • public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}


public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
    • 調用put(K key, V value)調用邏輯
    • put方法調用鍊：
      • put(K key, V value)->putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)->resize()
      • put(K key, V value)->putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)->newNode(int hash, K key, V value, Node<K,V> next)
      • put(K key, V value)->putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)->TreeNode.putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v)
      • put(K key, V value)->putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)->newNode(int hash, K key, V value, Node<K,V> next)->treeifyBin(Node<K,V>[] tab, int hash)->replacementTreeNode(Node<K,V> p, Node<K,V> next)
    • 步驟解析：
      • 調用put(K key,V value)方法，在put(K key,V value)方法中調用putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
      • 在putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) 先将hashmap的table屬性指派給tab變量，判斷tab是否為null，或者tab的length是否為0,（初始化操作）。
        • 如果tab為null或者tab數組的length長度為0，則調用resize進行hashmap數組擴容，實際為初始化操作。
          • 調用resize()方法進行初始化擴容
            • 在resize()方法中先擷取table屬性，根據table屬性内容生成舊數組的長度oldCapacity，舊擴容門檻值oldThr，初始化新的數組長度newCapacity為0，新的擴容門檻值newThr為0
            • 判斷舊數組bucket長度oldCapacity是否大于0,
            • 如果oldCapacity大于0，表示試一次擴容操作，則先做一個保障機制，判斷oldCapacity是否大于hashmap數組最大值MAXIMUM_CAPACITY，如果oldCapacity大于等MAXIMUM_CAPACITY，則不進行擴容，将擴容門檻值指派成Integer.MAX_VALUE
            • 如果oldCapacity小于MAXIMUM_CAPACITY,則将新數組的容量newCap擴大至原來的兩倍newCap = oldCap << 1
            • 這裡有個判斷如果擴容至兩倍後的newCap小于MAXIMUM_CAPACITY并且原數組長度oldCap大于初始化數組長度DEFAULT_INITIAL_CAPACITY = 16,在這個條件下，将擴容門檻值也直接擴大成原來的兩倍newThr = oldThr << 1
            • 如果不滿足上述條件，擴容後的newCap大于MAXIMUM_CAPACITY或者oldCap小于初始化數組長度16，那麼會在後續操作中根據新的數組長度newCap計算新的擴容門檻值
            • 接下去判斷舊擴容門檻值oldThr是否大于0，如果oldThr大于0，則将oldThr指派給newCap
            • 如果oldCap <=0 并且oldThr <= 0，則這個場景為初始化場景那麼新的數組長度和擴容門檻值都使用初始化的參數，newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFUALT_INITIAL_CAPACITY)
            • 接下去的邏輯是判斷newThr是否為0，如果newThr為0，表示在上面的邏輯中，newCap過大大于了MAXIMUM_CAPACITY，是以重新計算擴容門檻值，并且判斷如果擴容門檻值過大，則直接取Integer.MAX_VALUE
            • 根據新的數組長度newCap生成新的Node<k,v> newTab[]數組，将table屬性值指派為newTab[]
            • 循環周遊oldTab将就數組中的元素，重新根據hashCode計算出在新數組中的位置，指派到newTab的相應的位置下
            • 在循環中判斷oldTab[j]位置上的元素是否為null，如果為null則繼續取下一個元素
            • 如果不為null
            • 判斷oldTab[i]的Node元素是否有後繼節點，如果沒有則根據hash值重新和newCap取餘擷取Node元素在新數組中的下标位置
            • 判斷oldTab[i]的Node元素是否為TreeNode，如果是則表示目前oldTab[i]下的是一顆紅黑樹，此時需要調用TreeNode.split()，此處後續解釋
            • 如果不滿足上述兩個條件，則表示目前插入的是連結清單的操作。這裡将操作分成高位連結清單hiHead，hiTail（擴容後的新數組的位置=舊數組連結清單索引位置+舊數組長度）和低位連結清單（舊數組的連結清單索引位置）loHead，loTail。
            • 這裡使用的方式是使用元素的hash & 舊數組長度oldCap，判斷得出的結果是否為0
            • 如果為0，則元素應該在低位連結清單處，也就是舊連結清單索引位置
            • 如果為1，則元素應該在高位連結清單處，也就是擴容後，舊連結清單索引位置+舊連結清單的長度
            • 解釋：這麼操作的原因是因為，擴容後，重hash的數組索引隻可能在“原索引位置”或者“原索引位置+oldCap”
            • 假設老表的長度為16，即oldCap為16，則新标的容量為16 * 2 =32。
            • 假設節點1的hash值為：0000 0000 0000 0000 0000 1111 0000 1010，節點2的hash值為0000 0000 0000 0000 0000 1111 0001 1010，oldCap-1的hash值為0000 0000 0000 0000 0000 0000 0000 1111，則節點1和節點2在舊表的索引位置為0000 0000 0000 0000 0000 0000 0000 1010（計算方法為&運算，兩個同時為1，結果為1，否則為0）。
            • 然後擴容後數組長度newCap為32，對應的newCap-1的hash值為0000 0000 0000 0000 0000 0000 0001 1111，節點1的hash值為：0000 0000 0000 0000 0000 1111 0000 1010，節點2的hash值為0000 0000 0000 0000 0000 1111 0001 1010。最後節點1在新表的索引值為0000 0000 0000 0000 0000 0000 0000 1010，而索引2在新表的索引值為0000 0000 0000 0000 0000 0000 0001 1010。對比可以看出，如果兩個節點在老表的位置相同，在新标的索引位置隻取決于節點hash值的倒數第n位（n = log2（newCapacity)）,目前為第5位。而此位的值剛好是oldCapacity的值16，也就是0000 0000 0000 0000 0000 0000 0001 0000
            • 是以，由于結果值取決于節點hash值得倒數第n位（此時為第5位），而此位置剛好是老表容量值，是以此時新表索引位置的計算可以替換為，直接使用節點hash值與老表容量oldCap進行位與（&）運算，如果結果為0則該節點在新表的索引位置為原索引位置，否則該節點的新表索引位置為“原索引+oldCap（舊表的數組容量）”
            • 最後在resize()方法中，傳回newTab
        • n為目前table的長度
        • 接下去在putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法中，先根據目前數組長度-1（n-1) & 元素key的hash值（實際是取模運算）擷取到元素應該在table的索引位置
        • 判斷元素計算後的索引位置在table處是否已存在元素
          • 如果不存在，則将新元素添加的table上，索引為(n-1)&hash
          • 如果在索引位置已存在元素則要分三個條件判斷
          • 判斷索引位置上已存在Node的key是否等于新添加的key，判斷條件為先判斷hash值，如果hash值相同，再調用key的equals方法判斷兩者是否相同，如果滿足上述兩個條件，則是一次替換操作，将新的value替換掉老的value，傳回oldValue
          • 如果索引位置上已存在Node的key不等于新添加的key，接着判斷目前索引位置上的節點是否為樹節點TreeNode，如果是樹節點，則進行樹節點的添加或替換操作，調用TreeNode.putTreeVal()方法，（後續要補充）
          • 如果如果索引位置上已存在Node的key不等于新添加的key，并且目前索引位置上的節點不是樹節點，那麼此時需要進行連結清單的添加或替換操作（jdk1.8是尾插法）
            • 添加方法，判斷連結清單上的節點的key是否等于新添加的key，判斷條件為先判斷hash值，如果hash值相同，再調用key的equals方法判斷兩者是否相同如果滿足上述兩個條件，則是一次替換操作，将新的value替換掉老的value，傳回oldValue。
            • 如果沒有找到相同key的節點，則是一次添加操作，找到連結清單上next屬性為null的節點p，也就是尾結點，将p的next屬性指派為new Node（newNode(hash, key, value, null)）。添加完後，還要判斷是否需要樹化
            • 判斷樹化的條件是，當連結清單上的節點數操作了樹化門檻值TREEIFY_THRESHOLD=8，并且容器中的元素數量超過了最小樹化元素總數MIN_TREEIFY_CAPACITY=64。
            • 如果目前連結清單上的節點數超過了樹化門檻值8，但是容器中的元素數量為超過最小樹化元素總數64，此時進行的是一次resize()擴容操作。
            • 隻有當連結清單上的節點數超過了樹化門檻值8，并且容器中的元素數量超過了最小樹化元素總數是，才進行樹化操作
            • 樹化操作，先循環連結清單上所有節點，調用replacementTreeNode(Node<K,V> p, Node<K,V> next) 将Node節點轉成TreeNode節點。将原來的單向連結清單變成雙向連結清單。 
              p.prev = tl;
tl.next = p;
            • 然後調用TreeNode.treeify(Node<K,V>[] tab) 方法進行具體樹化操作
    • 源碼： 
      • public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
集合 java hashmap
上一篇: Java集合在JDK1.7和JDK1.8中的不同——JDK1.7和JDK1.8中集合的對比研究——java集合深入了解1、ArrayList
下一篇: python的matplotlab繪圖時中文亂碼，報錯的解決問題，設定預設字型

繼續閱讀