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