HashMap - 基於哈希表和Map 介面的鍵值對利器（JDK 1.7）

HashMap 的一些認識： (JDK 1.7) 基於哈希表的Map介面的非同步實現，定義了鍵映射到值的規則此實現提供所有可選的映射操作，並允許使用null值和null鍵此實現假定哈希函數將元素適當分佈在各桶之間，為讀取操作提供穩定性能迭代時間與實例容量(桶的數量)及其大小(鍵-值映射關係數) ...

HashMap 的一些認識： (JDK 1.7)

基於哈希表的Map介面的非同步實現，定義了鍵映射到值的規則
此實現提供所有可選的映射操作，並允許使用null值和null鍵
此實現假定哈希函數將元素適當分佈在各桶之間，為讀取操作提供穩定性能
迭代時間與實例容量(桶的數量)及其大小(鍵-值映射關係數)成正比

■ 類定義

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

繼承 AbstractMap抽象類，實現了Map介面
實現 Cloneable介面
實現 java.io.Serializable 介面，支持序列化

HashMap - “鏈表散列” (數組+鏈表)，數組每一項都是一條鏈的數據結構

//The default initial capacity - MUST be a power of two.
static final int DEFAULT_INITIAL_CAPACITY = 16;
//The maximum capacity - MUST be a power of two <= 1<<30.
static final int MAXIMUM_CAPACITY = 1 << 30;
//The load factor used when none specified in constructor.
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//The table, resized as necessary. Length MUST Always be a power of two.
transient Entry<K,V>[] table;
//The number of key-value mappings contained in this map.
transient int size;
//The next size value at which to resize (capacity * load factor).
int threshold;
//The load factor for the hash table.
final float loadFactor;
/**
  * The number of times this HashMap has been structurally modified
  * Structural modifications are those that change the number of mappings in
  * the HashMap or otherwise modify its internal structure (e.g.,
  * rehash).  This field is used to make iterators on Collection-views of
  * the HashMap fail-fast.  (See ConcurrentModificationException).
  */
transient int modCount;

■ 構造器

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);
    // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
        this.loadFactor = loadFactor;
        //閾值為容量*負載因數和最大容量+1之間的最小值 以此值作為容量翻倍的依據(不能超過最大容量)
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        //初始化一個2次冪的Entry類型數組 一個桶對應一個Entry對象
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() && 
        (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
}

- Entry

/**
  * 靜態類 預設實現內部Entry介面 (介面中可定義內部介面-Map.Entry介面為Map的內部介面)
  * PS:JDK8中引入default，作用為在介面中定義預設方法實現
  */
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;//key具有引用不可變特性
    V value;
    Entry<K,V> next;//next指向下一個：單向鏈表，頭插入
    final int hash;
    ……
}

■ 主要方法

　put(k, v)

/**
  * @return key不存在返回null，否則返回舊值
  */
public V put(K key, V value) {
    //其允許存放null的key和null的value
    //當其key為null時，調用putForNullKey方法，放入到table[0]的這個位置（null鍵只有一個）
    if (key == null)
        return putForNullKey(value);
    //通過調用hash方法對key進行哈希，得到哈希之後的數值
    //其目的是為了儘可能的讓鍵值對可以分不到不同的桶中
    int hash = hash(key);
    //根據上一步驟中求出的hash得到在數組中是索引i
    int i = indexFor(hash, table.length);
    //如果i處的Entry不為null，則通過其next指針不斷遍歷e元素的下一個元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;//使用臨時變數k主要用於e.key的賦值，意義有限
        //hash一致 && (key引用相同 或 key字元串比較相同)
        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;//若key不存在則返回null
}

hash()

//JDK1.7
final int hash(Object k) {
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h = hashSeed;
    }
    //異或就是兩個數的二進位形式，按位對比，相同取0，不同取一
    //此演算法加入了高位計算，防止低位不變，高位變化時，造成的 hash 衝突
    h ^= k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
