HashMap為什么要指定初始大小？

在Java中，HashMap是一種基于哈希表實現(xiàn)的鍵值對存儲結構。哈希表是一種典型的散列表，它通過哈希函數(shù)將任意長度的鍵值對映射到一個固定長度的數(shù)組中，然后使用鏈表或紅黑樹等數(shù)據(jù)結構來解決哈希沖突。

在HashMap中，指定初始大小的作用是為了減少哈希沖突，提高存儲效率和查詢效率。當哈希表大小不足時，HashMap會自動擴容，但這個過程比較耗時，因為需要重新計算鍵值對的哈希值，重新分配內存空間，重新插入鍵值對等。如果預估好數(shù)據(jù)規(guī)模，指定初始大小可以避免不必要的擴容，提高程序的性能。

另外，指定初始大小還可以控制哈希表的負載因子。負載因子是哈希表中鍵值對數(shù)量與哈希表大小的比值，通常情況下，負載因子的值在0.75左右可以達到較好的性能和空間利用率。如果負載因子過高，會導致哈希沖突增多，查詢效率降低；如果負載因子過低，會導致哈希表空間浪費，存儲效率降低。因此，指定初始大小可以控制負載因子的值，達到平衡空間和時間的效果。

總之，指定初始大小可以優(yōu)化HashMap的空間利用率、時間復雜度和性能表現(xiàn)，是一種比較常見的優(yōu)化策略。

使用默認負載因子0.75時,需要put()，3個元素，需指定初始大小為4

如果使用默認的負載因子0.75，在put 3個元素時，設置初始大小為4是剛好合適的，不需要自動擴容，且能夠達到較好的效率。但是，如果要put 5個元素，初始大小為4可能就不夠了，會觸發(fā)自動擴容，導致效率降低。

具體來說，當初始大小為4時，哈希表的容量為4，而負載因子為0.75，表示當哈希表中元素數(shù)量達到容量的 0.75 倍即 3 個時，就會觸發(fā)自動擴容。因此，當你要put 5個元素時，會觸發(fā)一次自動擴容。

為了避免自動擴容，需要將初始大小設置得更大。一種常用的方法是，將初始大小設置為大于等于要put 的元素數(shù)量的最小的2的冪次方。例如，如果要put 5個元素，可以將初始大小設置為8，這樣可以避免觸發(fā)自動擴容，提高效率。

當然，如果你希望在put 5個元素時也不觸發(fā)自動擴容，并且能夠達到最大化的效率，可以根據(jù)實際情況調整初始大小和負載因子。具體的值需要根據(jù)實際場景進行調整，以達到最優(yōu)的性能。

怎么保證不會擴容呢？

可以將初始大小設置為大于等于要put的元素數(shù)量的最小的2的冪次方，以確保在使用默認負載因子的情況下，不會在插入元素時觸發(fā)擴容。例如如果需要put()5個元素，即2的5次方 = 32

那為什么要設置這么大而不是設置8？

當我們將初始大小設置為8時，如果要put 5個元素，那么在使用默認負載因子0.75的情況下，哈希表會在第四個元素插入時就觸發(fā)擴容，這是因為當前的容量為8，而put第四個元素時，已經(jīng)有3個元素占用了哈希表中的位置，此時負載因子已經(jīng)達到了0.375（即3/8），超過了默認負載因子0.75的一半，因此需要進行擴容。

而當我們將初始大小設置為32時，即使要put 5個元素，也不會觸發(fā)擴容，因為當前的容量為32，而put第五個元素時，已經(jīng)有4個元素占用了哈希表中的位置，此時負載因子為0.125（即4/32），遠遠低于默認負載因子0.75，不需要進行擴容。

因此，為了避免不必要的擴容操作，我們可以將初始大小設置為大于等于要put的元素數(shù)量的最小的2的冪次方，以確保在使用默認負載因子的情況下，不會在插入元素時觸發(fā)擴容。當然，如果我們知道要put的元素數(shù)量是多少，也可以直接將初始大小設置為該數(shù)量，以避免不必要的空間浪費。

知道要put的元素數(shù)量是多少，也可以直接將初始大小設置為該數(shù)量，這樣如果默認負載因子0.75豈不是又要開始觸發(fā)擴容？還是有消耗呢？比起空間浪費，這種要怎么衡量呢？

