[轉] HashMap的存取之美 - gugege－IT工程師數位筆記本

文章出處

本文轉自 http://www.nowamagic.net/librarys/veda/detail/1202

HashMap是一種十分常用的數據結構，作為一個應用開發人員，對其原理、實現的加深理解有助于更高效地進行數據存取。本文所用的jdk版本為1.5。

使用HashMap

《Effective JAVA》中認為，99%的情況下，當你覆蓋了equals方法后，請務必覆蓋hashCode方法。默認情況下，這兩者會采用Object的“原生”實現方式，即：

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

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

另一方面，你應該盡量避免使用“可變”的類作為HashMap的鍵。如果你將一個對象作為鍵值并保存在HashMap中，之后又改變了其狀態，那么HashMap就會產生混亂，你所保存的值可能丟失（盡管遍歷集合可能可以找到）。

HashMap存取機制

Hashmap實際上是一個數組和鏈表的結合體，利用數組來模擬一個個桶（類似于Bucket Sort）以快速存取不同hashCode的key，對于相同hashCode的不同key，再調用其equals方法從List中提取出和key所相對應的value。

Java中hashMap的初始化主要是為initialCapacity和loadFactor這兩個屬性賦值。前者表示hashMap中用來區分不同hash值的key空間長度，后者是指定了當hashMap中的元素超過多少的時候，開始自動擴容，。默認情況下initialCapacity為16，loadFactor為0.75，它表示一開始hashMap可以存放16個不同的hashCode，當填充到第12個的時候，hashMap會自動將其key空間的長度擴容到32，以此類推；這點可以從源碼中看出來：

1 void addEntry(int hash, K key, V value, int bucketIndex) {  
2     Entry<K,V> e = table[bucketIndex];  
3         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
4         if (size++ >= threshold)  
5             resize(2 * table.length);  
6 }

而每當hashMap擴容后，內部的每個元素存放的位置都會發生變化（因為元素的最終位置是其hashCode對key空間長度取模而得），因此resize方法中又會調用transfer函數，用來重新分配內部的元素；這個過程成為rehash，是十分消耗性能的，因此在可預知元素的個數的情況下，一般應該避免使用缺省的initialCapacity，而是通過構造函數為其指定一個值。例如我們可能會想要將數據庫查詢所得1000條記錄以某個特定字段（比如ID）為key緩存在hashMap中，為了提高效率、避免rehash，可以直接指定initialCapacity為2048。

另一個值得注意的地方是，hashMap其key空間的長度一定為2的N次方，這一點可以從一下源碼中看出來：

1 int capacity = 1;

2 while (capacity < initialCapacity)

3 　　capacity <<= 1;

即使我們在構造函數中指定的initialCapacity不是2的平方數，capacity還是會被賦值為2的N次方。

為什么Sun Microsystem的工程師要將hashMap key空間的長度設為2的N次方呢？這里參考R.W.Floyed給出的衡量散列思想的三個標準：一個好的hash算法的計算應該是非常快的，一個好的hash算法應該是沖突極小化，如果存在沖突，應該是沖突均勻化。

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

上述設計的原因在于，取模運算在包括Java在內的大多數語言中的效率都十分低下，而當除數為2的N次方時，取模運算將退化為最簡單的位運算，其效率明顯提升（按照Bruce Eckel給出的數據，大約可以提升5～8倍）。看看JDK中是如何實現的：

1 static int indexFor(int h, int length) {  
2     return h & (length-1);  
3 }

當key空間長度為2的N次方時，計算hashCode為h的元素的索引可以用簡單的與操作來代替笨拙的取模操作！假設某個對象的hashCode為35（二進制為100011），而hashMap采用默認的initialCapacity（16），那么indexFor計算所得結果將會是100011 & 1111 = 11，即十進制的3，是不是恰好是35 Mod 16。

上面的方法有一個問題，就是它的計算結果僅有對象hashCode的低位決定，而高位被統統屏蔽了；以上面為例，19（10011）、35（100011）、67（1000011）等就具有相同的結果。針對這個問題， Joshua Bloch采用了“防御性編程”的解決方法，在使用各對象的hashCode之前對其進行二次Hash，參看JDK中的源碼：