//JDK1.8 擾動函數 -> 散列值優化函數
static final int hash(Object key) {
    int h;
    //把一個數右移16位即丟棄低16為，就是任何小於2^16的數，右移16後結果都為0
    //2的16次方再右移剛好就是1 同時int最大值為32位
    //任何一個數，與0按位異或的結果都是這個數本身
    //為indexFor做準備
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

indexFor()

/**
  * Int範圍(2^32)從-2147483648到2147483648，加起來大概40億空間，記憶體不能直接讀取
  * 用之前還要先做對數組的長度取模運算，得到的餘數才能用來訪問數組下標
  * @Param h 根據hash方法得到h
  * @Param length 一定是2次冪
  */
static int indexFor(int h, int length) {
    //2次冪-1 返回的結果的二進位為永遠是都是1 比如 15 -> 1111 (16 -> 10000)
    //與運算 只有 1 & 1 = 1 正好相當於一個“低位掩碼”
    //如果length-1中某一位為0，則不論h中對應位的數字為幾，對應位結果都是0，這樣就讓兩個h取到同一個結果，hash衝突
    //同時這個操作可以保證索引不會大於數組的大小(見開頭的描述)
    return h & (length-1);
}

addEntry()

//該方法為包訪問 package java.util(本包私有性高於子類)
void addEntry(int hash, K key, V value, int bucketIndex) {
    //當前容量超過閾值 && 當前坐標數組非空
    //有個優雅的設計在於，若bucketIndex處沒有Entry對象，那麼新添加的entry對象指向null，從而就不會有鏈了
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);//容量擴容一倍
        hash = (null != key) ? hash(key) : 0;//hash重新計算
        bucketIndex = indexFor(hash, table.length);//index重新計算
    }
    createEntry(hash, key, value, bucketIndex);//新增Entry元素到數組的制定下標位置
}
//該方法為包訪問 package java.util
void createEntry(int hash, K key, V value, int bucketIndex) {
    // 獲取指定 bucketIndex 索引處的 Entry
    Entry<K,V> e = table[bucketIndex];
    // 將新創建的 Entry 放入 bucketIndex 索引處，並讓新的 Entry 指向原來的 Entry
    // 形成鏈表，新加入的放入鏈表頭部，最先加入的放入尾部
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

remove()

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    return (e == null ? null : e.value);
}


/**
  * Removes and returns the entry associated with the specified key
  * in the HashMap.  Returns null if the HashMap contains no mapping
  * for this key.
  */
final Entry<K,V> removeEntryForKey(Object key) {
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];//用於記錄該key的前一個元素(預設先從隊首開始)
    Entry<K,V> e = prev;//從隊首開始往隊尾遍歷
    //遍歷key所在鏈表
    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;//remove屬於結構性改造，modCount計數+1
            size--;//當前Map的有效元素數量-1
            if (prev == e)
                table[i] = next;//若當前key正好位於隊首，則隊首指向next
            else 
                prev.next = next;//若當前key不位於隊首，則該key之前的元素的next指向該key的下一個元素
            e.recordRemoval(this);//LinkedHashMap專用方法
            return e;
        }
        //繼續往隊尾找
        prev = e;//指向當前迴圈元素的上一個元素
        e = next;//指向下一次迴圈元素
    }
    return e;
}

■ HashMap 迭代

//方法一
Iterator<Map.Entry<Integer,Object>> it = map.entrySet().iterator();
while (it.hasNext()) {
   Map.Entry<Integer, Object> entry = it.next();
   System.out.println("key=" + entry.getKey() + " and value=" + entry.getValue());
   //在迭代中可刪除 Map 元素也是推薦，避免快速失敗
}


//方法二
for (Map.Entry<Integer,Object> entry : map.entrySet()) {
   System.out.println("key=" + entry.getKey() + " and value=" + entry.getValue());
}

***** 此版本為JDK 1.7，由於筆者水平有限，之後有補充的話會更新此文，請各位看客多多諒解支持 ********

***** JDK1.8 的 HashMap 之後會另寫一篇 ******

HashMap - 基於哈希表和Map 介面的鍵值對利器 （JDK 1.7）

HashMap - 基於哈希表和Map 介面的鍵值對利器（JDK 1.7）