Java 7 HashMap 詳解-有解無憂

HashMap<K, V>

是 AbStractMap 的子類，實作了 Map、Cloneable 和 Serializable（后面有關于 Serializable 的一個問題），

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

DEFAULT_INITIAL_CAPACITY（默認初始容量）

常量，值為 16，必須是 2 的冪，

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

MAXIMUM_CAPACITY（最大容量）

常量，值為 2 的 30 次冪，即使建構式 public HashMap(int initialCapacity, float loadFactor) 和 public HashMap(int initialCapacity) 的引數 initialCapacity 比 MAXIMUM_CAPACITY 大，域 table 陣列的長度仍為 MAXIMUM_CAPACITY，

static final int MAXIMUM_CAPACITY = 1 << 30;

DEFAULT_LOAD_FACTOR（默認加載因子）

常量，值為 0.75，除了建構式 public HashMap(int initialCapacity, float loadFactor)，其它建構式創建的 HashMap 物件的加載因子都為 DEFAULT_LOAD_FACTOR，

static final float DEFAULT_LOAD_FACTOR = 0.75f;

EMPTY_TABLE

常量，值為 Entry<?, ?> 型別的空陣列，當 inflateTable 方法沒有被呼叫時，table 域的初始值為它，為什么不用 null？Java 8 中用 null，

static final Entry<?,?>[] EMPTY_TABLE = {};

table

哈希表，必要時調整大小，長度必須總是 2 的冪，為什么長度必須總是 2 的冪？見靜態方法 indexFor(int h, int length)，為什么 table 等域被修飾符 transient 修飾？ Object 類的 hashCode 方法是本地方法，在不同計算機上的回傳值可能不同，

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

threshold

閾值，如果 table == EMPTY_table，以剛好比 threshold 大于等于的 2 的冪為長度“初始化” table，

int threshold;

loadFactor

加載因子，閾值 = 容量 * 加載因子，

final float loadFactor;

modCount

在結構上被修改的次數，結構修改是那些更改映射數或以其他方式修改內部結構（例如，rehash 方法）的次數，此欄位用來使集合視圖上的迭代器 fail-fast（參見 ConcurrentModificationException），

transient int modCount;

ALTERNATIVE_HASHING_THRESHOLD_DEFAULT（替代哈希閾值默認）、Holder、hashSeed

一般情況下，指定虛擬機引數 jdk.map.althashing.threshold 開啟替代哈希，

HashMap(int initialCapacity, float loadFactor)

使用 initialCapacity 和 loadFactor 構造一個空的 HashMap，先校驗引數，再給 loadFactor 和 threshold 域賦值，最后呼叫 init 方法，在 HashMap 中，init 方法什么都不做，

在此類外和其他三個建構式中都被呼叫，

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();
}

void init() {
}

HashMap(Map m)

用指定的映射構造一個新的 HashMap，它是用默認加載因子創建的，初始容量足夠大，先呼叫建構式，然后“初始化” table 域，最后將引數 m 中的鍵值映射放入 table 陣列中，

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);
}

inflateTable(int toSize)

“初始化”表，先呼叫 roundUpToPowerOf2 方法獲得剛好比 threshold 大于等于的 2 的冪，然后初始化 threshold 和 table 域，

private void inflateTable(int toSize) {
    int capacity = roundUpToPowerOf2(toSize);

    // loadFactor 是可以大于 1 的，但是會加劇哈希沖突，所以保持默認值 0.75 就好
    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;
}

indexFor(int h, int length)

回傳哈希的位置，長度必須總是 2 的冪，這樣 h & (length - 1) 和 h % length 等價，& 的效率比 % 高，

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);
}

get(Object key)

key 為空時呼叫 getForNullKey()，xxxForNullKey() 都是為了性能，遍歷 table 陣列的 0 位置，遇到 key 為空的映射，回傳它的值，否則回傳空，在 addEntry(int hash, K key, V value, int bucketIndex) 中，為空的 key 被放在 table 陣列的 0 位置；不為空時呼叫 getEntry()，

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);

    return null == entry ? null : entry.getValue();
}

private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

getEntry(Object key)

