存取之美——HashMap原理與實(shí)踐

2009-12-10

HashMap是一種十分常用的數(shù)據(jù)結(jié)構(gòu)，作為一個(gè)應(yīng)用開(kāi)發(fā)人員，對(duì)其原理、實(shí)現(xiàn)的加深理解有助于更高效地進(jìn)行數(shù)據(jù)存取。本文所用的jdk版本為1.5。

使用HashMap

《Effective JAVA》中認(rèn)為，99%的情況下，當(dāng)你覆蓋了equals方法后，請(qǐng)務(wù)必覆蓋hashCode方法。默認(rèn)情況下，這兩者會(huì)采用Object的“原生”實(shí)現(xiàn)方式，即：

protected native int hashCode();
public boolean equals(Object obj) {
return (this == obj);
}  

hashCode方法的定義用到了native關(guān)鍵字，表示它是由C或C++采用較為底層的方式來(lái)實(shí)現(xiàn)的，你可以認(rèn)為它返回了該對(duì)象的內(nèi)存地址；而缺省equals則認(rèn)為，只有當(dāng)兩者引用同一個(gè)對(duì)象時(shí)，才認(rèn)為它們是相等的。如果你只是覆蓋了equals()而沒(méi)有重新定義hashCode()，在讀取HashMap的時(shí)候，除非你使用一個(gè)與你保存時(shí)引用完全相同的對(duì)象作為key值，否則你將得不到該key所對(duì)應(yīng)的值。

另一方面，你應(yīng)該盡量避免使用“可變”的類(lèi)作為HashMap的鍵。如果你將一個(gè)對(duì)象作為鍵值并保存在HashMap中，之后又改變了其狀態(tài)，那么HashMap就會(huì)產(chǎn)生混亂，你所保存的值可能丟失（盡管遍歷集合可能可以找到）。

HashMap存取機(jī)制

Hashmap實(shí)際上是一個(gè)數(shù)組和鏈表的結(jié)合體，利用數(shù)組來(lái)模擬一個(gè)個(gè)桶（類(lèi)似于Bucket Sort）以快速存取不同hashCode的key，對(duì)于相同hashCode的不同key，再調(diào)用其equals方法從List中提取出和key所相對(duì)應(yīng)的value。

Java中hashMap的初始化主要是為initialCapacity和loadFactor這兩個(gè)屬性賦值。前者表示hashMap中用來(lái)區(qū)分不同hash值的key空間長(zhǎng)度，后者是指定了當(dāng)hashMap中的元素超過(guò)多少的時(shí)候，開(kāi)始自動(dòng)擴(kuò)容，。默認(rèn)情況下initialCapacity為16，loadFactor為0.75，它表示一開(kāi)始hashMap可以存放16個(gè)不同的hashCode，當(dāng)填充到第12個(gè)的時(shí)候，hashMap會(huì)自動(dòng)將其key空間的長(zhǎng)度擴(kuò)容到32，以此類(lèi)推；這點(diǎn)可以從源碼中看出來(lá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)
resize(2 * table.length);
}    

而每當(dāng)hashMap擴(kuò)容后，內(nèi)部的每個(gè)元素存放的位置都會(huì)發(fā)生變化（因?yàn)樵氐淖罱K位置是其hashCode對(duì)key空間長(zhǎng)度取模而得），因此resize方法中又會(huì)調(diào)用transfer函數(shù)，用來(lái)重新分配內(nèi)部的元素；這個(gè)過(guò)程成為rehash，是十分消耗性能的，因此在可預(yù)知元素的個(gè)數(shù)的情況下，一般應(yīng)該避免使用缺省的initialCapacity，而是通過(guò)構(gòu)造函數(shù)為其指定一個(gè)值。例如我們可能會(huì)想要將數(shù)據(jù)庫(kù)查詢(xún)所得1000條記錄以某個(gè)特定字段（比如ID）為key緩存在hashMap中，為了提高效率、避免rehash，可以直接指定initialCapacity為2048。