1 static int hash(Object x) {  
2         int h = x.hashCode();  
3         h += ~(h << 9);  
4         h ^=  (h >>> 14);  
5         h +=  (h << 4);  
6         h ^=  (h >>> 10);  
7         return h;  
8     }

采用這種旋轉Hash函數的主要目的是讓原有hashCode的高位信息也能被充分利用，且兼顧計算效率以及數據統計的特性，其具體的原理已超出了本文的領域。

加快Hash效率的另一個有效途徑是編寫良好的自定義對象的HashCode，String的實現采用了如下的計算方法：

1 for (int i = 0; i < len; i++) { 2 h = 31*h + val[off++]; 3 } 4 hash = h;

這種方法HashCode的計算方法可能最早出現在Brian W. Kernighan和Dennis M. Ritchie的《The C Programming Language》中，被認為是性價比最高的算法（又被稱為times33算法，因為C中乘數常量為33，JAVA中改為31），實際上，包括List在內的大多數的對象都是用這種方法計算Hash值。

另一種比較特殊的hash算法稱為布隆過濾器，它以犧牲細微精度為代價，換來存儲空間的大量節儉，常用于諸如判斷用戶名重復、是否在黑名單上等等。

Fail-Fast機制

眾所周知，HashMap不是線程安全的集合類。但在某些容錯能力較好的應用中，如果你不想僅僅因為1%的可能性而去承受hashTable的同步開銷，則可以考慮利用一下HashMap的Fail-Fast機制，其具體實現如下：

Entry<K,V> nextEntry() {   
if (modCount != expectedModCount)  
    throw new ConcurrentModificationException();  
                     …… 
}

其中modCount為HashMap的一個實例變量，并且被聲明為volatile，表示任何線程都可以看到該變量被其它線程修改的結果（根據JVM內存模型的優化，每一個線程都會存一份自己的工作內存，此工作內存的內容與本地內存并非時時刻刻都同步，因此可能會出現線程間的修改不可見的問題）。使用Iterator開始迭代時，會將modCount的賦值給expectedModCount，在迭代過程中，通過每次比較兩者是否相等來判斷HashMap是否在內部或被其它線程修改。HashMap的大多數修改方法都會改變ModCount，參考下面的源碼：

 1 public V put(K key, V value) {  
 2     K k = maskNull(key);  
 3         int hash = hash(k);  
 4         int i = indexFor(hash, table.length);  
 5         for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
 6             if (e.hash == hash && eq(k, e.key)) {  
 7                 V oldValue = e.value;  
 8                 e.value = value;  
 9                 e.recordAccess(this);  
10                 return oldValue;  
11             }  
12         }  
13         modCount++;  
14         addEntry(hash, k, value, i);  
15         return null;  
16     }