回傳與引數 key 關聯的 Entry 物件，先獲得 key 的哈希，為了避免沖突，哈希函式被設計得很復雜，然后獲得 key 在 table 中的位置，最后遍歷那個位置的所有 Entry 并回傳與 key 對應的 Entry，

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash &&
            // key 和 e.key 的參考相同（含同時為 null 的情況）
            ((k = e.key) == key ||
                (key != null && key.equals(k))))
            return e;
    }
    return null;
}

final int hash(Object k) {
    int h = hashSeed;
    // 如果禁用了替代哈希且 k 是 String 的實體
    if (0 != h && k instanceof String) {
        // sun.misc.Hashing 這個類在 JDK 8 中被移除
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // 此函式確保僅在每個位位置以常數倍數不同的哈希代碼具有有限的沖突數（默認加載因子下約為 8）
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

put(K key, V value)

先確保 table 陣列被初始化，key 為空時呼叫 putForNullKey(V value) 將鍵值對放在 table 陣列的 0 位置，不為空時先獲得 key 的哈希，然后獲得 key 在 table 中的位置，最后遍歷那個位置的所有 Entry，如果找到與 key 對應的 Entry，覆寫它的值，如果找不到就呼叫 addEntry 方法在 table 陣列中添加一個 Entry，回傳值為被覆寫的值，

public V put(K key, V value) {
    // 如果 table 與 EMPTY_TABLE 共享空表實體（表未初始化時）
    if (table == EMPTY_TABLE) {
        // 對表初始化或擴容
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    // 回傳哈希值 h 的索引
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash &&
            // key 和 e.key 的參考相同（含同時為 null 的情況）
            ((k = e.key) == key ||
                key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            // 當呼叫 HashMap 中已有的鍵 k 的 put(k，v) 覆寫條目中的值時，就會呼叫此方法
            e.recordAccess(this);
            return oldValue;
        }
    }

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

resize(int newCapacity)

如果舊容量為 MAXIMUM_CAPACITY，將閾值賦值為 Integer.MAX_VALUE，回傳，防止此方法再次被呼叫，先創建容量為引數 newCapacity 的新 table，然后呼叫 transfer 方法轉移所有的 Entry 從當前 table 到新 table，最后替換 table 和 threhold，

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);
}

transfer(Entry[] newTable, boolean rehash)

轉移所有的 Entry 從當前 table 到新 table，被多個執行緒呼叫時可能會出現回圈鏈表，執行緒不安全，

假設 table 中的某個位置如下圖所示（有三個 Entry），thread1 和 thread2 都剛剛執行完這個位置的第一次 while 回圈的 Entry next = e.next;

thread1 執行完 while 回圈

thread2 執行完第一次 while 回圈

thread2 執行完第二次 while 回圈

thread2 執行完第三次 while 回圈

可能出現 CPU 占用過高的問題，結合 Linux 和 JDK 的命令一起分析：

top 找出 CPU 占比最高的行程的 PID
ps -ef 或 jps 進一步定位這個行程是一個什么樣的后臺程式
ps -mp PID -o THREAD, tid, time 找出這個行程中 CPU 占比最高的執行緒的 TID
jstack PID | grep TID 的十六進制的小寫 -A60 定位到具體代碼行

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;
        }
    }
}

putAll(Map m)

先確保 table 陣列被初始化，然后如果引數 m 中鍵值映射的數量比閾值大，用加載因子計算出目標容量，并調整 table 陣列的大小為剛好大于等于目標容量的 2 的冪，最后呼叫 put 方法將引數 m 中的鍵值映射放入 table 陣列中，

public void putAll(Map<? extends K, ? extends V> m) {
    int numKeysToBeAdded = m.size();
    if (numKeysToBeAdded == 0)
        return;

    if (table == EMPTY_TABLE) {
        inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
    }

    /*
     * 如果要添加的映射數大于或等于閾值，則展開映射，
     * 這是保守的；明顯的條件是（m.size() + size）>= threshold，
     * 但是如果要添加的鍵與此映射中已有的鍵重疊，則此條件可能導致具有兩倍于適當容量的映射，
     * 通過使用保守的計算方法，我們最多可以對自己進行一次額外的調整，
     */
    if (numKeysToBeAdded > threshold) {
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
        if (targetCapacity > MAXIMUM_CAPACITY)
            targetCapacity = MAXIMUM_CAPACITY;
        int newCapacity = table.length;
        while (newCapacity < targetCapacity)
            newCapacity <<= 1;
        if (newCapacity > table.length)
            resize(newCapacity);
    }

    for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
}

