22.原始碼閱讀（jdk1.6 HashMap原始碼和原理分析）
摘要：
HashMap 底層採用陣列 + 連結串列的的實現方式來降低資料插入和查詢的時間複雜度,理想狀態下可以實現時間複雜度位O(1)，今天就從原始碼的角度看一下它是如何實現的。我們從它的兩個關鍵方法put和get入手。
put方法
public V put(K key, V va...
HashMap 底層採用陣列 + 連結串列的的實現方式來降低資料插入和查詢的時間複雜度,理想狀態下可以實現時間複雜度位O(1)，今天就從原始碼的角度看一下它是如何實現的。我們從它的兩個關鍵方法put和get入手。
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);
//陣列中i位置存在Entry物件
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;
}
}
//不存在則建立一個新的Entry加入陣列，並將計數器加1
modCount++;
addEntry(hash, key, value, i);
return null;
}
這裡有兩個關鍵方法hash和indexFor，hash()方法的作用是對key的hashCode值進行一系列的位運算，看下邊的原始碼
/** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions.This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. * 註釋的意思大概是說下邊程式碼是對給定的雜湊值應用補充雜湊函式 * 我們只需要知道一點，經過這些位運算之後，hash值的雜湊效果會 * 得到優化即可 */ static int hash(int h) { // 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); }
再看indexFor方法,將得到的hash值與hashMap中陣列的長度-1的值進行與運算，得到的就是這個元素將會被放置在陣列中的哪個位置的index，並且絕不用擔心發生陣列越界之類的問題，原因請自行發現
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
我們再回到上邊的put方法中，獲取到當前元素將要插入的index後，會從當前的這個內建的陣列中查詢這個index位置是否已經存放了Entry，如果有則變數這個index位置的連結串列，判斷是否有相同key值的元素存在（當前的這個陣列指的就是在new HashMap的時候預設創建出來的一個Entry陣列，它有一個預設長度，此時在沒有進行put操作的時候，陣列中元素都是null）如果此時是第一次put，那麼陣列中是空的，直接繞過這個for迴圈往下執行。如果進行put操作的時候，陣列中存這個index，那麼會進入這個for迴圈，拿到i這個位置的單鏈表，遍歷連結串列中所有的Entry,如果有相同key的元素，則找到它，用新的value值替換舊value，並返回舊value
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;
}
}
繼續往下，如果不存在，那麼建立新的Entry物件
addEntry(hash, key, value, i)
hash：key值計算得到的hash值
i: 經過hash和indexFor方法計算得到的被put的key，value即將被放入陣列中的位置
/**
* Adds a new entry with the specified key, value and hash code to
* the specified bucket.It is the responsibility of this
* method to resize the table if appropriate.
*
* Subclass overrides this to alter the behavior of put method.
*/
void addEntry(int hash, K key, V value, int bucketIndex) {
//拿到陣列中bucketIndex位置的Entry物件，第一次執行，他是null
Entry<K,V> e = table[bucketIndex];
//new了一個Entry物件放在這個bucketIndex位置上
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//判斷是否已經達到了需要擴容的條件，如果是則對HashMap進行擴容
if (size++ >= threshold)
resize(2 * table.length);
}
Entry構造方法中第四個引數很重要，我們知道HashMap是基於陣列和單鏈表的，陣列就是指的Entry陣列，而單鏈表呢？就在Entry物件的這個next屬性上
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
}
新增一個Entry到陣列中某一位置後，會同時給它指定它的next，這個next就是它所指向的下一個Entry元素，這樣，每次新增一個Entry都會把這個Entry加入到這個連結串列的第一個位置，它的next就是原來在第一個位置的Entry物件，這樣就連成了一個鏈子
添加了第一個Entry到陣列中某一index後，它的next指向的是一個null，因為在沒有新增的時候，這個index的位置存放的就是null值
此時我們的陣列中添加了第一個Entry，此時會判斷當前陣列的長度是否已經達到了極值（每次新增都會進行一次判斷），如果是則對陣列進行擴容，執行 resize(2 * table.length)可以看到，每次會擴容一倍的長度
/** * Rehashes the contents of this map into a new array with a * larger capacity.This method is called automatically when the * number of keys in this map reaches its threshold. * * If current capacity is MAXIMUM_CAPACITY, this method does not * resize the map, but sets threshold to Integer.MAX_VALUE. * This has the effect of preventing future calls. * * @param newCapacity the new capacity, MUST be a power of two; *must be greater than current capacity unless current *capacity is MAXIMUM_CAPACITY (in which case value *is irrelevant). */ void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //判斷當前陣列的長度是否已經達到了設定的MAXIMUM_CAPACITY //如果是則將threshold （達到這個值就滿足擴容的條件），設定為int的最大值 //那麼此時hashMap停止擴容，可見，hashMap容量是有極限的 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } //建立一個新的Entry陣列 Entry[] newTable = new Entry[newCapacity]; //將舊的陣列中的值經過轉換放入新的陣列中 transfer(newTable); //使用擴容後的陣列 table = newTable; //擴容閾值更新 threshold = (int)(newCapacity * loadFactor); }
HashMap擴容的原理也很簡單，因為它是基於陣列實現的，所以所謂的擴容並不是將原有的陣列長度擴大，而是建立了一個新的陣列，這個陣列的長度等於擴容後的長度，然後將舊陣列中的元素轉移到新陣列中，舊的陣列廢棄，這個轉移的過程仍然是經過了一系列的變換的，我們知道之前的陣列中每一個put進來的元素的index都是經過一系列的位運算得到的，那麼這裡在進行轉移的時候同樣要再次進行運算得到新的index，因為這個index是基於hash值和陣列長度生成的，hash值不會改變但是陣列長度經過擴容後是不同了，所以要重新計算，否則會導致查詢資料失敗
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
//遍歷舊的陣列中所有的Entry物件
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
//拿到index位置的Entry後，如果這個Entry不為null，則迴圈遍歷這個連結串列
if (e != null) {
src[j] = null;
do {
//拿到連結串列上每一個Entry
Entry<K,V> next = e.next;
//計算這個Entry在擴容後陣列中的index值
int i = indexFor(e.hash, newCapacity);
//設定這個Entry的next值
e.next = newTable[i];
//把這個Entry放在計算得到的index位置上
newTable[i] = e;
//賦值獲取下一個Entry，直到這個連結串列遍歷完成
e = next;
} while (e != null);
}
}
}
原始碼是這樣的先後順序放置的，如果你把順序調換一下會更好理解。這裡我們先調整一下程式碼的順序如下（不影響結果，但是更易理解）。大概過程就是假設我第一個找到了index=1的位置的這個單鏈表（這個連結串列可能只有一個元素，也可能有多個），我會獲取到這個位置的第一個Entry,計算得到它在新陣列中的index,然後把這個Entry放在這個陣列的index位置上，將它的next指定為原本這個位置的值，其實就是null,這是第一步，第二步就是獲取到第一個Entry的next值，也就是連結串列中第二個位置的Entry，把這個Entry重新指定為e，重複上邊的操作，這樣一整個過程下來，舊的陣列中的所有元素都被正確的放置在了新陣列中的正確位置上，達到了擴容的效果
do {
//計算這個Entry在擴容後陣列中的index值
int i = indexFor(e.hash, newCapacity);
//把這個Entry放在計算得到的index位置上
newTable[i] = e;
//設定這個Entry的next值
e.next = newTable[i];
//拿到連結串列上每一個Entry
Entry<K,V> next = e.next;
//賦值獲取下一個Entry，直到這個連結串列遍歷完成
e = next;
} while (e != null);
get方法
put看完之後get就簡單多了。根據傳入的key值，進行hash和indexFor運算，得到key在陣列中的index，然後拿到陣列中index位置的entry物件，再從這個位置的單鏈表中查詢key值相同的value返回
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}.(There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
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;
}
總結一下：
1.HashMap底層基於陣列和單鏈表
2.hash()和indexFor()方法作用很關鍵
3.如果你去看看native曾hashCode值獲取的方式，你會得到兩個結論(hashCode值並不是簡單的地址值，而是地址值進行右移16位之後的一個值，參閱ndk底層c++程式碼實現)：
兩個不同的物件 hashCode 值可能會相等，hashCode 值不相等的兩個物件肯定不是同一物件。
附上手寫的HashMap程式碼
public class MyHashMap<K,V> {
public MapEntry<K,V>[] table;
int size;
/**
* 擴容閾值,達到這個值時就要擴容
*/
int threshold = 8;
/**
* 擴容因子
*/
final float loadFactor = 0.75f;
public class MapEntry<K,V>{
private K key;
private V value;
MapEntry<K,V> next;
int hash;
public MapEntry(int hash,K key,V value,MapEntry<K,V> next) {
this.key = key;
this.value = value;
this.hash =hash;
this.next = next;
}
}
public V put(K key,V value) {
if(table == null) {
table = new MapEntry[8];
}
//判斷key為null
if(key == null) {
return null;
}
int hash = hash(key);
int index = getIndex(hash,table.length);
System.out.println("key = "+key+" hash="+hash+" index="+ index);
//判斷這個key是否存在
for (MapEntry<K,V> e = table[index]; e!=null;e = e.next) {
Object k = null;
if(e.hash == hash && ((k = e.key) == key) || (key.equals(k))){
V oldV = e.value;
e.value = value;
return oldV;
}
}
//新增新的
addEntry(hash,key,value,index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
//hash值相等，兩個物件不一定相等，兩個物件不相等，hash值有可能相等
//hashCode值 從native看，mask_bits(value()>> hash_shift,hash_mask))
//是地址右移16位的結果
if(size >= threshold && table[index] != null) {
//右移一位，擴容一倍
resize(size << 1);
//重新計算index
index = getIndex(hash,table.length);
}
//新增
createEntry(hash,key,value,index);
size++;
}
private void createEntry(int hash, K key, V value, int index) {
MapEntry<K, V> newEntry = new MapEntry<K, V>(hash, key, value, table[index]);
table[index] = newEntry;
}
private void resize(int newCapacity) {
MapEntry<K, V> [] newTable = new MapEntry[newCapacity];
//將原來陣列中的內容經過轉換之後放入新陣列
transform(newTable);
table = newTable;
threshold = (int) (newCapacity*loadFactor);
System.out.println("擴容之後：newCapacity="+newCapacity+" threshold="+threshold);
}
/**
* 重新計算雜湊
* @param newTable
*/
private void transform(MyHashMap<K, V>.MapEntry<K, V>[] newTable) {
int newCapacity = newTable.length;
for(MapEntry<K,V> e:table) {
while(null != e) {
MapEntry<K, V> next = e.next;
int index = getIndex(e.hash,newCapacity);
//把原來陣列中的e放在新的陣列中index位置
newTable[index] = e;
//將這個e插入到index位置的第一個，將原來index位置的e指定給e的next
e.next =newTable[index];
//把原來陣列中某index位置這條連結串列上的每一個元素都重新歸位
e = next;
}
}
}
/**
* 通過hash值找到table的index
* @param hash
* @return
*
* & : 兩位同時為“1”，結果才為“1”，否則為0
*/
private int getIndex(int hash,int length) {
return hash & length-1;
}
/**
* ^ : 就是相同為0不同為1
* @param key
* @return
*/
private int hash(K key) {
int h = 0;
h = key.hashCode();
int h16 = h>>>16;
return (key == null)?0:(h^(h16));
}
public V get(K key) {
if(key == null) {
return null;
}
MapEntry<K, V> entry = getEntry(key);
return entry == null?null:entry.value;
}
private MyHashMap<K, V>.MapEntry<K, V> getEntry(K key) {
int hash = hash(key);
int index = getIndex(hash,table.length);
for (MapEntry<K,V> e = table[index]; e!=null;e = e.next) {
Object k = null;
if(e.hash == hash && ((k = e.key) == key) || (key.equals(k))){
return e;
}
}
return null;
}
public int getSize() {
// TODO Auto-generated method stub
return size;
}
}