確實，如果我們知道要put的元素數(shù)量是多少，也可以直接將初始大小設置為該數(shù)量。在這種情況下，如果使用默認負載因子0.75，當哈希表中的元素數(shù)量達到容量的 0.75 倍時，就會觸發(fā)擴容，從而浪費一些空間。但是，這里需要注意的是，在初始大小等于元素數(shù)量的情況下，擴容所需的代價通常比較小，因為仍然有足夠的空間可以容納元素。

如果我們比較在初始大小等于元素數(shù)量和初始大小為2的冪次方時的空間浪費和時間代價，通常情況下，后者會更少。因為在初始大小為2的冪次方時，哈希表的容量通常都比較大，可以容納更多的元素，從而減少擴容的次數(shù)，提高效率。而在初始大小等于元素數(shù)量時，哈希表的容量通常比較小，可能需要進行多次擴容，導致效率降低。

當然，這并不是說初始大小等于元素數(shù)量就一定不好，或者初始大小為2的冪次方就一定好。具體的選擇需要根據(jù)實際情況來衡量，綜合考慮空間和時間的代價，以達到最優(yōu)的性能。

為什么，在初始大小等于元素數(shù)量的情況下，擴容所需的代價通常比較小?

在初始大小等于元素數(shù)量的情況下，如果使用默認負載因子0.75，當哈希表中的元素數(shù)量達到容量的 0.75 倍時，就會觸發(fā)擴容。此時，需要重新計算哈希值并將元素重新插入到新的更大的哈希表中，這個過程需要花費一定的時間，但是由于初始容量等于元素數(shù)量，因此擴容時所需的空間通常比較小，因此空間代價相對較小。

在初始大小為2的冪次方時，哈希表的容量通常都比較大，可以容納更多的元素，從而減少擴容的次數(shù)，提高效率。但是，如果元素數(shù)量遠小于容量，會導致空間浪費。此外，由于需要將元素重新哈希并重新插入，因此擴容時所需的時間會相對較長，因此時間代價相對較高。

因此，在選擇初始大小時，需要綜合考慮空間和時間的代價，以達到最優(yōu)的性能。如果我們知道要put的元素數(shù)量是多少，也可以直接將初始大小設置為該數(shù)量，但是需要注意元素數(shù)量和容量之間的平衡，避免空間浪費和過多的擴容操作。

假設需要put()4個元素,指定其初始大小為4，它會經(jīng)過一次擴容，那么它會擴容到多大呢？

在這個情況下，哈希表的初始大小為4，需要存儲4個元素。因為默認負載因子為0.75，所以在哈希表中存儲4個元素時，會有一個擴容操作。擴容操作會將哈希表的容量翻倍，然后將已有的元素重新分配到新的容量中，以充分利用空間。因此，哈希表在擴容后的容量為8。

具體而言，哈希表的擴容觸發(fā)條件是：當哈希表中的元素數(shù)量達到容量的0.75時，就會觸發(fā)擴容操作。在這個情況下，初始大小為4，容量為4，因此當存儲第3個元素時，哈希表的元素數(shù)量為3，容量為4，還有一個空位。但是，當存儲第4個元素時，哈希表的元素數(shù)量就達到了容量的0.75，也就是3個元素的75%。因此，哈希表觸發(fā)了一次擴容操作，容量翻倍，變?yōu)?。然后，已有的3個元素會重新分配到新的容量中，以充分利用空間。

哈希表在擴容時會將容量翻倍，因此在這個情況下，哈希表的容量從4擴容到了8，擴容了兩倍。哈希表的擴容操作是為了保證哈希表中的負載因子不超過預設的值，以提高哈希表的性能和空間利用率。在Java中，HashMap類的默認負載因子是0.75，也就是當哈希表中的元素數(shù)量達到容量的0.75時，就會觸發(fā)擴容操作，容量翻倍。

擴展：

負載因子與實際元素數(shù)據(jù)之間的計算

負載因子是指哈希表中已經(jīng)被占用的元素數(shù)量與容量的比值。例如，當哈希表容量為32，其中已經(jīng)有4個元素被占用時，負載因子就是4/32=0.125。

如果要使用負載因子為0.125，可以通過以下公式計算哈希表的容量：

容量 = 元素數(shù)量 / 負載因子

例如，如果要存儲32個元素，使用負載因子為0.125，那么哈希表的容量就應該是：

容量 = 32 / 0.125 = 256

因此，可以將哈希表的初始大小設置為256，并使用負載因子為0.125，這樣可以在不觸發(fā)擴容的情況下存儲32個元素，同時盡可能地減少空間浪費。

