Java基礎篇之HashMap指定初始值
HashMap為什么要指定初始大???
在Java中,HashMap
是一種基于哈希表實現(xiàn)的鍵值對存儲結構。哈希表是一種典型的散列表,它通過哈希函數(shù)將任意長度的鍵值對映射到一個固定長度的數(shù)組中,然后使用鏈表或紅黑樹等數(shù)據(jù)結構來解決哈希沖突。
在HashMap
中,指定初始大小的作用是為了減少哈希沖突,提高存儲效率和查詢效率。當哈希表大小不足時,HashMap
會自動擴容,但這個過程比較耗時,因為需要重新計算鍵值對的哈希值,重新分配內(nèi)存空間,重新插入鍵值對等。如果預估好數(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ù)實際情況調(diào)整初始大小和負載因子。具體的值需要根據(jù)實際場景進行調(diào)整,以達到最優(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倍時,就需要擴容。這個負載因子比默認負載因子小,因此擴容的頻率會相對較低,但是需要更大的容量,因此會占用更多的內(nèi)存。
總之,負載因子是一個用于計算哈希表容量和擴容觸發(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ù)中,我們可以調(diào)用父類的構造函數(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指定初始值內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
淺談mybatis 樂觀鎖實現(xiàn),解決并發(fā)問題
這篇文章主要介紹了淺談mybatis 樂觀鎖實現(xiàn),解決并發(fā)問題,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08SpringMVC后端返回數(shù)據(jù)到前端代碼示例
這篇文章主要介紹了SpringMVC后端返回數(shù)據(jù)到前端代碼示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-04-04