HashMap一句話就可以說個大概：
用哈希算法把key計算出索引index丈攒，然后將key芦瘾、value構(gòu)成的HashMapEntry放入HashMapEntry[index]际度，即完成了put功能首懈，get時將key重計算出index去取HashMapEntry菱农。
以上只是最表層的思想炕淮，如果不同key計算出相同的index呢？HashMapEntry里的next就起到作用了干毅。
HashMap
如上圖：橫排的Entry為HashMapEntry[]宜猜，縱向的箭頭表示同一index下存在多個Entry，Entry之間采用的是鏈?zhǔn)酱鎯Α?/p>
HashMap的大體設(shè)計思路就是如此了硝逢，接下來看看源碼是如何寫的（源碼是android-23）姨拥。
構(gòu)造函數(shù)
無參構(gòu)造函數(shù)：創(chuàng)建空表設(shè)置閾值
/**
* Min capacity (other than zero) for a HashMap. Must be a power of two
* greater than 1 (and less than 1 << 30).
*/
//HashMap最小的容量。此容量必須是以2為底的次方數(shù)渠鸽，且大于1小于2的30次方
private static final int MINIMUM_CAPACITY = 4;
/**
* An empty table shared by all zero-capacity maps (typically from default
* constructor). It is never written to, and replaced on first put. Its size
* is set to half the minimum, so that the first resize will create a
* minimum-sized table.
*/
//空表叫乌，容量是最小容量的一半
private static final Entry[] EMPTY_TABLE
= new HashMapEntry[MINIMUM_CAPACITY >>> 1];//無符號右移
public HashMap() {
table = (HashMapEntry<K, V>[]) EMPTY_TABLE;
threshold = -1; // Forces first put invocation to replace EMPTY_TABLE閾值超過閾值時需要擴(kuò)容
}
帶容量的構(gòu)造參數(shù)
對傳入的容量值稍作處理，然后創(chuàng)建表
/**
* Max capacity for a HashMap. Must be a power of two >= MINIMUM_CAPACITY.
*/
//吧啦吧啦徽缚，容量必須是以2為底的次方數(shù)憨奸，且大于MINIMUM_CAPACITY
private static final int MAXIMUM_CAPACITY = 1 << 30;
public HashMap(int capacity) {
if (capacity < 0) {//拋異常
throw new IllegalArgumentException("Capacity: " + capacity);
}
if (capacity == 0) {//容量為0時和無參構(gòu)造函數(shù)邏輯一致，我認(rèn)為可以HashMap()然后return搞定凿试，不需要重復(fù)代碼
@SuppressWarnings("unchecked")
HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;
table = tab;
threshold = -1; // Forces first put() to replace EMPTY_TABLE
return;
}
if (capacity < MINIMUM_CAPACITY) {
capacity = MINIMUM_CAPACITY;
} else if (capacity > MAXIMUM_CAPACITY) {
capacity = MAXIMUM_CAPACITY;
} else {
capacity = Collections.roundUpToPowerOfTwo(capacity);//獲取大于等于capacity并且是 2 的次方的整數(shù)
}
makeTable(capacity);
}
private HashMapEntry<K, V>[] makeTable(int newCapacity) {
@SuppressWarnings("unchecked") HashMapEntry<K, V>[] newTable
= (HashMapEntry<K, V>[]) new HashMapEntry[newCapacity];//根據(jù)傳入的容量創(chuàng)建數(shù)組
table = newTable;
threshold = (newCapacity >> 1) + (newCapacity >> 2); // 3/4 capacity
//設(shè)置容量閾值排宰，如果大于閾值則擴(kuò)充數(shù)組大小
return newTable;
}
帶負(fù)載因子的構(gòu)造方法
什么是負(fù)載因子？
HashMap的存儲結(jié)構(gòu)是一個數(shù)組那婉，數(shù)組內(nèi)的項為鏈表板甘。
數(shù)組的優(yōu)勢是查找迅速，由于分配的內(nèi)存空間連續(xù)详炬，但產(chǎn)生的index不一定連續(xù)盐类，所以會產(chǎn)生空間的浪費(fèi)。
鏈表的優(yōu)勢是增刪快速，但查找速度不如數(shù)組在跳，必須一個一個的向下查找枪萄。
負(fù)載因子的功能就是為了協(xié)調(diào)數(shù)組與鏈表之間的優(yōu)劣，負(fù)載因子大則鏈表的長度會大以致查找速度會降低硬毕，否則數(shù)組的長度大造成空間的浪費(fèi)呻引。
根據(jù)實(shí)際的使用情況礼仗，設(shè)置合適的負(fù)載因子吐咳。由于源碼并未實(shí)際設(shè)置，所以負(fù)載因子的功能只帶過元践。
/**
* Constructs a new {@code HashMap} instance with the specified capacity and
* load factor.
*
* @param capacity
* the initial capacity of this hash map.
* @param loadFactor
* the initial load factor.
* @throws IllegalArgumentException
* when the capacity is less than zero or the load factor is
* less or equal to zero or NaN.
*/
public HashMap(int capacity, float loadFactor) {
this(capacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Load factor: " + loadFactor);
}
/*
* Note that this implementation ignores loadFactor; it always uses
* a load factor of 3/4. This simplifies the code and generally
* improves performance.
*/
}
帶子集的構(gòu)造方法
根據(jù)子集的大小調(diào)整自身的數(shù)組大小韭脊，將子集數(shù)據(jù)裝填到自身。
public HashMap(Map<? extends K, ? extends V> map) {
//設(shè)置數(shù)組大小
this(capacityForInitSize(map.size()));
//裝填子集
constructorPutAll(map);
}
//返回需要的大小
static int capacityForInitSize(int size) {
int result = (size >> 1) + size; // Multiply by 3/2 to allow for growth
//對傳入的size乘以1.5单旁，但是移位的操作快速所以采用了移位代替乘
// boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY
//返回值要求>= 0 且<MAXIMUM_CAPACITY沪羔，具體如何實(shí)現(xiàn)
//假設(shè)MAXIMUM_CAPACITY為1000
//(MAXIMUM_CAPACITY-1)=0111
//~(MAXIMUM_CAPACITY-1)=1000
//所以result & ~(MAXIMUM_CAPACITY-1))的目的是去低位，與0一定為0象浑，除非高位不為0蔫饰，但高位不為0的話就大于MAXIMUM_CAPACITY了所以就有了如下
return (result & ~(MAXIMUM_CAPACITY-1))==0 ? result : MAXIMUM_CAPACITY;
}
//裝填
final void constructorPutAll(Map<? extends K, ? extends V> map) {
if (table == EMPTY_TABLE) {//如果是空表則翻倍空間大小
doubleCapacity(); // Don't do unchecked puts to a shared table.
}
for (Entry<? extends K, ? extends V> e : map.entrySet()) {
//組裝key value 進(jìn)行裝填
constructorPut(e.getKey(), e.getValue());
}
}
裝填項
private void constructorPut(K key, V value) {
if (key == null) {//key為null時維護(hù)entryForNullKey
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {
entryForNullKey = constructorNewEntry(null, value, 0, null);
size++;
} else {
entry.value = value;
}
return;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);//計算出index
HashMapEntry<K, V> first = tab[index];//此項不為空向下搜索鏈表
for (HashMapEntry<K, V> e = first; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
e.value = value;
return;
}
}
// No entry for (non-null) key is present; create one
tab[index] = constructorNewEntry(key, value, hash, first);
size++;
}
HashMapEntry<K, V> constructorNewEntry(
K key, V value, int hash, HashMapEntry<K, V> first) {
return new HashMapEntry<K, V>(key, value, hash, first);
}
PUT
public V put(K key, V value)
傳入key、value愉豺，計算hash
如果存在key則更新并返回舊值篓吁，否則添加新HashMapEntry并返回null
除此以外有一個特例，HashMap內(nèi)還維護(hù)了一個entryForNullKey用于存儲key=null時的value
@Override public V put(K key, V value) {
if (key == null) {
return putValueForNullKey(value);
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {
preModify(e);
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
// No entry for (non-null) key is present; create one
modCount++;
if (size++ > threshold) {
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
}
第一步存null的Key
transient int size;
transient int modCount;
//transient 此關(guān)鍵字不參與序列化蚪拦，存儲時不會保存杖剪，只存于此對象。
private V putValueForNullKey(V value) {
HashMapEntry<K, V> entry = entryForNullKey;
if (entry == null) {//不存在舊值
addNewEntryForNullKey(value);
size++;//總存儲量
modCount++;//修改次數(shù)
return null;
} else {//存在舊值
preModify(entry);//修改前操作
V oldValue = entry.value;
entry.value = value;
return oldValue;
}
}
void addNewEntryForNullKey(V value) {
entryForNullKey = new HashMapEntry<K, V>(null, value, 0, null);
}
//空實(shí)現(xiàn)驰贷，可以做一些修改前的預(yù)處理
void preModify(HashMapEntry<K, V> e) { }
第二步更新key
HashMapEntry<K, V>[] tab = table;
//由hash求得index
int index = hash & (tab.length - 1);
//遍歷鏈表
for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
if (e.hash == hash && key.equals(e.key)) {//key存在于HashMap中的條件：hash和key相同
preModify(e);//預(yù)處理
V oldValue = e.value;
e.value = value;//更新
return oldValue;
}
}
第三步存新key
能夠走到這里說明key不為null盛嘿，且之前沒有存儲過此key
modCount++;//修改計數(shù)加一
if (size++ > threshold) {//存儲空間大于閾值，加倍空間
tab = doubleCapacity();
index = hash & (tab.length - 1);
}
addNewEntry(key, value, hash, index);
return null;
增加空間大小
private HashMapEntry<K, V>[] doubleCapacity() {
HashMapEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
//如果已經(jīng)是最大的則無法增加
if (oldCapacity == MAXIMUM_CAPACITY) {
return oldTable;
}
//容量翻倍
int newCapacity = oldCapacity * 2;
HashMapEntry<K, V>[] newTable = makeTable(newCapacity);
//表中無數(shù)據(jù)直接返回
if (size == 0) {
return newTable;
}
//表中有數(shù)據(jù)括袒，需要將數(shù)據(jù)轉(zhuǎn)移到新表
for (int j = 0; j < oldCapacity; j++) {
//代碼見下
}
return newTable;
}
將數(shù)據(jù)轉(zhuǎn)移到新表
疑問：在對鏈表重新分布處理時次兆，如果鏈表內(nèi)的entry被放入新index，但源碼并未對entry前項的next指針賦null锹锰。索引使用時并不會有問題类垦，但同一對象指針被存在了兩處。沒看懂望高人指點(diǎn)城须。
for (int j = 0; j < oldCapacity; j++) {
/*
* Rehash the bucket using the minimum number of field writes.
* This is the most subtle and delicate code in the class.
*/
HashMapEntry<K, V> e = oldTable[j];
if (e == null) {//null不管
continue;
}
int highBit = e.hash & oldCapacity;//舊index
HashMapEntry<K, V> broken = null;
newTable[j | highBit] = e;//存入新的index
//對鏈表重新分布蚤认，疑問處
for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {
int nextHighBit = n.hash & oldCapacity;
if (nextHighBit != highBit) {
if (broken == null)
newTable[j | nextHighBit] = n;
else
broken.next = n;
broken = e;
highBit = nextHighBit;
}
}
if (broken != null)
broken.next = null;
}
新表處理過后進(jìn)行put
void addNewEntry(K key, V value, int hash, int index) {
table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}
GET
key為null的處理，否則由key計算hash找出index的項糕伐，對列表遍歷查找砰琢。
列表內(nèi)查找條件：
key地址相同
或
entry的hash相同且key的值相同
找不到返null
public V get(Object key) {
if (key == null) {
HashMapEntry<K, V> e = entryForNullKey;
return e == null ? null : e.value;
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
e != null; e = e.next) {
K eKey = e.key;
if (eKey == key || (e.hash == hash && key.equals(eKey))) {
return e.value;
}
}
return null;
}
Remove
@Override public V remove(Object key) {
if (key == null) {//key為空的情況
return removeNullKey();
}
int hash = Collections.secondaryHash(key);
HashMapEntry<K, V>[] tab = table;
int index = hash & (tab.length - 1);
for (HashMapEntry<K, V> e = tab[index], prev = null;
e != null; prev = e, e = e.next) {//鏈表的移除方式
if (e.hash == hash && key.equals(e.key)) {
if (prev == null) {
tab[index] = e.next;
} else {
prev.next = e.next;
}
modCount++;
size--;
postRemove(e);
return e.value;
}
}
private V removeNullKey() {
HashMapEntry<K, V> e = entryForNullKey;
if (e == null) {
return null;
}
entryForNullKey = null;
modCount++;
size--;
postRemove(e);
return e.value;
}
/**
* Subclass overrides this method to unlink entry.
*/
//空實(shí)現(xiàn) 移除后操作
void postRemove(HashMapEntry<K, V> e) { }