0.125跟默認負載因子0.75有什么關系呢？

默認負載因子0.75和負載因子0.125都是用于計算哈希表容量的參數(shù)，但是它們的取值不同，因此對哈希表的容量和擴容行為也有影響。

默認負載因子0.75表示當哈希表中的元素數(shù)量達到容量的0.75倍時，就會觸發(fā)擴容。這個值是經(jīng)驗值，根據(jù)哈希表的設計和使用場景來確定的。如果哈希表中元素數(shù)量較少，就會浪費空間；如果元素數(shù)量較多，就會引起頻繁的擴容操作，影響性能。

而負載因子0.125表示哈希表中已經(jīng)被占用的元素數(shù)量與容量的比值為0.125。如果使用這個負載因子，就需要根據(jù)元素數(shù)量計算出合適的容量，以盡可能地減少空間浪費。如果哈希表中元素數(shù)量達到容量的0.125倍時，就需要擴容。這個負載因子比默認負載因子小，因此擴容的頻率會相對較低，但是需要更大的容量，因此會占用更多的內存。

總之，負載因子是一個用于計算哈希表容量和擴容觸發(fā)條件的參數(shù)，需要根據(jù)實際需求來選擇合適的值。默認負載因子0.75適用于大多數(shù)情況，如果需要更嚴格的空間控制，可以選擇更小的負載因子。

怎么設置默認負載因子為0.125呢？

默認負載因子是哈希表實現(xiàn)中的一個參數(shù)，通常是在實現(xiàn)代碼中預先定義好的。如果要將默認負載因子從0.75修改為0.125，需要修改哈希表實現(xiàn)的源代碼。

具體而言，需要找到哈希表實現(xiàn)中關于負載因子的定義，并將其修改為0.125。例如，在Java中，可以使用HashMap類來實現(xiàn)哈希表，而HashMap類中關于負載因子的定義如下：

/**
 * The load factor for the hash table.
 *
 * @serial
 */
final float loadFactor;

其中，loadFactor是一個final類型的float變量，用于表示哈希表的負載因子。默認情況下，loadFactor的值為0.75。

要將負載因子修改為0.125，可以將HashMap類中的loadFactor定義修改為如下所示：

/**
 * The load factor for the hash table.
 *
 * @serial
 */
final float loadFactor = 0.125f;

修改后，HashMap類中的所有哈希表實例都會使用負載因子0.125來計算容量和擴容觸發(fā)條件。當然，這也可能會對HashMap的性能產(chǎn)生一定的影響，因此需要根據(jù)實際情況來選擇合適的負載因子。

如果你無法修改哈希表實現(xiàn)的源代碼

那么就無法直接修改默認負載因子。但是，你仍然可以創(chuàng)建自定義的哈希表實現(xiàn)，并在其中使用自己定義的負載因子。

例如，在Java中，你可以創(chuàng)建一個自定義的哈希表類，繼承自HashMap，并在其中重寫loadFactor字段，將其修改為0.125。示例代碼如下：

public class MyHashMap<K,V> extends HashMap<K,V> {
    private static final long serialVersionUID = 1L;
    public static final float LOAD_FACTOR = 0.125f;
    public MyHashMap() {
        super();
    }
    public MyHashMap(int initialCapacity) {
        super(initialCapacity);
    }
    public MyHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
    }
    @Override
    public float getLoadFactor() {
        return LOAD_FACTOR;
    }
}

在這個自定義的哈希表類中，我們定義了一個常量LOAD_FACTOR，用于表示負載因子的值。然后，在構造函數(shù)中，我們可以調用父類的構造函數(shù)，并傳入LOAD_FACTOR作為負載因子的值。同時，我們還重寫了getLoadFactor方法，返回LOAD_FACTOR，以確保哈希表中的負載因子始終為0.125。

使用這個自定義的哈希表類時，就可以使用負載因子0.125來計算容量和擴容觸發(fā)條件了。例如，可以創(chuàng)建一個容量為64的哈希表，存儲32個元素，代碼如下：

MyHashMap<String, Integer> map = new MyHashMap<>(64);
for (int i = 0; i < 32; i++) {
    map.put("key" + i, i);
}

這個哈希表的負載因子為0.125，可以充分利用空間，同時擴容的頻率也會相對較低。

總結

到此這篇關于Java基礎篇之HashMap指定初始值的文章就介紹到這了,更多相關Java HashMap指定初始值內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論