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í)行效率嚴重下降的原因。
以上就是本文關(guān)于Java源碼角度分析HashMap用法的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
相關(guān)文章
這篇文章主要介紹了java Lambda表達式的使用心得，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-10-10
這篇文章主要介紹了怎么用Java來寫一個銀行的存款系統(tǒng)，銀行存款主要有賬號和存款金額兩個屬性，感興趣的朋友跟隨文章往下看看吧2022-03-03
這篇文章主要介紹了SpringBoot中的PUT和Delete請求使用，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要介紹了Java檢查非空的三種方法總結(jié)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
java多線程并發(fā)中使用Lockers類將多線程共享資源鎖定
Lockers在多線程編程里面一個重要的概念是鎖定，如果一個資源是多個線程共享的，為了保證數(shù)據(jù)的完整性，在進行事務性操作時需要將共享資源鎖定，這樣可以保證在做事務性操作時只有一個線程能對資源進行操作，下面看一個示例2014-01-01
這篇文章主要介紹了Java?POI?excel設置單元格格式，自定義設置,設置單元格格式：來源_formats，更多數(shù)據(jù)類型從formats里面發(fā)現(xiàn)，需要的朋友可以參考下2024-01-01
java面向?qū)ο缶幊讨匾拍罾^承和多態(tài)示例解析
這篇文章主要為大家介紹了java面向?qū)ο缶幊痰膬蓚€重要概念繼承和多態(tài)示例解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-05-05
Java使用agent實現(xiàn)main方法之前的實例詳解
這篇文章主要介紹了Java使用agent實現(xiàn)main方法之前的實例詳解的相關(guān)資料,希望通過本文能幫助到大家，讓大家理解這部分內(nèi)容，需要的朋友可以參考下2017-10-10
今天小編就為大家分享一篇關(guān)于elasticsearch kibana簡單查詢講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-02-02
最近在搗鼓?SpringBoot?與?Vue?整合的項目,所以下面這篇文章主要給大家介紹了關(guān)于如何通過一篇文章教會你搭建vue+springboot項目,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-05-05