clear()

將 table 域中的每個位置賦值為空，size 域賦值為 0，但 modCount 域加 1（結構修改），

public void clear() {
    modCount++;
    Arrays.fill(table, null);
    size = 0;
}

containsValue(Object value)

如果 value 為空，回傳 containsNullValue() 的回傳值，因為 null 可以直接用 == 比較，物件要用 euqals 方法比較，

public boolean containsValue(Object value) {
    if (value == null)
        return containsNullValue();

    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (value.equals(e.value))
                return true;
    return false;
}

private boolean containsNullValue() {
    Entry[] tab = table;
    for (int i = 0; i < tab.length ; i++)
        for (Entry e = tab[i] ; e != null ; e = e.next)
            if (e.value == null)
                return true;
    return false;
}

Entry<K,V>

是 Map.Entry<K, V> 的子類，有 hash、key、value 和 next 四個域，在它的 equals 方法中，如果引數 o 是 Map.Entry 的實體且引數 o 的 key 和 value 域和它的相同，回傳 true，否則回傳 false，在它的 hashCode() 中，回傳值是鍵的哈希與值的哈希的異或結果，

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    ...
    public final boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry e = (Map.Entry)o;
        Object k1 = getKey();
        Object k2 = e.getKey();
        // k1 和 k2 的參考相同（含同時為 null 的情況）
        if (k1 == k2 ||
            (k1 != null && k1.equals(k2))) {
            Object v1 = getValue();
            Object v2 = e.getValue();
            if (v1 == v2 || (v1 != null && v1.equals(v2)))
                return true;
        }
        return false;
    }

    public final int hashCode() {
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }
    ...
}

void addEntry(int hash, K key, V value, int bucketIndex)

如果在將鍵值映射放入 table 陣列中之前，鍵值映射的數量大于等于閾值且 table 陣列的對應位置不為空，以當前 table 陣列長度的二倍調整大小，重新計算哈希和對應位置，呼叫 createEntry 方法從鏈表頭部放入 Entry 物件，

如果不考慮調整大小，用 createEntry 方法代替 addEntry 方法，

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 createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    // 頭插法
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

entrySet()

entrySet() 回傳 entrySet0() 的回傳值，

如果 entrySet 不為空，entrySet0() 回傳 entrySet；如果為空，初始化 entrySet 并回傳，

entrySet 的默認值為空，

EntrySet 的構造方法繼承自 AbstractSet>，什么都不做，

hashMap.forEach((key, value) -> System.out.println(key + "=" + value)); 先呼叫 entrySet 的 iterator() 獲得迭代器，iterator() 回傳 HashMap 的 newEntryIterator() 的回傳值，newEntryIterator() 創建一個 EntryIterator 物件并回傳，

然后通過 EntryIterator 物件的 next() 遍歷 entrySet，next() 回傳 nextEntry() 的回傳值，

nextEntry() 先判斷 modCount 與預期的是否相等和下一個 Entry 是否為空，如果相等且不為空，將下一個 Entry 的 next 域賦值給 EntryIterator 的 next 域并判斷是否為空，如果為空，將 table 陣列中下一個位置的 Entry 賦值給 next 域，回傳下一個 Entry，

keySet() 和 values() 同理，最后回傳的是 nextEntry.getKey() 的回傳值和 nextEntry.value，

public Set<Map.Entry<K,V>> entrySet() {
    return entrySet0();
}

private Set<Map.Entry<K,V>> entrySet0() {
    Set<Map.Entry<K,V>> es = entrySet;
    return es != null ? es : (entrySet = new EntrySet());
}

private transient Set<Map.Entry<K,V>> entrySet = null;

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator();
    }
    ...
}

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {
    ...
    protected AbstractSet() {
    }
    ...
}

Iterator<Map.Entry<K,V>> newEntryIterator()   {
    return new EntryIterator();
}

private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
    public Map.Entry<K,V> next() {
        return nextEntry();
    }
}

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
    
    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    }

    public final boolean hasNext() {
        return next != null;
    }
    
    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
    
        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
        current = e;
        return e;
    }
    ...
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/136511.html

標籤：其他

上一篇：BCIduino腦電模塊如何通過OpenBCI_GUI測阻抗？

下一篇：Mysql用戶與權限操作