—HashMap—
創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司是一家服務(wù)多年做網(wǎng)站建設(shè)策劃設(shè)計(jì)制作的公司,為廣大用戶提供了成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè),成都網(wǎng)站設(shè)計(jì),1元廣告,成都做網(wǎng)站選創(chuàng)新互聯(lián),貼合企業(yè)需求,高性價(jià)比,滿足客戶不同層次的需求一站式服務(wù)歡迎致電。
優(yōu)點(diǎn):超級(jí)快速的查詢速度,時(shí)間復(fù)雜度可以達(dá)到O(1)的數(shù)據(jù)結(jié)構(gòu)非HashMap莫屬。動(dòng)態(tài)的可變長(zhǎng)存儲(chǔ)數(shù)據(jù)(相對(duì)于數(shù)組而言)。
缺點(diǎn):需要額外計(jì)算一次hash值,如果處理不當(dāng)會(huì)占用額外的空間。
—HashMap如何使用—
平時(shí)我們使用hashmap如下
Map<Integer,String> maps=new HashMap<Integer,String>(); maps.put(1, "a"); maps.put(2, "b");
上面代碼新建了一個(gè)HashMap并且插入了兩個(gè)數(shù)據(jù),這里不接受基本數(shù)據(jù)類型來做K,V
如果這么寫的話,就會(huì)出問題了:
Map<int,double> maps=new HashMap<int,double>();
我們?yōu)槭裁匆@樣使用呢?請(qǐng)看源碼:
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
這是HashMap實(shí)現(xiàn)類的定義。
—HashMap是一個(gè)動(dòng)態(tài)變長(zhǎng)的數(shù)據(jù)結(jié)構(gòu)—
在使用HashMap的時(shí)候,為了提高執(zhí)行效率,我們往往會(huì)設(shè)置HashMap初始化容量:
Map<String,String> rm=new HashMap<String,String>(2)
或者使用guava的工具類Maps,可以很方便的創(chuàng)建一個(gè)集合,并且,帶上合適的大小初始化值。
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 //默認(rèn)加載因子,如果不制定的話是0.75 DEFAULT_INITIAL_CAPACITY //默認(rèn)初始化容量,默認(rèn)是16 threshold //閾(yu)值 根據(jù)加載因子和初始化容量計(jì)算得出 ,<span microsoft yahei";">threshold表示當(dāng)HashMap的size大于threshold時(shí)會(huì)執(zhí)行resize操作。
因此我們知道了,如果我們調(diào)用無參數(shù)的構(gòu)造方法的話,我們將得到一個(gè)16容量的數(shù)組。
所以問題就來了:如果初始容量不夠怎么辦?
數(shù)組是定長(zhǎng)的,如何用一個(gè)定長(zhǎng)的數(shù)據(jù)來表示一個(gè)不定長(zhǎng)的數(shù)據(jù)呢,答案就是找一個(gè)更長(zhǎng)的,但是在resize的時(shí)候是很降低效率的。所以我們建議HashMap的初始化的時(shí)候要給一個(gè)靠譜的容量大小。
—HashMap的Put方法—
public V put(K key, V value) { if (key == null) //鍵為空的情況,HashMap和HashTable的一個(gè)區(qū)別 return putForNullKey(value); int hash = hash(key.hashCode()); //根據(jù)鍵的hashCode算出hash值 int i = indexFor(hash, table.length); //根據(jù)hash值算出究竟該放入哪個(gè)數(shù)組下標(biāo)中 for (Entry<K,V> e = table[i]; e != null; e = e.next) {//整個(gè)for循環(huán)實(shí)現(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++;//計(jì)數(shù)器 addEntry(hash, key, value, i); //添加到數(shù)組中 return null; }
如果插入的數(shù)據(jù)超過現(xiàn)有容量就會(huì)執(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 ><strong> resize(2 * table.length); }
這里顯示了如果當(dāng)前 size++ >threshold 的話那么就會(huì)擴(kuò)展當(dāng)前的size的兩倍,執(zhí)行resize(2*table.length),那么他們是如何擴(kuò)展的呢?
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 >new 一個(gè)新的數(shù)組,</span> <strong> <span >transfer(newTable);</span> </strong> //將就數(shù)組轉(zhuǎn)移到新的數(shù)組中 table = newTable; threshold = (int)(newCapacity * loadFactor); //重新計(jì)算容量 }
對(duì)于轉(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 >indexFor(e.hash, newCapacity); //根據(jù)hash值個(gè)容量重新計(jì)算下標(biāo)</span></strong> e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } }
—hashmap擴(kuò)容額外執(zhí)行次數(shù)—
因此如果我們要添加一個(gè)1000個(gè)元素的hashMap,如果我們用默認(rèn)值那么我么需要額外的計(jì)算多少次呢
當(dāng)大于16*0.75=12的時(shí)候,需要從新計(jì)算12次
當(dāng)大于16*2*0.75=24的時(shí)候,需要額外計(jì)算24次
……
當(dāng)大于16*n*0.75=768的時(shí)候,需要額外計(jì)算768次
所以我們總共在擴(kuò)充過程中額外計(jì)算12+24+48+……+768次
因此強(qiáng)力建議我們?cè)陧?xiàng)目中如果知道范圍的情況下,我們應(yīng)該手動(dòng)指定初始大小像這樣:
Map<Integer,String> maps=new HashMap<Integer,String>(1000);
總結(jié):這就是為什么當(dāng)hashmap使用過程中如果超出 初始容量后他的執(zhí)行效率嚴(yán)重下降的原因。
以上就是本文關(guān)于Java源碼角度分析HashMap用法的全部?jī)?nèi)容,希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題,如有不足之處,歡迎留言指出。感謝朋友們對(duì)本站的支持!
分享名稱:Java源碼角度分析HashMap用法
鏈接分享:http://chinadenli.net/article30/gisdso.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供用戶體驗(yàn)、網(wǎng)站營(yíng)銷、自適應(yīng)網(wǎng)站、云服務(wù)器、建站公司、定制開發(fā)
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)