Java源碼角度分析HashMap用法
—HashMap—
優(yōu)點：超級快速的查詢速度，時間復雜度可以達到O（1）的數(shù)據(jù)結(jié)構(gòu)非HashMap莫屬。動態(tài)的可變長存儲數(shù)據(jù)（相對于數(shù)組而言）。
缺點：需要額外計算一次hash值，如果處理不當會占用額外的空間。
—HashMap如何使用—
平時我們使用hashmap如下
Map<Integer,String> maps=new HashMap<Integer,String>(); maps.put(1, "a"); maps.put(2, "b");
上面代碼新建了一個HashMap并且插入了兩個數(shù)據(jù)，這里不接受基本數(shù)據(jù)類型來做K,V
如果這么寫的話，就會出問題了：
Map<int,double> maps=new HashMap<int,double>();
我們?yōu)槭裁匆@樣使用呢？請看源碼：
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
這是HashMap實現(xiàn)類的定義。
—HashMap是一個動態(tài)變長的數(shù)據(jù)結(jié)構(gòu)—
在使用HashMap的時候，為了提高執(zhí)行效率，我們往往會設置HashMap初始化容量：
Map<String,String> rm=new HashMap<String,String>(2)
或者使用guava的工具類Maps，可以很方便的創(chuàng)建一個集合，并且，帶上合適的大小初始化值。
Map<String, Object> map = Maps.newHashMapWithExpectedSize(7);
那么為什么要這樣使用呢？我們來看他們的源碼構(gòu)造函數(shù)。
未帶參的構(gòu)造函數(shù)：
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
名詞解釋：
DEFAULT_LOAD_FACTOR //默認加載因子，如果不制定的話是0.75 DEFAULT_INITIAL_CAPACITY //默認初始化容量，默認是16 threshold //閾（yu）值 根據(jù)加載因子和初始化容量計算得出 ，<span style="color: rgb(54, 46, 43); font-family: "microsoft yahei";">threshold表示當HashMap的size大于threshold時會執(zhí)行resize操作。
因此我們知道了，如果我們調(diào)用無參數(shù)的構(gòu)造方法的話，我們將得到一個16容量的數(shù)組。
所以問題就來了：如果初始容量不夠怎么辦？
數(shù)組是定長的，如何用一個定長的數(shù)據(jù)來表示一個不定長的數(shù)據(jù)呢，答案就是找一個更長的，但是在resize的時候是很降低效率的。所以我們建議HashMap的初始化的時候要給一個靠譜的容量大小。
—HashMap的Put方法—
public V put(K key, V value) {
if (key == null) //鍵為空的情況，HashMap和HashTable的一個區(qū)別
return putForNullKey(value);
int hash = hash(key.hashCode()); //根據(jù)鍵的hashCode算出hash值
int i = indexFor(hash, table.length); //根據(jù)hash值算出究竟該放入哪個數(shù)組下標中
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//整個for循環(huán)實現(xiàn)了如果存在K那么就替換V
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;//計數(shù)器
addEntry(hash, key, value, i); //添加到數(shù)組中
return null;
}
如果插入的數(shù)據(jù)超過現(xiàn)有容量就會執(zhí)行
addEntry(hash, key, value, i);
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
<span style="color:#ff0000;"><strong> resize(2 * table.length);
}
這里顯示了如果當前 size++ >threshold 的話那么就會擴展當前的size的兩倍，執(zhí)行resize（2*table.length）,那么他們是如何擴展的呢？
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity]; <span style="color: rgb(51, 51, 51); font-family: Arial;">new 一個新的數(shù)組，</span>
<strong> <span style="color:#ff0000;">transfer(newTable);</span> </strong> //將就數(shù)組轉(zhuǎn)移到新的數(shù)組中
table = newTable;
threshold = (int)(newCapacity * loadFactor); //重新計算容量
}
對于轉(zhuǎn)移數(shù)組transfer是如何轉(zhuǎn)移的呢？
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = <strong><span style="color:#ff0000;">indexFor(e.hash, newCapacity); //根據(jù)hash值個容量重新計算下標</span></strong>
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
—hashmap擴容額外執(zhí)行次數(shù)—
因此如果我們要添加一個1000個元素的hashMap，如果我們用默認值那么我么需要額外的計算多少次呢
當大于16*0.75=12的時候，需要從新計算12次
當大于16*2*0.75=24的時候，需要額外計算24次
……
當大于16*n*0.75=768的時候，需要額外計算768次
所以我們總共在擴充過程中額外計算12+24+48+……+768次
因此強力建議我們在項目中如果知道范圍的情況下，我們應該手動指定初始大小像這樣：
Map<Integer,String> maps=new HashMap<Integer,String>(1000);
總結(jié)：這就是為什么當hashmap使用過程中如果超出 初始容量后他的執(zhí)行效率嚴重下降的原因。
以上就是本文關于Java源碼角度分析HashMap用法的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
相關文章
這篇文章主要為大家介紹了Java?C++刷題leetcode1106解析布爾表達式示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-01-01
這篇文章主要介紹了Java中多態(tài)性的實現(xiàn)方式，什么是多態(tài)？通過簡單的一道題目幫大家理解java多態(tài)性，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-09-09
這篇文章主要介紹了Spring Boot支持HTTPS步驟詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-09-09
Spring用AspectJ開發(fā)AOP(基于Annotation)
這篇文章主要介紹了Spring用AspectJ開發(fā)AOP(基于Annotation),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-10-10
Jpa 如何使用@EntityListeners 實現(xiàn)實體對象的自動賦值
這篇文章主要介紹了Jpa 如何使用@EntityListeners 實現(xiàn)實體對象的自動賦值，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
這篇文章主要通過幾個例題為大家詳細介紹一些Java動態(tài)規(guī)劃中的線性DP，文中的示例代碼講解詳細，對我們學習Java有一定的幫助，需要的可以參考一下2022-11-11
MybatisPlus更新為null的字段及自定義sql注入
mybatis-plus在執(zhí)行更新操作,當更新字段為空字符串或者null的則不會執(zhí)行更新,本文主要介紹了MybatisPlus更新為null的字段及自定義sql注入,感興趣的可以了解一下2024-05-05
Java 多線程并發(fā)AbstractQueuedSynchronizer詳情
這篇文章主要介紹了Java 多線程并發(fā)AbstractQueuedSynchronizer詳情，文章圍繞主題展開想象的內(nèi)容介紹，具有一定的參考價值，感興趣的小伙伴可以參考一下2022-06-06
IDEA啟動Tomcat報Unrecognized option: --add-opens=java
這篇文章主要為大家介紹了解決IDEA啟動Tomcat報Unrecognized option: --add-opens=java.base/java.lang=ALL-UNNAMED的方法,文中通過圖文介紹的非常詳細,需要的朋友可以參考下2023-08-08
idea hibernate jpa 生成實體類的實現(xiàn)
這篇文章主要介紹了idea hibernate jpa 生成實體類的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-11-11