基礎(chǔ)很重要哦...
1. HashMap工作原理：
HashMap是基于Hash表的Map接口的非同步實(shí)現(xiàn)。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null作為鍵和值。無序。
2. HashMap數(shù)據(jù)結(jié)構(gòu)：
HashMap實(shí)際上是一個(gè)“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)，即是數(shù)組和鏈表的結(jié)合體。HashMap底層就是個(gè)數(shù)組結(jié)構(gòu)，數(shù)組的每一項(xiàng)是一個(gè)鏈表。當(dāng)新建一個(gè)HashMap時(shí)，就會(huì)新創(chuàng)建一個(gè)數(shù)組。
Java代碼：
| /** * 長(zhǎng)度擴(kuò)容必須是2的倍數(shù) */ transient Entry[] table; static class Entry<K,V> implements Map.Entry<K,V> { final K key; V value; Entry<K,V> next; final int hash; … … public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; init(); } |
可以看到，每個(gè)Entry就是一個(gè)鍵值對(duì)，本身對(duì)象持有下一個(gè)對(duì)象的引用，這樣就構(gòu)成了鏈表。
為了元素在HashMap中均勻分布，通常想到的是把hashCode對(duì)數(shù)組長(zhǎng)度取模運(yùn)算，但是取模運(yùn)算的消耗比較大，那么HashMap做法是根據(jù)key算的的hashCode跟數(shù)組-1進(jìn)行“與”運(yùn)算(&)。
將初始大小設(shè)置為16的原因(當(dāng)擴(kuò)容是必須是2的整數(shù)次冪)：主要為了使HashMap的訪問的性能最高，減少key在bucket中存取時(shí)的碰撞幾率。
3. HashMap的resize：
當(dāng)HashMap的元素越來越多時(shí)，碰撞的幾率就越來越高，因?yàn)閿?shù)組的長(zhǎng)度初始時(shí)是固定的，所以為了提高查詢的效率，就要對(duì)HashMap的數(shù)組進(jìn)行擴(kuò)容，在HashMap數(shù)組擴(kuò)容后最消耗性能點(diǎn)是：原數(shù)組中的元素必須重新計(jì)算在新數(shù)組中的位置，然后存放進(jìn)去。
什么時(shí)候擴(kuò)容？
當(dāng)HashMap中的元素個(gè)數(shù)超過數(shù)組大小*負(fù)載因子的時(shí)，會(huì)進(jìn)行數(shù)組擴(kuò)容，默認(rèn)的loadFactor是0.75（意思是當(dāng)一個(gè)Map填滿了75%bucket的時(shí)），也就是當(dāng)為12（16*0.75），就會(huì)把數(shù)組擴(kuò)容原來大小的兩倍：16*2=32。然后重新計(jì)算每個(gè)元素在數(shù)組中的位置（此時(shí)比較消耗性能了）。 這個(gè)過程也叫做rehashing（因?yàn)樗{(diào)用了hash方法找到新bucket的位置）。
建議當(dāng)我們已預(yù)知了數(shù)組的元素個(gè)數(shù)，可根據(jù)具體需求自行設(shè)置數(shù)組初始容量以便提高查詢性能。但是要記得考慮“&”的問題。這樣也解決了resize的問題。
4. HashMap的存取實(shí)現(xiàn)：
put方法分析：
如果傳入key為null值，則將其放倒數(shù)組的第一個(gè)位置。如果key不為空，首先對(duì)key調(diào)用hashCode方法，對(duì)返回的hashCode值做hash，通過計(jì)算hash值可以找到bucket(這個(gè)bucket就是指Entry數(shù)組)位置(下標(biāo))來存儲(chǔ)Entry對(duì)象。
| public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { 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++; addEntry(hash, key, value, i); return null; } |
雖然發(fā)生碰撞的幾率較小，但是如果發(fā)生碰撞，則會(huì)將新添加的元素放倒鏈表頭部，早先加入的元素放倒鏈表尾部（我們可以將發(fā)生碰撞的這個(gè)鏈表理解為LinkedList，這個(gè)LinkedList中存儲(chǔ)了鍵值對(duì)形式的Map.Entry對(duì)象）。
| 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) resize(2 * table.length); } |
get方法：
調(diào)用get方法時(shí)，首先會(huì)根據(jù)傳入的key調(diào)用hashCode方法，計(jì)算hash值找到bucket位置，然后遍歷鏈表（即上面所說的linkedList<Entry<K,V>>），判斷hash和key的equals方法查找到對(duì)應(yīng)的Entry對(duì)象。
| public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } |
最佳實(shí)踐方式：
使用不可變的、聲明作final的對(duì)象，并且采用合適的equals()和hashCode()方法的話，將會(huì)減少碰撞的發(fā)生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個(gè)獲取對(duì)象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。
參考:http://www.importnew.com/7099.html
posted on 2013-11-18 18:01
David1228 閱讀(2901)
評(píng)論(4) 編輯 收藏 所屬分類:
JAVA