如何進行HashMap擴容機制源碼分析

這期內容當中小編將會給大家帶來有關如何進行HashMap擴容機制源碼分析，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

具體看源碼之前，我們先簡單的說一下HashMap的底層數據結構

　　1、HashMap底層的數據結構是 數組 + 鏈表 + 紅黑樹

　　2、我們需要先了解一下HashMap底層的兩個變量

　　2-1：loadFactor: 加載因子，默認是0.75，這個值是經過反復測試最合適的值。

　　2-2：threshold: 當map里面的數據大于這個threshold就會進行擴容

　　注:詳細了解loadFactor點擊這里

　　2、現在來看一下HashMap的構造方法

　　hashMap的構造方法有4個。

　　1、空參構造方法，這個時候加載因子為默認的0.75，并且不會創建空間。

　　threshold 為0

　　數組為null

　　public HashMap() {

　　this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted

　　}

　　2、給定初始化容量大小，這個構造方法里面會直接去調用第三個構造方法

　　threshold 已經有值了

　　數組為null

　　public HashMap(int initialCapacity) {

　　this(initialCapacity, DEFAULT_LOAD_FACTOR);

　　}

　　3、給定初始化大小，和加載因子。

　　1、其實并不建議修改默認的加載因子。當然除非你很了解這里面的邏輯找到一個適合自己這個項目的加載因子

　　2、先是判斷你給的初始化容量是否合法，如果合法的話就用這個初始化容量計算出 threshold

　　threshold 已經有值了

　　數組為null

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

　　}

　　4、把一個Map作為參數傳遞過來，加載因子適應默認的0.75。把其它Map轉化成HashMap

　　threshold 已經有值了

　　數組為也不為空了

　　public HashMap(Map m) {

　　this.loadFactor = DEFAULT_LOAD_FACTOR;

　　putMapEntries(m, false);

　　}

　　final void putMapEntries(Map m, boolean evict) {

　　int s = m.size();

　　if (s > 0) {

　　if (table == null) { // pre-size

　　float ft = ((float)s / loadFactor) + 1.0F;

　　int t = ((ft < (float)MAXIMUM_CAPACITY) ?

　　(int)ft : MAXIMUM_CAPACITY);

　　if (t > threshold)

　　threshold = tableSizeFor(t);

　　}

　　else if (s > threshold)

　　resize();

　　for (Map.Entry e : m.entrySet()) {

　　K key = e.getKey();

　　V value = e.getValue();

　　putVal(hash(key), key, value, false, evict);

　　}

　　}

　　}

　　3、讓我們看看是HashMap是怎么進入擴容的

　　3-1：我們先從 put() 這個方法說起

　　public V put(K key, V value) {

　　return putVal(hash(key), key, value, false, true);

　　}

　　這個put方法底層是調用了一個叫 putVal 的方法，但是在這之前我們有必要看一下hash()這個方法。

　　直接使用 對象.hashCode(), 可能會出現重復，所以這個hash是對生成的hashcode進行一下擾亂，讓其重復性更低。

　　從這里也可以看到，HashMap只允許一個null鍵

　　static final int hash(Object key) {

　　int h;

　　return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

　　}

　　3-2：下面我們看一下這個putVal方法

　　putVal源碼：

　　final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

