最近在看Guava中的Cache的源碼，它的實現基于ConcurrentHashMap，前段時間組里招人，據說很多看起來很牛掰的簡歷，一個HashMap就能刷掉很多，所以順便把HashMap和ConcurrentHashMap的源碼復習一遍。先從HashMap開始（另：Hashtable是HashMap的線程安全版本，它的實現和HashMap實現基本一致，除了它不能包含null值的key和value，并且它在計算hash值和數組索引值的方式要稍微簡單一些。對于線程安全的實現，Hashtable簡單的將所有操作都標記成synchronized，即對當前實例的鎖，這樣容易引起一些性能問題，所以目前一般使用性能更好的ConcurrentHashMap）。
Map是對鍵值對存儲的抽象，因而其最主要的方法有：
1. 添加新的鍵值對(key,value)；
2. 通過鍵(key)查找關聯的值(value)；
3. 通過鍵(key)移除關聯的值(value)；
4. 判斷鍵(key)或值(value)的存在性。
其他的方法有：判斷鍵值對的空屬性以及目前的鍵值對數，獲取所有鍵、所有值或者所有鍵值對的集合，批量添加，清除所有鍵值對等。在Map中，一個鍵值對用Entry接口來表示。因而在Java中，對Map接口的定義如下：
public interface Map<K,V> {
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void putAll(Map<? extends K, ? extends V> m);
void clear();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
boolean equals(Object o);
int hashCode();
}
HashMap是哈希表對Map非線程安全版本的實現，
它允許key為null，也允許value為null。所謂哈希表就是通過一個哈希函數計算出一個key的哈希值，然后使用該哈希值定位對應的value所在的位置；如果出現哈希值沖突（多個key產生相同的哈希值），則采用一定的沖突處理方法定位到正真value位置，然后返回查找到的value值。一般哈希表內部使用一個數組實現，使用哈希函數計算出key對應數組中的位置，然后使用處理沖突法找到真正的value，并返回。因而實現哈希表最主要的問題在于選擇哈希函數和沖突處理方法，好的哈希函數能使數據分布更加零散，從而減少沖突的可能性，而好的沖突處理方法能使沖突處理更快，盡量讓數據分布更加零散，從而不會影響將來的沖突處理方法。
在嚴蔚敏、吳偉明版本的《數據結構（C語言版）》中提供的哈希函數有：1. 直接定址法（線性函數法）；2. 數字分析法；3. 平方取中法；4. 折疊法；5. 除留余數法；6. 隨機數法。在JDK的HashMap中采用了移位異或法后除留余數（和2的n次方'&'操作）。HashMap內部的數據結構是一個Entry<K, V>的數組，在使用key查找value時，先使用key實例計算hash值，然后對計算出的hash值做各種移位和異或操作，然后取其數組的最大索引值的余數（'&'操作，一般其容量值都是2的倍數，因而可以認為是除留余數）。在JDK 1.7中對String類型采用了內部hash算法（當數組容量超過一定的閥值，使用“jdk.map.althashing.threshold”設置該閥值，默認為Integer.MAX_VALUE，即關閉該功能），并且使用了一個hashSeed作為初始值，不了解這些算法的具體緣由，就這樣淺嘗輒止了。
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
同樣在上述的數據結構書中關于沖突處理提供了幾個方法：1. 開放定址法；2. 再哈希法；3.鏈地址法；4. 建立一個公共溢出區法。在JDK的HashMap中采用了鏈地址法，即每個數組bucket中存放的是一個Entry鏈，每次新添加一個鍵值對，就是向鏈頭添加一個Entry實例，新添加的Entry的下一個元素是原有的鏈頭（如果該數組bucket不存在Entry鏈，則原有鏈頭值為null，不影響邏輯）。每個Entry包含key、value、hash值和指向下一個Entry的next指針。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
}
添加
從以上描述中，我們可以知道添加新的鍵值對可以分成兩部分：
1. 使用key計算出內部數組的索引值（index）。
2. 如果該索引的數組bucket中已經存在Entry鏈，并且該鏈中已經存在新添加的key的值，則將原有的值設置成新添加的值，并返回舊值。
3. 否則，創建新的Entry實例，將該實例插入到原有鏈的頭部。
4. 在新添加Entry實例時，如果當前size超過閥值（capacity * loadFactor），數組容量將會自動擴大兩倍，在數組擴容時，所有原存在的Entry會重新計算索引值，并且Entry鏈的順序也會發生顛倒（如果還在同一個鏈中的話）；而該新添加的Entry的索引值也會重新計算。
5. 對key為null時，默認數組的索引值為0，其他邏輯不變。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
插入原理圖：
查找
查找和添加類似，首先根據key計算出數組的索引值（如果key為null，則索引值為0），然后順序查找該索引值對應的Entry鏈，如果在Entry鏈中找到相等的key，則表示找到相應的Entry記錄，否則，表示沒找到，返回null。對get()操作返回Entry中的Value值，對于containsKey()操作，則判斷是否存在記錄，兩個方法都調用getEntry()方法：
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
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 != null && key.equals(k))))
return e;
}
return null;
}
而對于value查找（如containsValue()操作）則需要整個表遍歷（數組遍歷和數組中的Entry鏈遍歷），因而這種查找的效率比較低，代碼實現也比較簡單。
移除
移除操作（remove()）也是先通過key值計算數組中的索引號（當key為null時索引號為0），從而找到Entry鏈，查找Entry鏈中的Entry，并將該Entry刪除。
遍歷
HashMap中實現了一個HashIterator，它首先遍歷數組，查找到一個非null的Entry實例，記錄該Entry所在數組索引，然后在下一個next()操作中，繼續查找下一個非null的Entry，并將之前查找到的非null Entry返回。為實現遍歷時不能修改HashMap的內容（可以更新已存在的記錄的值，但是不可以添加、刪除原有記錄），HashMap記錄一個modCount字段，在每次添加或刪除操作起效時，將modCount自增，而在創建HashIterator時記錄當前的modCount值（expectedModCount），如果在遍歷過程中（next()、remove()）操作時，HashMap中的modCount和已存儲的expectedModCount不一樣，表示HashMap已經被修改，拋出ConcurrentModificationException。即所謂的fail fast原則。
在HashMap中返回的key、value、Entry集合都是基于該Iterator實現，實現比較簡單，不細講。
注：clear()操作引起的內存問題-由于clear()操作只是將數組中的所有項置為null，數組本身大小并不改變，因而當某個HashMap已存儲過較大的數據時，調用clear()有些時候不是一個好的做法。
最后吐槽一下，即使JDK內部的HashMap也有很多的代碼重復。。。。。
posted on 2013-10-15 23:40
DLevin 閱讀(5719)
評論(2) 編輯 收藏 所屬分類:
Core Java