另一個(gè)值得注意的地方是，hashMap其key空間的長(zhǎng)度一定為2的N次方，這一點(diǎn)可以從一下源碼中看出來(lái)：

int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;    

即使我們?cè)跇?gòu)造函數(shù)中指定的initialCapacity不是2的平方數(shù)，capacity還是會(huì)被賦值為2的N次方。

為什么Sun Microsystem的工程師要將hashMap key空間的長(zhǎng)度設(shè)為2的N次方呢？這里參考R.W.Floyed給出的衡量散列思想的三個(gè)標(biāo)準(zhǔn)： 一個(gè)好的hash算法的計(jì)算應(yīng)該是非?？斓?， 一個(gè)好的hash算法應(yīng)該是沖突極小化， 如果存在沖突，應(yīng)該是沖突均勻化。

為了將各元素的hashCode保存至長(zhǎng)度為L(zhǎng)ength的key數(shù)組中，一般采用取模的方式，即index = hashCode % Length。不可避免的，存在多個(gè)不同對(duì)象的hashCode被安排在同一位置，這就是我們平時(shí)所謂的“沖突”。如果僅僅是考慮元素均勻化與沖突極小化，似乎應(yīng)該將Length取為素?cái)?shù)（盡管沒(méi)有明顯的理論來(lái)支持這一點(diǎn)，但數(shù)學(xué)家們通過(guò)大量的實(shí)踐得出結(jié)論，對(duì)素?cái)?shù)取模的產(chǎn)生結(jié)果的無(wú)關(guān)性要大于其它數(shù)字）。為此，Craig Larman and Rhett Guthrie《Java Performence》中對(duì)此也大加抨擊。為了弄清楚這個(gè)問(wèn)題，Bruce Eckel（Thinking in JAVA的作者）專(zhuān)程采訪了java.util.hashMap的作者Joshua Bloch，并將他采用這種設(shè)計(jì)的原因放到了網(wǎng)上（http://www./javatutorials/javahashmap.shtml） 。

上述設(shè)計(jì)的原因在于，取模運(yùn)算在包括Java在內(nèi)的大多數(shù)語(yǔ)言中的效率都十分低下，而當(dāng)除數(shù)為2的N次方時(shí)，取模運(yùn)算將退化為最簡(jiǎ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空間長(zhǎng)度為2的N次方時(shí)，計(jì)算hashCode為h的元素的索引可以用簡(jiǎn)單的與操作來(lái)代替笨拙的取模操作！假設(shè)某個(gè)對(duì)象的hashCode為35（二進(jìn)制為100011），而hashMap采用默認(rèn)的initialCapacity（16），那么indexFor計(jì)算所得結(jié)果將會(huì)是100011 & 1111 = 11，即十進(jìn)制的3，是不是恰好是35 Mod 16。

上面的方法有一個(gè)問(wèn)題，就是它的計(jì)算結(jié)果僅有對(duì)象hashCode的低位決定，而高位被統(tǒng)統(tǒng)屏蔽了；以上面為例，19（10011）、35（100011）、67（1000011）等就具有相同的結(jié)果。針對(duì)這個(gè)問(wèn)題， Joshua Bloch采用了“防御性編程”的解決方法，在使用各對(duì)象的hashCode之前對(duì)其進(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è)有效途徑是編寫(xiě)良好的自定義對(duì)象的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)為是性?xún)r(jià)比最高的算法（又被稱(chēng)為times33算法，因?yàn)镃中乘數(shù)常量為33，JAVA中改為31），實(shí)際上，包括List在內(nèi)的大多數(shù)的對(duì)象都是用這種方法計(jì)算Hash值。

另一種比較特殊的hash算法稱(chēng)為布隆過(guò)濾器，它以犧牲細(xì)微精度為代價(jià)，換來(lái)存儲(chǔ)空間的大量節(jié)儉，常用于諸如判斷用戶(hù)名重復(fù)、是否在黑名單上等等。

