HashMap可以說是java從業者經常用到的，儘管網上有很多介紹HashMap的文章，但是我還是想寫一寫自己的一些見解，同時加深自己對HashMap的理解與印象。

首先，HashMap最早出現於jdk1.2，位於java.util包下。

HashMap繼承了AbstractMap，實現了Map, Cloneable, Serializable。

這裡咱們分兩個版本進行介紹，分別是jdk1.6和jdk1.8。1.8在1.6的基礎上有了很大的改進。

JDK1.6下的HashMap

整個類加上注釋一共有代碼1039行，整個類的變數一共十個。類方法40個。內部類一共8個。

咱們先看一個貫穿全文的內部類，是HashMap的基本組成。

那就是Entry。

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;

/**
 * Creates new entry.
 */
Entry(int h, K k, V v, Entry<K,V> 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();
}

/**
 * This method is invoked whenever the value in an entry is
 * overwritten by an invocation of put(k,v) for a key k thats already
 * in the HashMap.
 */
void recordAccess(HashMap<K,V> m) {
}

/**
 * This method is invoked whenever the entry is
 * removed from the table.
 */
void recordRemoval(HashMap<K,V> m) {
}
}

HashMap是由數組+鏈表構成，那麼數組和鏈表就是一個個Entry組成。我們可以看到Entry類包含的變數有泛型的key，value，以及同是Entry類型的指針，hash值。

自己手畫了一個HashMap的組成結構圖。

十個類變數：

private static final long serialVersionUID = 362498820763181265L;

serialVersionUID基本是每個需要序列化的類都有的一個變數，不作介紹。

static final int DEFAULT_INITIAL_CAPACITY = 16;

DEFAULT_INITIAL_CAPACITY是table數組默認容量，默認為16。

static final int MAXIMUM_CAPACITY = 1 << 30;

MAXIMUM_CAPACITY是table數組最大容量，為2的30次方。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

DEFAULT_LOAD_FACTOR：默認載入因子，初始值0.75。

transient Entry[] table;

table是HashMap的主要構成，數組裡面放的是Entry類型的數據。

transient int size;

size是HashMap包含鍵值對的數目。

int threshold;

這個是table數組擴容的標準，達到這個值就會進行擴容，默認的值是。容量*載入因子。

final float loadFactor;

這個是hash表的載入因子。

transient volatile int modCount;

modCount記錄HashMap被修改的次數。包括插入刪除等操作。

private transient Set<Map.Entry<K,V>> entrySet = null;

entrySet 是存儲Entry類型數據的set。

40個類方法就不一一介紹了。選幾個相對重要的看看。

首先是默認構造方法

public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}

我們可以看到使用的是默認的容量和載入因子。對loadFactor、threshold賦值。以及初始化table。init()是一個空方法，不作討論。

除了默認構造方法，還有其它三個構造方法。分別是HashMap(int initialCapacity)、HashMap(int initialCapacity, float loadFactor)、HashMap(Map<? extends K, ? extends V> m)。

HashMap(int initialCapacity)會調用HashMap(int initialCapacity, float loadFactor)，傳入默認的載入因子。HashMap(Map<? extends K, ? extends V> m)則是根據傳進來的map生成具有同樣鍵值對的map。

這裡我們看一下HashMap(int initialCapacity, float loadFactor)

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)
capacity <<= 1;

this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}

上面可以看到顯示判斷傳入的初始容量和載入因子，如果不符合要求則拋出異常，超過最大容量則默認最大容量。capacity <<= 1;這個很有意思，一直循環找到大於你傳進去初始容量的2的階乘。這個也保證了table的大小為2的倍數。後面的代碼也和前面說的一樣了。

下面主要看一下核心的put和get方法。

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> 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是否為空，為空調用putForNullKey(value)。這裡說明瞭一個問題，那就是hashmap接受key為空的情況，同樣value也可以為空。那麼基本和hashmap沒什麼區別的hashtable，卻不允許空value的情況，會拋出空指針異常。

我們先假設key為空，看一下putForNullKey(value)。

private V putForNullKey(V value) {
for (Entry<K,V> 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;
}

默認取table數組index為0的位置的鏈表，如果發現有key為空的情況，則替換value。如果遍歷完之後都沒有匹配的。就modCount自增，調用 addEntry方法。

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);
}