以put方法為例，每次往HashMap中添加元素都會導致modCount自增。其它諸如remove、clear方法也都包含類似的操作。從上面可以看出，HashMap所采用的Fail-Fast機制本質上是一種樂觀鎖機制，通過檢查狀態——沒有問題則忽略——有問題則拋出異常的方式，來避免線程同步的開銷，下面給出一個在單線程環境下發生Fast-Fail的例子：

 1 class Test {    
 2     public static void main(String[] args) {               
 3         java.util.HashMap<Object,String> map=new java.util.HashMap<Object,String>();    
 4        map.put(new Object(), "a");    
 5        map.put(new Object(), "b");    
 6        java.util.Iterator<Object> it=map.keySet().iterator();    
 7        while(it.hasNext()){    
 8            it.next();    
 9            map.put("", "");         
10         System.out.println(map.size());    
11     }    
12 }

運行上面的代碼會拋出java.util.ConcurrentModificationException，因為在迭代過程中修改了HashMap內部的元素導致modCount自增。若將上面代碼中 map.put(new Object(), "b") 這句注釋掉，程序會順利通過，因為此時HashMap中只包含一個元素，經過一次迭代后已到了尾部，所以不會出現問題，也就沒有拋出異常的必要了。

在通常并發環境下，還是建議采用同步機制。這一般通過對自然封裝該映射的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedMap 方法來“包裝”該映射。最好在創建時完成這一操作，以防止意外的非同步訪問。

LinkedHashMap

遍歷HashMap所得到的數據是雜亂無章的，這在某些情況下客戶需要特定遍歷順序時是十分有用的。比如，這種數據結構很適合構建 LRU 緩存。調用 put 或 get 方法將會訪問相應的條目（假定調用完成后它還存在）。putAll 方法以指定映射的條目集合迭代器提供的鍵-值映射關系的順序，為指定映射的每個映射關系生成一個條目訪問。Sun提供的J2SE說明文檔特別規定任何其他方法均不生成條目訪問，尤其，collection 集合類的操作不會影響底層映射的迭代順序。

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

1 private void remove() {  
2        before.after = after;  
3        after.before = before;  
4 }

實際上就是改變前后指針所指向的元素。

顯然，由于增加了維護鏈接列表的開支，其性能要比 HashMap 稍遜一籌，不過有一點例外：LinkedHashMap的迭代所需時間與其的所包含的元素成比例；而HashMap 迭代時間很可能開支較大，因為它所需要的時間與其容量（分配給Key空間的長度）成比例。一言以蔽之，隨機存取用HashMap，順序存取或是遍歷用LinkedHashMap。

LinkedHashMap還重寫了removeEldestEntry方法以實現自動清除過期數據的功能，這在HashMap中是無法實現的，因為后者其內部的元素是無序的。默認情況下，LinkedHashMap中的removeEldestEntry的作用被關閉，其具體實現如下：

1 protected boolean removeEldestEntry(Map.Entry<k,v> eldest) { 
2     return false; 
3 }

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

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

它表示，剛開始，LinkedHashMap中的元素不斷增長；當它內部的元素超過MAX_ENTRIES（100）后，每當有新的元素被插入時，都會自動刪除雙鏈表中最前端（最舊）的元素，從而保持LinkedHashMap的長度穩定。

缺省情況下，LinkedHashMap采取的更新策略是類似于隊列的FIFO，如果你想實現更復雜的更新邏輯比如LRU（最近最少使用）等，可以在構造函數中指定其accessOrder為true，因為的訪問元素的方法（get）內部會調用一個“鉤子”，即recordAccess，其具體實現如下：

1 void recordAccess(HashMap<K,V> m) {  
2     LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
3     if (lm.accessOrder) {  
4         lm.modCount++;  
5         remove();  
6         addBefore(lm.header);  
7     }  
8 }

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

WeakHashMap

99%的Java教材教導我們不要去干預JVM的垃圾回收機制，但JAVA中確實存在著與其密切相關的四種引用：強引用、軟引用、弱引用以及幻象引用。

Java中默認的HashMap采用的是采用類似于強引用的強鍵來管理的，這意味著即使作為key的對象已經不存在了（指沒有任何一個引用指向它），也仍然會保留在HashMap中，在某些情況下（例如內存緩存）中，這些過期的條目可能會造成內存泄漏等問題。

WeakHashMap采用的策略是，只要作為key的對象已經不存在了（超出生命周期），就不會阻止垃圾收集器清空此條目，即使當前機器的內存并不緊張。不過，由于GC是一個優先級很低的線程，因此不一定會很快發現那些只具有弱引用的對象，除非你顯示地調用它，可以參考下面的例子：

 1 public static void main(String[] args) {  
 2     Map<String, String>map = new WeakHashMap<String, String>();  
 3     map.put(new String("Alibaba"), "alibaba");  
 4     while (map.containsKey("Alibaba")) {  
 5         try {  
 6             Thread.sleep(500);  
 7          } catch (InterruptedException ignored) {  
 8          }  
 9          System.out.println("Checking for empty");  
10          System.gc();  
11     }

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

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

 1 private ReferenceQueue queue = new ReferenceQueue(); 
 2 ValueCell vc; 
 3 Map hash = new HashMap(initialCapacity, loadFactor); 
 4 …… 
 5 while ((vc = (ValueCell) queue.poll()) != null) { 
 6 if (vc.isValid()) { 
 7           hash.remove(vc.key); 
 8            } else { 
 9              valueCell.dropped--; 
10            } 
11 } 
12 }

processQueue方法會在幾乎所有SoftHashMap的方法中被調用到，JVM會通過ReferenceQueue的poll方法通知該對象已經過期并且當前的內存現狀需要將它釋放，此時我們就可以將其從hashMap中剔除。事實上，默認情況下，Alibaba的MemoryCache所使用的就是SoftHashMap。

文章列表