Fail-Fast機(jī)制

眾所周知，HashMap不是線程安全的集合類(lèi)。但在某些容錯(cuò)能力較好的應(yīng)用中，如果你不想僅僅因?yàn)?%的可能性而去承受hashTable的同步開(kāi)銷(xiāo)，則可以考慮利用一下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è)線程都會(huì)存一份自己的工作內(nèi)存，此工作內(nèi)存的內(nèi)容與本地內(nèi)存并非時(shí)時(shí)刻刻都同步，因此可能會(huì)出現(xiàn)線程間的修改不可見(jiàn)的問(wèn)題） 。使用Iterator開(kāi)始迭代時(shí)，會(huì)將modCount的賦值給expectedModCount，在迭代過(guò)程中，通過(guò)每次比較兩者是否相等來(lái)判斷HashMap是否在內(nèi)部或被其它線程修改。HashMap的大多數(shù)修改方法都會(huì)改變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中添加元素都會(huì)導(dǎo)致modCount自增。其它諸如remove、clear方法也都包含類(lèi)似的操作。 從上面可以看出，HashMap所采用的Fail-Fast機(jī)制本質(zhì)上是一種樂(lè)觀鎖機(jī)制，通過(guò)檢查狀態(tài)——沒(méi)有問(wèn)題則忽略——有問(wèn)題則拋出異常的方式，來(lái)避免線程同步的開(kāi)銷(xiāo)，下面給出一個(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)行上面的代碼會(huì)拋出java.util.ConcurrentModificationException，因?yàn)樵诘^(guò)程中修改了HashMap內(nèi)部的元素導(dǎo)致modCount自增。若將上面代碼中 map.put(new Object(), "b") 這句注釋掉，程序會(huì)順利通過(guò)，因?yàn)榇藭r(shí)HashMap中只包含一個(gè)元素，經(jīng)過(guò)一次迭代后已到了尾部，所以不會(huì)出現(xiàn)問(wèn)題，也就沒(méi)有拋出異常的必要了。

在通常并發(fā)環(huán)境下，還是建議采用同步機(jī)制。這一般通過(guò)對(duì)自然封裝該映射的對(duì)象進(jìn)行同步操作來(lái)完成。如果不存在這樣的對(duì)象，則應(yīng)該使用 Collections.synchronizedMap 方法來(lái)“包裝”該映射。最好在創(chuàng)建時(shí)完成這一操作，以防止意外的非同步訪問(wèn)。

LinkedHashMap

遍歷HashMap所得到的數(shù)據(jù)是雜亂無(wú)章的，這在某些情況下客戶(hù)需要特定遍歷順序時(shí)是十分有用的。比如，這種數(shù)據(jù)結(jié)構(gòu)很適合構(gòu)建 LRU 緩存。調(diào)用 put 或 get 方法將會(huì)訪問(wèn)相應(yīng)的條目（假定調(diào)用完成后它還存在）。putAll 方法以指定映射的條目集合迭代器提供的鍵-值映射關(guān)系的順序，為指定映射的每個(gè)映射關(guān)系生成一個(gè)條目訪問(wèn)。Sun提供的J2SE說(shuō)明文檔特別規(guī)定任何其他方法均不生成條目訪問(wèn)，尤其，collection 集合類(lèi)的操作不會(huì)影響底層映射的迭代順序。

LinkedHashMap的實(shí)現(xiàn)與 HashMap 的不同之處在于，前者維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序通常就是集合中元素的插入順序。該類(lèi)定義了header、before與after三個(gè)屬性來(lái)表示該集合類(lèi)的頭與前后“指針”，其具體用法類(lèi)似于數(shù)據(jù)結(jié)構(gòu)中的雙鏈表，以刪除某個(gè)元素為例：

