HashMap其原理是底層是一個(gè)table數(shù)組+鏈表兄墅，數(shù)組的每一項(xiàng)是一個(gè)鏈表頭。當(dāng)然不同的jar包對應(yīng)的HashMap源碼還是有點(diǎn)出入的芋膘，以下以安卓的為準(zhǔn)祭钉。
而存入數(shù)組中的元素是Entry，Entry可以理解為一個(gè)封裝了key和value的對象它改，我們存進(jìn)入的其實(shí)是一個(gè)Entry對象疤孕，里面包含了key和value值。
分析一下put方法：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<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;
}
new一個(gè)HashMap時(shí)候央拖，其實(shí)并沒有創(chuàng)建一片內(nèi)存地址祭阀，只有在put時(shí)候才會去判斷table是否為空，如果為空才創(chuàng)建鲜戒。
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
put方法里面先判斷key值是否為空专控，如果是空的話，直接返回空值遏餐。
if (key == null)
return putForNullKey(value);
如果key不為空的話伦腐，通過key計(jì)算獲取到hash值
然后通過hash值獲取到數(shù)組中相應(yīng)的索引，這里要注意一下失都，如果put多個(gè)的話柏蘑，數(shù)組角標(biāo)i的值是有可能一樣的幸冻，因?yàn)閿?shù)組存的每一項(xiàng)其實(shí)也是一個(gè)鏈表頭，如果當(dāng)期數(shù)組已經(jīng)有put進(jìn)entry對象的話咳焚，那么就通過鏈表插入值洽损，采用的是頭插法。
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
獲取到數(shù)組角標(biāo)后黔攒，通過角標(biāo)去for循環(huán)遍歷這個(gè)角標(biāo)下的鏈表趁啸，如果是當(dāng)前key是之前已經(jīng)有插入的相同的key强缘，那么就把新值插入之前相同的key中督惰，然后把舊的value return回來
for (HashMapEntry<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;
}
}
如果key是新的key的話，就新增一個(gè)entry旅掂，當(dāng)前的hash值赏胚，數(shù)值角標(biāo)，key商虐，value值存進(jìn)去
ddEntry(hash, key, value, i);
分析一下get方法：
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry<K,V> 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;
}
通過get方法可以看出觉阅，調(diào)用了getEntry方法，通過key獲取到entry對象秘车，如果對象為空典勇，只返回空值，如果對象不為空叮趴，則返回相應(yīng)的value值割笙。
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
重點(diǎn)要看下getEntry方法，通過源碼可以看通過key獲取到了hash值眯亦，然后通過for循環(huán)遍歷相應(yīng)數(shù)組角標(biāo)下的鏈表伤溉，判斷key值一樣，并且hash值一樣的話妻率，就返回相應(yīng)的entry對象乱顾。
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
for (HashMapEntry<K,V> 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;
}
而且遍歷是從鏈表頭開始遍歷的，這也說明了越后面的put進(jìn)去的值被找到的時(shí)間越短宫静。
關(guān)于擴(kuò)容問題
從源碼中可以看出在put里面的addEntry方法進(jìn)行判斷走净，當(dāng)數(shù)組不為空或者put數(shù)量（size）大于16個(gè)時(shí)候，就會進(jìn)行擴(kuò)容孤里，擴(kuò)容了一倍伏伯。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
