2009-12-10
HashMap是一種十分常用的數(shù)據(jù)結(jié)構(gòu)，作為一個(gè)應(yīng)用開發(fā)人員，對其原理、實(shí)現(xiàn)的加深理解有助于更高效地進(jìn)行數(shù)據(jù)存取。本文所用的jdk版本為1.5。
《Effective JAVA》中認(rèn)為，99%的情況下，當(dāng)你覆蓋了equals方法后，請務(wù)必覆蓋hashCode方法。默認(rèn)情況下，這兩者會采用Object的“原生”實(shí)現(xiàn)方式，即：
protected native int hashCode();public boolean equals(Object obj) {return (this == obj);} hashCode方法的定義用到了native關(guān)鍵字，表示它是由C或C++采用較為底層的方式來實(shí)現(xiàn)的，你可以認(rèn)為它返回了該對象的內(nèi)存地址；而缺省equals則認(rèn)為，只有當(dāng)兩者引用同一個(gè)對象時(shí)，才認(rèn)為它們是相等的。如果你只是覆蓋了equals()而沒有重新定義hashCode()，在讀取HashMap的時(shí)候，除非你使用一個(gè)與你保存時(shí)引用完全相同的對象作為key值，否則你將得不到該key所對應(yīng)的值。
另一方面，你應(yīng)該盡量避免使用“可變”的類作為HashMap的鍵。如果你將一個(gè)對象作為鍵值并保存在HashMap中，之后又改變了其狀態(tài)，那么HashMap就會產(chǎn)生混亂，你所保存的值可能丟失（盡管遍歷集合可能可以找到）。
Hashmap實(shí)際上是一個(gè)數(shù)組和鏈表的結(jié)合體，利用數(shù)組來模擬一個(gè)個(gè)桶（類似于Bucket Sort）以快速存取不同hashCode的key，對于相同hashCode的不同key，再調(diào)用其equals方法從List中提取出和key所相對應(yīng)的value。
Java中hashMap的初始化主要是為initialCapacity和loadFactor這兩個(gè)屬性賦值。前者表示hashMap中用來區(qū)分不同hash值的key空間長度，后者是指定了當(dāng)hashMap中的元素超過多少的時(shí)候，開始自動擴(kuò)容，。默認(rèn)情況下initialCapacity為16，loadFactor為0.75，它表示一開始hashMap可以存放16個(gè)不同的hashCode，當(dāng)填充到第12個(gè)的時(shí)候，hashMap會自動將其key空間的長度擴(kuò)容到32，以此類推；這點(diǎn)可以從源碼中看出來：
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);} 而每當(dāng)hashMap擴(kuò)容后，內(nèi)部的每個(gè)元素存放的位置都會發(fā)生變化（因?yàn)樵氐淖罱K位置是其hashCode對key空間長度取模而得），因此resize方法中又會調(diào)用transfer函數(shù)，用來重新分配內(nèi)部的元素；這個(gè)過程成為rehash，是十分消耗性能的，因此在可預(yù)知元素的個(gè)數(shù)的情況下，一般應(yīng)該避免使用缺省的initialCapacity，而是通過構(gòu)造函數(shù)為其指定一個(gè)值。例如我們可能會想要將數(shù)據(jù)庫查詢所得1000條記錄以某個(gè)特定字段（比如ID）為key緩存在hashMap中，為了提高效率、避免rehash，可以直接指定initialCapacity為2048。
另一個(gè)值得注意的地方是，hashMap其key空間的長度一定為2的N次方，這一點(diǎn)可以從一下源碼中看出來：
int capacity = 1;while (capacity < initialCapacity)capacity <<= 1;
即使我們在構(gòu)造函數(shù)中指定的initialCapacity不是2的平方數(shù)，capacity還是會被賦值為2的N次方。
為什么Sun Microsystem的工程師要將hashMap key空間的長度設(shè)為2的N次方呢？這里參考R.W.Floyed給出的衡量散列思想的三個(gè)標(biāo)準(zhǔn)： 一個(gè)好的hash算法的計(jì)算應(yīng)該是非?？斓模?一個(gè)好的hash算法應(yīng)該是沖突極小化， 如果存在沖突，應(yīng)該是沖突均勻化。
為了將各元素的hashCode保存至長度為Length的key數(shù)組中，一般采用取模的方式，即index = hashCode % Length。不可避免的，存在多個(gè)不同對象的hashCode被安排在同一位置，這就是我們平時(shí)所謂的“沖突”。如果僅僅是考慮元素均勻化與沖突極小化，似乎應(yīng)該將Length取為素?cái)?shù)（盡管沒有明顯的理論來支持這一點(diǎn)，但數(shù)學(xué)家們通過大量的實(shí)踐得出結(jié)論，對素?cái)?shù)取模的產(chǎn)生結(jié)果的無關(guān)性要大于其它數(shù)字）。為此，Craig Larman and Rhett Guthrie《Java Performence》中對此也大加抨擊。為了弄清楚這個(gè)問題，Bruce Eckel（Thinking in JAVA的作者）專程采訪了java.util.hashMap的作者Joshua Bloch，并將他采用這種設(shè)計(jì)的原因放到了網(wǎng)上（http://www.roseindia.net/javatutorials/javahashmap.shtml） 。
上述設(shè)計(jì)的原因在于，取模運(yùn)算在包括Java在內(nèi)的大多數(shù)語言中的效率都十分低下，而當(dāng)除數(shù)為2的N次方時(shí)，取模運(yùn)算將退化為最簡單的位運(yùn)算，其效率明顯提升（按照Bruce Eckel給出的數(shù)據(jù)，大約可以提升5～8倍） ?？纯碕DK中是如何實(shí)現(xiàn)的：
static int indexFor(int h, int length) {return h & (length-1);} 當(dāng)key空間長度為2的N次方時(shí)，計(jì)算hashCode為h的元素的索引可以用簡單的與操作來代替笨拙的取模操作！假設(shè)某個(gè)對象的hashCode為35（二進(jìn)制為100011），而hashMap采用默認(rèn)的initialCapacity（16），那么indexFor計(jì)算所得結(jié)果將會是100011 & 1111 = 11，即十進(jìn)制的3，是不是恰好是35 Mod 16。
上面的方法有一個(gè)問題，就是它的計(jì)算結(jié)果僅有對象hashCode的低位決定，而高位被統(tǒng)統(tǒng)屏蔽了；以上面為例，19（10011）、35（100011）、67（1000011）等就具有相同的結(jié)果。針對這個(gè)問題， Joshua Bloch采用了“防御性編程”的解決方法，在使用各對象的hashCode之前對其進(jìn)行二次Hash，參看JDK中的源碼：
static int hash(Object x) {int h = x.hashCode();h += ~(h << 9);h ^= (h >>> 14);h += (h << 4);h ^= (h >>> 10);return h;} 采用這種旋轉(zhuǎn)Hash函數(shù)的主要目的是讓原有hashCode的高位信息也能被充分利用，且兼顧計(jì)算效率以及數(shù)據(jù)統(tǒng)計(jì)的特性，其具體的原理已超出了本文的領(lǐng)域。
加快Hash效率的另一個(gè)有效途徑是編寫良好的自定義對象的HashCode，String的實(shí)現(xiàn)采用了如下的計(jì)算方法：
for (int i = 0; i < len; i++) {h = 31*h + val[off++];}hash = h; 這種方法HashCode的計(jì)算方法可能最早出現(xiàn)在Brian W. Kernighan和Dennis M. Ritchie的《The C Programming Language》中，被認(rèn)為是性價(jià)比最高的算法（又被稱為times33算法，因?yàn)镃中乘數(shù)常量為33，JAVA中改為31），實(shí)際上，包括List在內(nèi)的大多數(shù)的對象都是用這種方法計(jì)算Hash值。
另一種比較特殊的hash算法稱為布隆過濾器，它以犧牲細(xì)微精度為代價(jià)，換來存儲空間的大量節(jié)儉，常用于諸如判斷用戶名重復(fù)、是否在黑名單上等等。
眾所周知，HashMap不是線程安全的集合類。但在某些容錯(cuò)能力較好的應(yīng)用中，如果你不想僅僅因?yàn)?%的可能性而去承受hashTable的同步開銷，則可以考慮利用一下HashMap的Fail-Fast機(jī)制，其具體實(shí)現(xiàn)如下：
Entry<K,V> nextEntry() {if (modCount != expectedModCount)throw new ConcurrentModificationException();……} 其中modCount為HashMap的一個(gè)實(shí)例變量，并且被聲明為volatile，表示任何線程都可以看到該變量被其它線程修改的結(jié)果（根據(jù)JVM內(nèi)存模型的優(yōu)化，每一個(gè)線程都會存一份自己的工作內(nèi)存，此工作內(nèi)存的內(nèi)容與本地內(nèi)存并非時(shí)時(shí)刻刻都同步，因此可能會出現(xiàn)線程間的修改不可見的問題） 。使用Iterator開始迭代時(shí)，會將modCount的賦值給expectedModCount，在迭代過程中，通過每次比較兩者是否相等來判斷HashMap是否在內(nèi)部或被其它線程修改。HashMap的大多數(shù)修改方法都會改變ModCount，參考下面的源碼：
public V put(K key, V value) {K k = maskNull(key);int hash = hash(k);int i = indexFor(hash, table.length);for (Entry<K,V> e = table[i]; e != null; e = e.next) {if (e.hash == hash && eq(k, e.key)) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, k, value, i);return null;} 以put方法為例，每次往HashMap中添加元素都會導(dǎo)致modCount自增。其它諸如remove、clear方法也都包含類似的操作。 從上面可以看出，HashMap所采用的Fail-Fast機(jī)制本質(zhì)上是一種樂觀鎖機(jī)制，通過檢查狀態(tài)——沒有問題則忽略——有問題則拋出異常的方式，來避免線程同步的開銷，下面給出一個(gè)在單線程環(huán)境下發(fā)生Fast-Fail的例子：
class Test {public static void main(String[] args) {java.util.HashMap<Object,String> map=new java.util.HashMap<Object,String>();map.put(new Object(), "a");map.put(new Object(), "b");java.util.Iterator<Object> it=map.keySet().iterator();while(it.hasNext()){it.next();map.put("", "");System.out.println(map.size());}} 運(yùn)行上面的代碼會拋出java.util.ConcurrentModificationException，因?yàn)樵诘^程中修改了HashMap內(nèi)部的元素導(dǎo)致modCount自增。若將上面代碼中 map.put(new Object(), "b") 這句注釋掉，程序會順利通過，因?yàn)榇藭r(shí)HashMap中只包含一個(gè)元素，經(jīng)過一次迭代后已到了尾部，所以不會出現(xiàn)問題，也就沒有拋出異常的必要了。
在通常并發(fā)環(huán)境下，還是建議采用同步機(jī)制。這一般通過對自然封裝該映射的對象進(jìn)行同步操作來完成。如果不存在這樣的對象，則應(yīng)該使用 Collections.synchronizedMap 方法來“包裝”該映射。最好在創(chuàng)建時(shí)完成這一操作，以防止意外的非同步訪問。
遍歷HashMap所得到的數(shù)據(jù)是雜亂無章的，這在某些情況下客戶需要特定遍歷順序時(shí)是十分有用的。比如，這種數(shù)據(jù)結(jié)構(gòu)很適合構(gòu)建 LRU 緩存。調(diào)用 put 或 get 方法將會訪問相應(yīng)的條目（假定調(diào)用完成后它還存在）。putAll 方法以指定映射的條目集合迭代器提供的鍵-值映射關(guān)系的順序，為指定映射的每個(gè)映射關(guān)系生成一個(gè)條目訪問。Sun提供的J2SE說明文檔特別規(guī)定任何其他方法均不生成條目訪問，尤其，collection 集合類的操作不會影響底層映射的迭代順序。
LinkedHashMap的實(shí)現(xiàn)與 HashMap 的不同之處在于，前者維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序通常就是集合中元素的插入順序。該類定義了header、before與after三個(gè)屬性來表示該集合類的頭與前后“指針”，其具體用法類似于數(shù)據(jù)結(jié)構(gòu)中的雙鏈表，以刪除某個(gè)元素為例：
private void remove() {before.after = after;after.before = before;} 實(shí)際上就是改變前后指針?biāo)赶虻脑亍?
顯然，由于增加了維護(hù)鏈接列表的開支，其性能要比 HashMap 稍遜一籌，不過有一點(diǎn)例外：LinkedHashMap的迭代所需時(shí)間與其的所包含的元素成比例；而HashMap 迭代時(shí)間很可能開支較大，因?yàn)樗枰臅r(shí)間與其容量（分配給Key空間的長度）成比例。一言以蔽之，隨機(jī)存取用HashMap，順序存取或是遍歷用LinkedHashMap。
LinkedHashMap還重寫了removeEldestEntry方法以實(shí)現(xiàn)自動清除過期數(shù)據(jù)的功能，這在HashMap中是無法實(shí)現(xiàn)的，因?yàn)楹笳咂鋬?nèi)部的元素是無序的。默認(rèn)情況下，LinkedHashMap中的removeEldestEntry的作用被關(guān)閉，其具體實(shí)現(xiàn)如下：