private void remove() {
before.after = after;
after.before = before;
}    

實(shí)際上就是改變前后指針?biāo)赶虻脑亍?

顯然，由于增加了維護(hù)鏈接列表的開(kāi)支，其性能要比 HashMap 稍遜一籌，不過(guò)有一點(diǎn)例外：LinkedHashMap的迭代所需時(shí)間與其的所包含的元素成比例；而HashMap 迭代時(shí)間很可能開(kāi)支較大，因?yàn)樗枰臅r(shí)間與其容量（分配給Key空間的長(zhǎng)度）成比例。一言以蔽之，隨機(jī)存取用HashMap，順序存取或是遍歷用LinkedHashMap。

LinkedHashMap還重寫(xiě)了removeEldestEntry方法以實(shí)現(xiàn)自動(dòng)清除過(guò)期數(shù)據(jù)的功能，這在HashMap中是無(wú)法實(shí)現(xiàn)的，因?yàn)楹笳咂鋬?nèi)部的元素是無(wú)序的。默認(rèn)情況下，LinkedHashMap中的removeEldestEntry的作用被關(guān)閉，其具體實(shí)現(xiàn)如下：

protected boolean removeEldestEntry(Map.Entry eldest) {
return false;
}    

可以使用如下的代碼覆蓋removeEldestEntry：

private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}    

它表示，剛開(kāi)始，LinkedHashMap中的元素不斷增長(zhǎng)；當(dāng)它內(nèi)部的元素超過(guò)MAX_ENTRIES（100）后，每當(dāng)有新的元素被插入時(shí)，都會(huì)自動(dòng)刪除雙鏈表中最前端（最舊）的元素，從而保持LinkedHashMap的長(zhǎng)度穩(wěn)定。

缺省情況下，LinkedHashMap采取的更新策略是類(lèi)似于隊(duì)列的FIFO，如果你想實(shí)現(xiàn)更復(fù)雜的更新邏輯比如LRU（最近最少使用） 等，可以在構(gòu)造函數(shù)中指定其accessOrder為true，因?yàn)榈脑L問(wèn)元素的方法（get）內(nèi)部會(huì)調(diào)用一個(gè)“鉤子”，即recordAccess，其具體實(shí)現(xiàn)如下：

void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}   

上述代碼主要實(shí)現(xiàn)了這樣的功能：如果accessOrder被設(shè)置為true，則每次訪問(wèn)元素時(shí)，都將該元素移至headr的前面，即鏈表的尾部。將removeEldestEntry與accessOrder一起使用，就可以實(shí)現(xiàn)最基本的內(nèi)存緩存，具體代碼可參考http://bluepopopo./blog/180236。

WeakHashMap

99%的Java教材教導(dǎo)我們不要去干預(yù)JVM的垃圾回收機(jī)制，但JAVA中確實(shí)存在著與其密切相關(guān)的四種引用：強(qiáng)引用、軟引用、弱引用以及幻象引用。

Java中默認(rèn)的HashMap采用的是采用類(lèi)似于強(qiáng)引用的強(qiáng)鍵來(lái)管理的，這意味著即使作為key的對(duì)象已經(jīng)不存在了（指沒(méi)有任何一個(gè)引用指向它），也仍然會(huì)保留在HashMap中，在某些情況下（例如內(nèi)存緩存）中，這些過(guò)期的條目可能會(huì)造成內(nèi)存泄漏等問(wèn)題。

WeakHashMap采用的策略是，只要作為key的對(duì)象已經(jīng)不存在了（超出生命周期），就不會(huì)阻止垃圾收集器清空此條目，即使當(dāng)前機(jī)器的內(nèi)存并不緊張。不過(guò)，由于GC是一個(gè)優(yōu)先級(jí)很低的線程，因此不一定會(huì)很快發(fā)現(xiàn)那些只具有弱引用的對(duì)象，除非你顯示地調(diào)用它，可以參考下面的例子：