通過上面代碼我們可以看到這個時候就是把空的key，value封裝成Entry放到table[0]的位置，同時插入鏈表。這裡也判斷如果插入之後大小超過擴容大小（threshold），則調用resize方法擴容。

resize方法就不貼源碼了，再貼就有點深了，一會兒收不回來。簡單說一下resize做了什麼事情。resize主要new了一個傳進去的數值大小的Entry數組，然後把之前table的Entry轉移到新的Entry數組中，這個過程中根據每個Entry的hash值，重新定位了在新數組中的位置，然後將原table指針指向新的Entry數組，完成擴容。

然後咱們再回到最開始的put方法。這裡重新貼一下代碼。

public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> 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不為空，對key的hashcode值進行一次hash運算，然後根據得到的hash值，調用indexFor方法得到在table數組中的位置，接著遍歷table數組位置上的鏈表，如果存在相同的key，則對value值進行覆蓋。否則在該table鏈表頭部插入該鍵值對。我們剛纔看過addEntry方法，裡面會自增size，然後判斷是否大於threshold（擴容臨界值），如果是調用resize方法，這樣說明什麼呢？

舉個例子。一個默認大小16的HashMap，如果裡面存放了11個值，但是隻佔據了10個數組單元空間，其中一個鏈表上有兩個鍵值對。只需要再放入一個鍵值對，不管在之前10個鏈表下，還是新佔據一個單元空間，HashMap都會擴容。並不是佔據16個數組單元中的12個。這樣做我想到的好處是擴容後，調用indexFor方法，所有鍵值對會分佈更加均勻，保證每個鏈表只有一個元素。

看代碼的時候，我就在想如果不擴容，HashMap也能存下非常多的元素，為什麼還要擴容呢？答案是便於操作，如插入和查找。一次hash和indexFor方法就能找到，為什麼還要遍歷長長的鏈表去找呢？

接著看一下get方法，看了put之後再看這個就很簡單了。

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
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.equals(k)))
return e.value;
}
return null;
}

首先同樣是key為空的情況，調用getForNullKey()。

private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}

put key為空時我們直接放在table[0]的鏈表裡，所以這裡直接遍歷0處的鏈表，找到直接返回，否則返回null。

不為空時就調用hash，indexFor方法，遍歷對應位置上的鏈表，返回相應的值。

接下來看一下remove方法。

public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}

直接調用removeEntryForKey方法。

final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;

while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}

return e;
}

這個方法定位到所刪除元素所屬鏈表的數組位置，然後new了兩個Entry類型的指針，prev和e。兩個指針同時遍歷鏈表，這個就是鏈表刪除常用的操作，當e遍歷到所刪除元素所在節點，prev指針在e的前一個節點，只需要prev指針的next指向e的next，那麼就把e所在的節點從鏈表中刪除了。

源碼的部分就到這裡結束了。下面是對HashMap的一些擴展。

HashMap遍歷,這裡使用了entrySet，調用Set的iterator方法。

Map<String,Object> map = new HashMap<String,Object>();
Iterator iterator=map.entrySet().iterator();
while(iterator.hasNext()){
Map.Entry entry=(Map.Entry)iterator.next();
System.out.println(entry.getKey()+" "+entry.getValue());
}

在開始的時候，說了HashMap繼承了AbstractMap，實現了Map。但是同時AbstractMap也實現了Map，那麼AbstractMap也實現了Map的所有方法，這裡為什麼還要實現Map呢？

一開始覺得是多餘了，因為已經繼承AbstractMap了。後來網上搜了一下確實是多餘了。作者Josh Bloch 自己承認當時沒考慮到這點，還以為實現Map有點價值。不過這個也一直這樣保留了，也沒有更改。

本來想把1.8的介紹和1.6寫在一起，但是1.8 HashMap的東西也不少，整合一起感覺篇幅太長，還是決定分開寫。感興趣的可以在專欄看另外一篇1.8的介紹。後續幾天會發出來。以後有新的關於HashMap的理解也會更新在這裡。

推薦閱讀：

相關文章