Java基礎(chǔ)篇之HashMap指定初始值
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)文章希望大家以后多多支持腳本之家!
相關(guān)文章
淺談mybatis 樂觀鎖實(shí)現(xiàn),解決并發(fā)問題
這篇文章主要介紹了淺談mybatis 樂觀鎖實(shí)現(xiàn),解決并發(fā)問題,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08Java 入門圖形用戶界面設(shè)計(jì)之列表框JList
圖形界面(簡稱GUI)是指采用圖形方式顯示的計(jì)算機(jī)操作用戶界面。與早期計(jì)算機(jī)使用的命令行界面相比,圖形界面對于用戶來說在視覺上更易于接受,本篇精講Java語言中關(guān)于圖形用戶界面的列表框JList2022-02-02es創(chuàng)建索引和mapping的實(shí)例
這篇文章主要介紹了es創(chuàng)建索引和mapping的實(shí)例,具有很好的參考價(jià)值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2023-02-02SpringMVC后端返回?cái)?shù)據(jù)到前端代碼示例
這篇文章主要介紹了SpringMVC后端返回?cái)?shù)據(jù)到前端代碼示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04