public static void main(String[] args) {
Map<String, String>map = new WeakHashMap<String, String>();
map.put(new String("Alibaba"), "alibaba");
while (map.containsKey("Alibaba")) {
try {
Thread.sleep(500);
} catch (InterruptedException ignored) {
}
System.out.println("Checking for empty");
System.gc();
}    

上述代碼輸出一次Checking for empty就退出了主線程，意味著GC在最近的一次垃圾回收周期中清除了new String(“Alibaba”),同時(shí)WeakHashMap也做出了及時(shí)的反應(yīng)，將該鍵對(duì)應(yīng)的條目刪除了。如果將map的類(lèi)型改為HashMap的話，由于其內(nèi)部采用的是強(qiáng)引用機(jī)制，因此即使GC被顯示調(diào)用，map中的條目依然存在，程序會(huì)不斷地打出Checking for empty字樣。另外，在使用WeakHashMap的情況下，若是將 map.put(new String("Alibaba"), "alibaba"); 改為 map.put("Alibaba", "alibaba"); 程序還是會(huì)不斷輸出Checking for empty。這與前面我們分析的WeakHashMap的弱引用機(jī)制并不矛盾，因?yàn)镴VM為了減小重復(fù)創(chuàng)建和維護(hù)多個(gè)相同String的開(kāi)銷(xiāo)，其內(nèi)部采用了蠅量模式（《Java與模式》），此時(shí)的“Alibaba”是存放在常量池而非堆中的，因此即使沒(méi)有對(duì)象指向“Alibaba”，它也不會(huì)被GC回收。弱引用特別適合以下對(duì)象：占用大量?jī)?nèi)存，但通過(guò)垃圾回收功能回收以后很容易重新創(chuàng)建。

介于HashMap和WeakHashMap之中的是SoftHashMap，它所采用的軟引用的策略指的是，垃圾收集器并不像其收集弱可及的對(duì)象一樣盡量地收集軟可及的對(duì)象，相反，它只在真正 “需要” 內(nèi)存時(shí)才收集軟可及的對(duì)象。軟引用對(duì)于垃圾收集器來(lái)說(shuō)是一種“睜一只眼，閉一只眼”方式，即 “只要內(nèi)存不太緊張，我就會(huì)保留該對(duì)象。但是如果內(nèi)存變得真正緊張了，我就會(huì)去收集并處理這個(gè)對(duì)象。” 就這一點(diǎn)看，它其實(shí)要比WeakHashMap更適合于實(shí)現(xiàn)緩存機(jī)制。遺憾的是，JAVA中并沒(méi)有實(shí)現(xiàn)相關(guān)的SoftHashMap類(lèi)（Apache和Google提供了第三方的實(shí)現(xiàn)），但它卻是提供了兩個(gè)十分重要的類(lèi)java.lang.ref.SoftReference以及ReferenceQueue，可以在對(duì)象應(yīng)用狀態(tài)發(fā)生改變是得到通知，可以參考com.alibaba.common.collection.SofthashMap中processQueue方法的實(shí)現(xiàn)：

private ReferenceQueue queue = new ReferenceQueue();
ValueCell vc;
Map hash = new HashMap(initialCapacity, loadFactor);
……
while ((vc = (ValueCell) queue.poll()) != null) {
if (vc.isValid()) {
hash.remove(vc.key);
} else {
valueCell.dropped--;
}
}
}   

processQueue方法會(huì)在幾乎所有SoftHashMap的方法中被調(diào)用到，JVM會(huì)通過(guò)ReferenceQueue的poll方法通知該對(duì)象已經(jīng)過(guò)期并且當(dāng)前的內(nèi)存現(xiàn)狀需要將它釋放，此時(shí)我們就可以將其從hashMap中剔除。事實(shí)上，默認(rèn)情況下，Alibaba的MemoryCache所使用的就是SoftHashMap。