Java 1.7 HashMap源碼閱讀

1. 構造方法

// 預設Hash 
	// The default initial capacity - MUST be a power of two.
	// 預設容量即hash可放置的元素數量
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	// The load factor used when none specified in constructor.
	// 未指定時的預設擴容因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
 	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 的注釋
        // If table == EMPTY_TABLE then this is the initial capacity at which the
    	// table will be created when inflated.
    	// 如果表為空表則threshold将在inflated時被建立
        threshold = initialCapacity;
        // init 為空方法 即當真正向hashmap中put時使用inflateTable方法初始化Entry數組
        init();
    }

2. put方法

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old value is replaced.
     * 
     * 
     */
 public V put(K key, V value) {
 		
        if (table == EMPTY_TABLE) {
       		 // 真正的初始化方法
        	// 代碼比較簡單 
        	// threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 
        	// threshold 初始時為12
            // table = new Entry[capacity];
            //  最後單獨說initHashSeedAsNeeded(capacity);
            inflateTable(threshold); // 這裡傳的是初始時 的 16 
        }
        // 為null值 指定位置
        // table[0]的連結清單  并傳回舊值或null
        if (key == null)
            return putForNullKey(value);
            // 計算hash值
        int hash = hash(key);
        // 為利用hash找到 key應該放到table的某個數組的鍊下
        int i = indexFor(hash, table.length);
        // 周遊 table[i]連結清單 找到與目前key相同的替換并傳回舊值
        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;
            }
        }
		// 若table[i]下沒有相同的key 則 modCount+1,并執行addEntry将key,value放到map中
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

執行addEntry方法将key,value存入map中。

此方法先計算是否需要擴容後真正放值。

//size : The number of key-value mappings contained in this map.
 void addEntry(int hash, K key, V value, int bucketIndex) {
 		// add之前會判斷目前map中的數量是否大于等于門檻值
 		// 擴容條件 目前size超過門檻值 并且 table[bucketIndex] 不為空
        if ((size >= threshold) && (null != table[bucketIndex])) {
        	// 擴容原先的兩倍 
            resize(2 * table.length);
            // 重新計算hash值
            hash = (null != key) ? hash(key) : 0;
            // 計算目前key所屬的 table數組位置
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

真正的放值方法，

使用的是頭插法即将table[bucketIndex]替換為我們的key，并将原先的Entry當作目前Entry的next節點

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

3. resize擴容方法

擴容方法是建立一個新的Entry數組（容量為原先的兩倍）

并将原先數組中的值轉移到新數組中

// 此處使用了一個全局變量MAXIMUM_CAPACITY 
static final int MAXIMUM_CAPACITY = 1 << 30;//1073741824 即2的30次方
 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        // 如果目前table容量已經等于最大容量值則将門檻值設定為整數最大值并傳回
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;//2<sup>31</sup>-1
            return;
        }
		
        Entry[] newTable = new Entry[newCapacity];
        // 轉移值 initHashSeedAsNeeded用于傳回是否需要重新計算hash
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        // 轉移值之後 更改table的引用 
        table = newTable;
        // 更新門檻值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

轉移數組方法

周遊table 并循環周遊每個連結清單為連結清單中每個元素計算隸屬與數組哪個位置然後轉移

注意：HashMap是非線程安全的轉移是會有機會造成循環引用，後面會示範怎樣造成循環引用

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

4. 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) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        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++;
                size--;
                // 若為連結清單 頭直接修改頭的引用
                if (prev == e)
                    table[i] = next;
                else //修改引用 前一個結點的下個結點指向目前的下個結點 進而抛棄目前節點
                    prev.next = next;
                
                e.recordRemoval(this);//
                return e;
            }
            // 修改引用 周遊下一個Entry
            prev = e;
            e = next;
        }

        return e;
    }

5. initHashSeedAsNeeded 和 hash

傳回是否需要重新計算hash

transient int hashSeed = 0;
final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;// 初始時 false
        
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);// 容量是否超過 預設時Integer最大值
        // 預設為false 但是通過列印可以得知為true 沒有檢視怎麼修改的但從字面意思時虛拟機是否啟動
        //private static volatile boolean booted = false;
   		// public static boolean isBooted() {
    	//    return booted;
    	//}

		// 預設 false ^ false 
        boolean switching = currentAltHashing ^ useAltHashing;// 異或預算 不相同時傳回true
        if (switching) {// true 時 hashSeed hash 種子
            hashSeed = useAltHashing//false
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

    /**
     * holds values which can't be initialized until after VM is booted.
     */
    private static class Holder {

        /**
         * Table capacity above which to switch to use alternative hashing.
         */
        static final int ALTERNATIVE_HASHING_THRESHOLD;

        static {
        // 判斷是否有此參數
        // 	-Djdk.map.althashing.threshold=-1:表示不做優化（不配置這個值作用一樣）
		// -Djdk.map.althashing.threshold<0:報錯

		// -Djdk.map.althashing.threshold=1:表示總是啟用随機HashSeed
		// -Djdk.map.althashing.threshold>=0:便是hashMap内部的數組長度超過該值了就使用随機HashSeed，降低碰撞
            String altThreshold = java.security.AccessController.doPrivileged(
                new sun.security.action.GetPropertyAction(
                    "jdk.map.althashing.threshold"));
            int threshold;
            try {
                threshold = (null != altThreshold)
                        ? Integer.parseInt(altThreshold)
                        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;// 預設Integer最大值

                // disable alternative hashing if -1
                if (threshold == -1) {
                    threshold = Integer.MAX_VALUE;
                }

                if (threshold < 0) {
                    throw new IllegalArgumentException("value must be positive integer.");
                }
            } catch(IllegalArgumentException failed) {
                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
            }
			
            ALTERNATIVE_HASHING_THRESHOLD = threshold;
        }
    }

final int hash(Object k) {
        int h = hashSeed;// hashSeed 預設為0
        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);
    }

6. 多線程 resize 線程不安全示範

轉移Entry會造成連結清單翻轉
線程1執行完轉移 線程二開始轉移

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

假定條件：兩個線程同時執行到，第一次while next = e.next時，線程一繼續執行，線程二等待線程一執行完後再執行。

e = table[i];

next = 1;

Java 1.7 HashMap源碼閱讀

Java 1.7 HashMap源碼閱讀

目錄

1. 構造方法

2. put方法

3. resize擴容方法

4. remove

5. initHashSeedAsNeeded 和 hash

6. 多線程 resize 線程不安全示範

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method