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

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

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

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

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

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

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

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

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

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

怎么保證不會擴(kuò)容呢？

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

那為什么要設(shè)置這么大而不是設(shè)置8？

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

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

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

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

確實(shí)，如果我們知道要put的元素?cái)?shù)量是多少，也可以直接將初始大小設(shè)置為該數(shù)量。在這種情況下，如果使用默認(rèn)負(fù)載因子0.75，當(dāng)哈希表中的元素?cái)?shù)量達(dá)到容量的 0.75 倍時(shí)，就會觸發(fā)擴(kuò)容，從而浪費(fèi)一些空間。但是，這里需要注意的是，在初始大小等于元素?cái)?shù)量的情況下，擴(kuò)容所需的代價(jià)通常比較小，因?yàn)槿匀挥凶銐虻目臻g可以容納元素。

如果我們比較在初始大小等于元素?cái)?shù)量和初始大小為2的冪次方時(shí)的空間浪費(fèi)和時(shí)間代價(jià)，通常情況下，后者會更少。因?yàn)樵诔跏即笮?的冪次方時(shí)，哈希表的容量通常都比較大，可以容納更多的元素，從而減少擴(kuò)容的次數(shù)，提高效率。而在初始大小等于元素?cái)?shù)量時(shí)，哈希表的容量通常比較小，可能需要進(jìn)行多次擴(kuò)容，導(dǎo)致效率降低。

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

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

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

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

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

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

在這個情況下，哈希表的初始大小為4，需要存儲4個元素。因?yàn)槟J(rèn)負(fù)載因子為0.75，所以在哈希表中存儲4個元素時(shí)，會有一個擴(kuò)容操作。擴(kuò)容操作會將哈希表的容量翻倍，然后將已有的元素重新分配到新的容量中，以充分利用空間。因此，哈希表在擴(kuò)容后的容量為8。

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

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

擴(kuò)展：

負(fù)載因子與實(shí)際元素?cái)?shù)據(jù)之間的計(jì)算

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

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

容量 = 元素?cái)?shù)量 / 負(fù)載因子

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

容量 = 32 / 0.125 = 256

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

0.125跟默認(rèn)負(fù)載因子0.75有什么關(guān)系呢？

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

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

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

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

怎么設(shè)置默認(rèn)負(fù)載因子為0.125呢？

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

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

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

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

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

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

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

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

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

例如，在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，用于表示負(fù)載因子的值。然后，在構(gòu)造函數(shù)中，我們可以調(diào)用父類的構(gòu)造函數(shù)，并傳入LOAD_FACTOR作為負(fù)載因子的值。同時(shí)，我們還重寫了getLoadFactor方法，返回LOAD_FACTOR，以確保哈希表中的負(fù)載因子始終為0.125。

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

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

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

總結(jié)

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

最新評論