HashMap源碼來自：android 25/java/util/HashMap 一、構造方法 下麵通過跟中源碼查看： table數組初始化 介紹put(K key, V value)方法前，先簡單介紹table數組初始化 ps： 這裡預設初始化了一個數組容量為16的table數組，其中關於roun ...
HashMap源碼來自：android-25/java/util/HashMap
一、構造方法
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int DEFAULT_INITIAL_CAPACITY = 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
// 參數預設為 4,0.75f
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 4 < MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
}
// 4 = DEFAULT_INITIAL_CAPACITY
else if (initialCapacity < DEFAULT_INITIAL_CAPACITY) {
initialCapacity = DEFAULT_INITIAL_CAPACITY;
}
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
threshold = initialCapacity;
init();
}ps：
init()為空方法；構造方法中只是做了HashMap數組容量欄位的一個簡單限制，最大為MAXIMUM_CAPACITY，最小為DEFAULT_INITIAL_CAPACITY
二、添加元素 put(K key, V value)
添加數據時，若出現衝突。
Java是通過 數組+鏈表 的形式解決衝突。效果如下圖所示：
- HashMap中有一個預設長度為16的table數組，當數組的容量達到預設長度的0.75倍時，則擴容兩倍；
- 其中table數組的每一項數據結構如下：
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key; // key
V value; // value
HashMapEntry<K,V> next; // 鏈表的下一項
int hash; // key 的hash值
}下麵通過跟中源碼查看：
table數組初始化
介紹put(K key, V value)方法前，先簡單介紹table數組初始化
// 添加key value
public V put(K key, V value) {
// 如果table列表為null，則用過inflateTable方法初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
...
return null;
}
// 初始化table數組
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
// 這裡計算一個2的n次方的數組容量，預設為2的4次方，為16
int capacity = roundUpToPowerOf2(toSize);
// 計算數組容量的0.75倍，超過數組容量0.75倍時，數組需要擴容
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
// 數組容量的0.75倍
threshold = (int) thresholdFloat;
// 初始化數組,預設容量capacity為16
table = new HashMapEntry[capacity];
}ps：
這裡預設初始化了一個數組容量為16的table數組，其中關於roundUpToPowerOf2(toSize)為什麼為2的n次方的問題，在下邊進行介紹
put(K key, V value)
// 添加key value
public V put(K key, V value) {
// 如果table列表為null，則用過inflateTable方法初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
// key 為null，則添加key為null的value
if (key == null)
return putForNullKey(value);
// 根據key獲取hash值
// Jenkins hash演算法，可參考以下鏈接：
// https://en.wikipedia.org/wiki/Jenkins_hash_function
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
// h & (length-1) 取餘太消耗性能，這裡通過位運算達到同樣的效果
// 獲取該key在table 數組的index
int i = indexFor(hash, table.length);
// 迴圈table[i]對應的鏈表
// 如果 hash值相同 && key相同，則替換對應value，並返回老的value值
// 註：這裡只是迴圈table[i]位置的鏈表，對於table數組未做迴圈
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 如果 hash值相同 && key相同，則替換對應value，並返回老的value值
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 以下兩種情況，則需要通過createEntry方法來看了
// hash相同 && key不同
// hash不同 && key不同
addEntry(hash, key, value, i);
return null;
}ps：
以上介紹了添加數據時，“如果 hash值相同 && key相同，則替換對應value，並返回老的value值”，但對於“hash相同 && key不同”與“hash不同 && key不同”情況，則需要在createEntry中進行說明
void addEntry(int hash, K key, V value, int bucketIndex) {
// 當數組的占用量，達到數組長度的0.75倍時，則需要擴容，擴展後的容量為原容量的2倍
// 數組擴容首先創建一個長度為原數組兩倍的數組，然後將老的數組數據賦值給新數組的對應項項目
// 數組擴容的代碼，這裡不再說明
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
// hash相同 && key不同
// hash不同 && key不同
createEntry(hash, key, value, bucketIndex);
}
// hash相同 && key不同
// hash不同 && key不同
void createEntry(int hash, K key, V value, int bucketIndex) {
// 取出table[bucketIndex]數組的原有值，可能為null，可能為HashMapEntry
// 若為null,則直接將value放在table[bucketIndex]位置就ok了
// 若不為null,則將新數組放到table[bucketIndex]位置，老數組放到新數據鏈表的next欄位
// hash衝突就是這樣解決了，可以看到確實與上圖一致，為數組+鏈表的方式解決衝突
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}ps：
通過createEntry方法，我們看到HashMap中通過數組+鏈表方式解決了Hash衝突，呼應了上圖
roundUpToPowerOf2(toSize)為什麼為2的n次方
打個比方：
- 當數組長度為15時，添加數組時
h & (length-1)計算成為hash&14（0x1110）,那麼最後一位永遠是0，從而造成table數組中 1（0x0001），3（0x0011），5（0x0101），7（0x0111），9（0x1001），11（0x1011）等位置永遠不可以存放數據，從而造成空間浪費； - 更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率。
ps：
關於 roundUpToPowerOf2(toSize)為什麼為2的n次方問題，詳細可查看
http://blog.csdn.net/yyh352091626/article/details/60866689?locationNum=4&fps=1
========== THE END ==========