　　boolean evict) {

　　Node[] tab; Node 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 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)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 V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {

　　Node[] tab; Node p; int n, i;

　　if ((tab = table) == null || (n = tab.length) == 0){

　　// 當數據為null或者長度為0的時候進行擴，并發擴后的長度返回給n(前面說了hashMap底層最開始是個數組)

　　n = (tab = resize()).length;

　　}

　　// 之前可能有同學有疑問，hashcode那么長，為啥默認HashMap數組默認長度是16。其實最后的下標是經過處理的 (n - 1) & hash

　　if ((p = tab[i = (n - 1) & hash]) == null){

　　// 如果當前數組的下標，并沒有數據，也就是說當前添加的數據是第一個，那就直接加入進去就好了。不需要排序啥的

　　tab[i] = newNode(hash, key, value, null);

　　}

　　else {

　　// 找到了數據下標，并且里面的已經有數據了，

　　// 這里就要找到當前數據的位置屬于那里并加入進去，

　　// 還要判斷當前長度是否大于我們設置的長度，大于就要把鏈轉化成紅黑樹便于查找

　　}

　　++modCount;

　　// 判斷當前長度是否大于需要擴的長度，其實也好理解，數組是可以裝滿的，但是鏈不可能滿呀，但是長度超過一定的長度的時候鏈的性能就會很差了

　　if (++size > threshold)

　　resize();

　　// 節點插入后的操作，目前這個沒有任何實現，里面是個空方法

　　afterNodeInsertion(evict);

　　return null;

　　}

　　3-3：總結進入擴容的兩種情況

　　添加一個數據的時候，底層數組為空的時候

　　添加一個數據結束后，判斷當前數據個數是否大于threshold (需要擴容)的大小，大于就進行擴容

　　注：因為數據是具體添加到數組里面的鏈表，所以不存在數組越界情況。

　　4、具體看一下擴容代碼

　　擴容源碼：

　　final Node[] resize() {

　　Node[] 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);

　　}鄭州專業婦科醫院 http://fk.zyfuke.com/

　　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[] newTab = (Node[])new Node[newCap];

　　table = newTab;

　　if (oldTab != null) {

　　for (int j = 0; j < oldCap; ++j) {

　　Node 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)e).split(this, newTab, j, oldCap);

　　else { // preserve order

　　Node loHead = null, loTail = null;

　　Node hiHead = null, hiTail = null;

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

　　}

　　同樣的把源碼進行一下簡單的分享，去除復雜的內容

　　// 這個擴容方法就是

　　// 1、找到新的容量大小和新的threshold大小

　　// 2、把舊的數據全部復制到新的數組中去

　　final Node[] resize() {

　　Node[] 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){

　　newCap = oldThr;

　　}

　　// 使用空參構造方法第一次擴容進入，使用參數為map的構造方法，第一次也會進入這個擴容方法

　　else {

　　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[] newTab = (Node[])new Node[newCap];

　　table = newTab;

　　// 把舊的數據全部復制到新的數組中去

　　if (oldTab != null) {

　　//

　　}

　　return newTab;

　　}

　　5、總結(面試的時候：請你說一下HashMap的擴容)：

　　HashMap底層數據結構是 數組 + 鏈表 + 紅黑樹

　　真正的數據是存儲在鏈表中的，鏈表的長度是無限的。所以這時候就引入一個變量 threshold

　　當第一次向map里面添加數據，或添加完數據后的大小，大于 threshold的大小，這時候就會進行擴容

　　先說一下非第一次擴容，這個相對簡單點

　　1、如果當前的容量大小，大于等于HashMap規定的最大容量的話，直接讓threshold等于Integer的最大值，就可以了。

　　2、一般情況當前數組長度是不會大于最大值的，所以這時候新的數組長度等于舊數組的2倍。如果新的數組長度小于HashMap規定的最大值，并且舊的數組長度也大于等于HashMap規定的默認大小容量大小(16)，那么threshold擴大2倍，否則不變

　　非第一次擴容

　　1、HashMap，有四個構造方法。空參構造方法的threshold變量是0，其它構造方法threshold都有初始值。

　　2、當舊的threshold大于0的時候，新的數組容量大小就等于舊的threshold大小。新的threshold大小等于加載因子新的數組大小。

　　3、當舊的threshold不大于0的時候，新的數組大小就等于默認的大小(16)，新的threshold大小，就等于默認的容量大小默認的加載因子大小

上述就是小編為大家分享的如何進行HashMap擴容機制源碼分析了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。