摘要：當哈希表中鍵值對的數量超過當前容量和裝載因子的乘積后，哈希表重新散列也就是內部的數據結構重建了，并且哈希表的容量大約變為原來的兩倍。下面的是根據哈希值得到元素在哈希表中的下標。一般在哈希表中是用哈希值對表長取模得到。
簡介
HashMap是Map接口下比較常用的一個類，我們都知道它存儲的是鍵值對(key-value)，可以高效地插入和刪除。這篇文章分析一下它內部的實現，由于源碼比較長，只看一些重要的。
存儲結構
首先，HashMap是基于哈希表存儲的。它內部有一個數組，當元素要存儲的時候，先計算其key的哈希值，根據哈希值找到元素在數組中對應的下標。如果這個位置沒有元素，就直接把當前元素放進去，如果有元素了(這里記為A)，就把當前元素鏈接到元素A的前面，然后把當前元素放入數組中。所以在Hashmap中，數組其實保存的是鏈表的首節點。下面是百度百科的一張圖：
如上圖，每個元素是一個Entry對象，在其中保存了元素的key和value，還有一個指針可用于指向下一個對象。所有哈希值相同的key(也就是沖突了)用鏈表把它們串起來，這是拉鏈法。
內部變量
//默認初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認裝載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//哈希表
transient Entry[] table;
//鍵值對的數量
transient int size;
//擴容的閾值
int threshold;
//哈希數組的裝載因子
final float loadFactor;
在上面的變量中，capacity是指哈希表的長度，也就是table的大小，默認為16。裝載因子loadFactor是哈希表的“裝滿程度”，JDK的文檔是這樣說的：
The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
大體意思是：裝載因子是哈希表在擴容之前能裝多滿的度量值。當哈希表中“鍵值對”的數量超過當前容量(capacity)和裝載因子的乘積后，哈希表重新散列(也就是內部的數據結構重建了)，并且哈希表的容量大約變為原來的兩倍。
從上面的變量定義可以看出，默認的裝載因子DEFAULT_LOAD_FACTOR 是0.75。這個值越大，空間利用率越高，但查詢速度(包括get和put)操作會變慢。明白了裝載因子之后，threshold也就能理解了，它其實等于容量*裝載因子。
構造器
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity) //計算出大于指定容量的最小的2的冪
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity]; //給哈希表分配空間
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
構造器有好幾個，最終都會調用上面的這個。它接受兩個參數，一個是初始容量，還有一個是裝載因子。剛開始先判斷值合不合法，有問題的話會拋出異常。重要的是下面的capacity的計算，它的邏輯是計算出大于initialCapacity的最小的2的冪。其實目的就是要讓容量能大于等于指定的初始容量，但這個值還得是2的指數倍，這是一個關鍵的問題。這么做的原因主要是為了哈希值的映射。先來看一下HashMap中有關哈希的方法：
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();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
return h & (length-1);
}
hash()方法重新計算了key的哈希值，用了比較復雜的位運算，具體邏輯我也不清楚，反正肯定是比較好的方法，能減少沖突什么的。
下面的indexFor()是根據哈希值得到元素在哈希表中的下標。一般在哈希表中是用哈希值對表長取模得到。當length(也就是capacity)為2的冪時，h & (length-1)是同樣的效果。并且，2的冪一定是偶數，那么減1之后就是奇數，二進制的最后一位一定是1。那么h & (length-1)的最后一位可能是1，也可能是0，可以均勻地散列。如果length是奇數，那么length-1就是偶數，最后一位是0。此時h & (length-1)的最后一位只可能是0，所有得到的下標都是偶數，那么哈希表就浪費了一半的空間。所以HashMap中的容量(capacity)一定要是2的冪。可以看到默認的DEFAULT_INITIAL_CAPACITY=16和MAXIMUM_CAPACITY=1<<30都是這樣的。
Entry對象
HashMap中的鍵值對被封裝成Entry對象，這是HashMap中的一個內部類，看一下它的實現：
static class Entry implements Map.Entry {
final K key;
V value;
Entry next;
int hash;
Entry(int h, K k, V v, Entry n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return (key==null ? 0 : key.hashCode()) ^
(value==null ? 0 : value.hashCode());
}
public final String toString() {
return getKey() + "=" + getValue();
}
void recordAccess(HashMap m) {
}
void recordRemoval(HashMap m) {
}
}
這個類的實現還是簡潔易懂的。提供了getKey()、getValue()等方法供調用，判斷相等是要求key和value均相等。
put操作
先put了才能get，所以先看一下put()方法：
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry 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;
}
在這個方法中，先判斷key是否為null，是的話調用putForNullKey()方法，這說明HashMap允許key為null(其實value可以)。如果不是null，計算哈希值并且得到在表中的下標。然后到對應的鏈表中查詢是否已經存在相同的key，如果已經存在就直接更新值(value)。否則，調用addEntry()方法進行插入。
看一下putForNullKey()方法：
private V putForNullKey(V value) {
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
可以看到，key為null時直接在下標0處插入，同樣是存在就更新值，否則調用addEntry()插入。
下面是addEntry()方法的實現：
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 e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
首先判斷是否要擴容(擴容會重新計算下標值，并且復制元素)，然后計算數組下標，最后在createEntry()中使用頭插法插入元素。
get操作
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
for (Entry e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
final Entry getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry 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;
}
這個比put()簡單一些，同樣要判斷key是不是null，然后就是鏈表的遍歷查詢。
總結
HashMap的基本實現就如上面所分析的，最后做下總結：
HashMap內部用Entry對象保存鍵值對，基于哈希表存儲，用拉鏈法解決沖突。
HashMap的默認容量大小為16，默認裝載因子為0.75。可以指定容量大小，容量最終一定會被設置為2的冪，這是為了均勻地散列。
HashMap的key和value都可以是null，當然只能有一個key是null，value可以有多個。
HashMap的鍵值對數量超過容量*裝載因子時會擴容，擴容后的容量大約是原來的兩倍。擴容會重新散列，所以元素的位置可能發生會變化，而且這是一個耗時操作。
HashMap是線程不安全的。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65356.html
