本篇博客僅為本人了解HashMap原理過程中界逛，查閱多篇博客后躯喇，為了加強記憶藤抡，寫下此篇侠碧，在此對多篇博客多有借鑒
HashMap概述
HashMap是基于哈希表的Map接口的非同步實現(xiàn)。此實現(xiàn)提供所有可選的映射操作缠黍，并允許使用null值和null鍵弄兜。此類不保證映射的順序，特別是它不保證該順序恒久不變瓷式。
HashMap數(shù)據(jù)結(jié)構(gòu)
HashMap中數(shù)據(jù)的存儲是由數(shù)組與鏈表一起實現(xiàn)的替饿。HashMap底層就是一個數(shù)組結(jié)構(gòu)，數(shù)組中的每一項又是一個鏈表贸典。當新建一個HashMap的時候视卢，就會初始化一個數(shù)組。
數(shù)組
數(shù)組是在內(nèi)存中開辟一段連續(xù)的空間廊驼，因此占用內(nèi)存嚴重据过，故空間復(fù)雜的很大惋砂。我們只要知道數(shù)組首個元素的地址，在數(shù)組中尋址就會非常容易蝶俱，其時間復(fù)雜度為O(1)班利。但是當要插入或刪除數(shù)據(jù)時，時間復(fù)雜度就會變?yōu)镺(n)榨呆。數(shù)組的特點是：尋址容易罗标，插入和刪除困難；
鏈表
鏈表在內(nèi)存的存儲區(qū)間是離散的积蜻，其插入和刪除操作的內(nèi)存復(fù)雜度為O(1)闯割，但是尋址操作的復(fù)雜度卻是O(n)。鏈表的特點是：尋址困難竿拆，插入和刪除容易宙拉。
從上圖中可以看出，HashMap底層就是一個數(shù)組結(jié)構(gòu)丙笋，數(shù)組中的每一項又是一個鏈表谢澈。當新建一個HashMap的時候，就會初始化一個數(shù)組御板。
HashMap原理
HashMap類有一個叫做Entry的內(nèi)部類锥忿。這個Entry類包含了key-value作為實例變量。 每當往hashmap里面存放key-value對的時候怠肋，都會為它們實例化一個Entry對象敬鬓，這個Entry對象就會存儲在前面提到的Entry數(shù)組table中。Entry具體存在table的那個位置是 根據(jù)key的hash值來決定笙各。
/**
* The table, resized as necessary. Length MUST Always be a power of two.
*/
transient Entry<K,V>[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
Entry就是數(shù)組中的元素钉答，每個 Map.Entry 其實就是一個key-value對，它持有一個指向下一個元素的引用杈抢，這就構(gòu)成了鏈表数尿。
HashMap存取實現(xiàn)
存儲
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
//HashMap允許存放null鍵值
//當key為null是，調(diào)用putForNullKey()方法春感，將value插入到數(shù)組的第一個位置砌创，即角標為0的位置
if (key == null)
return putForNullKey(value);
//計算key的hash值
int hash = hash(key);
//搜索hash值對應(yīng)的指定數(shù)組的索引
int i = indexFor(hash, table.length);
//如果i處的索引處Entry不為null，遍歷e元素的下一個元素
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;
}
}
//如果i出索引Entry為null鲫懒，表明此處沒有Entry
modCount++;
//將key和value添加到i處索引
addEntry(hash, key, value, i);
return null;
}
從上面的源代碼中可以看出：當我們往HashMap中put元素的時候嫩实，先根據(jù)key的hash值存哲，得到這個元素在數(shù)組中的位置（即下標）躁劣，然后再在該索引上的單向鏈表進行循環(huán)遍歷用equals比較key是否存在，如果存在則用新的value覆蓋原值立磁，如果不存在颂翼，則插入鏈表的頭部晃洒，這與后面的多線程安全相關(guān)慨灭。
putForNullKey(V value)方法
/**
* Offloaded version of put for null keys
*/
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;
}
addEntry(int hash, K key, V value, int bucketIndex) 方法
根據(jù)計算出的hash值，將key-value對放在數(shù)組table的i索引處球及。addEntry 是 HashMap 提供的一個包訪問權(quán)限的方法氧骤，代碼如下：
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The next size value at which to resize (capacity * load factor).一般是大于0.75，開始擴容吃引，double
* @serial
*/
int threshold;
/**
* 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) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
createEntry(int hash, K key, V value, int bucketIndex)方法
/**
* Like addEntry except that this version is used when creating entries
* as part of Map construction or "pseudo-construction" (cloning,
* deserialization). This version needn't worry about resizing the table.
*
* Subclass overrides this to alter the behavior of HashMap(Map),
* clone, and readObject.
*/
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
讀取
/**
* 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) {
//如果key為null筹陵，調(diào)用getForNullkey()方法，如果數(shù)組0角標對應(yīng)的Entry不為null镊尺，遍歷e元素的下一個元素
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
從上面的源代碼中可以看出：從HashMap中g(shù)et元素時朦佩，首先計算key的hash值，找到數(shù)組中對應(yīng)位置的某一元素庐氮，然后通過key的equals方法在對應(yīng)位置的鏈表中找到需要的元素语稠。
getForNullKey()方法
/**
* Offloaded version of get() to look up null keys. Null keys map
* to index 0. This null case is split out into separate methods
* for the sake of performance in the two most commonly used
* operations (get and put), but incorporated with conditionals in
* others.
*/
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
getEntry(Object key)方法
/**
* Returns the entry associated with the specified key in the
* HashMap. Returns null if the HashMap contains no mapping
* for the key.
*/
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
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 != null && key.equals(k))))
return e;
}
return null;
}
總結(jié)
HashMap 在底層將 key-value 當成一個整體進行處理，這個整體就是一個 Entry 對象弄砍。HashMap 底層采用一個 Entry[] 數(shù)組來保存所有的 key-value 對仙畦，當需要存儲一個 Entry 對象時，會根據(jù)hash值來決定其在數(shù)組中的存儲位置音婶，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置议泵；當需要取出一個Entry時，也會根據(jù)hash值找到其在數(shù)組中的存儲位置桃熄，再根據(jù)equals方法從該位置上的鏈表中取出該Entry。
山外山
HashMap的兩個重要屬性是容量capacity和裝載因子loadfactor型奥，默認值分別為16和0.75瞳收，當容器中的元素個數(shù)大于 capacity*loadfactor = 12時，容器會進行擴容resize 為2n厢汹，在初始化Hashmap時可以對著兩個值進行修改螟深，負載因子0.75被證明為是性能比較好的取值，通常不會修改烫葬，那么只有初始容量capacity會導(dǎo)致頻繁的擴容行為界弧，這是非常耗費資源的操作，所以搭综，如果事先能估算出容器所要存儲的元素數(shù)量垢箕，最好在初始化時修改默認容量capacity，以防止頻繁的resize操作影響性能兑巾。
java8對hashmap做了優(yōu)化 条获，底層有兩種實現(xiàn)方法，一種是數(shù)組和鏈表蒋歌，一種是數(shù)組和紅黑樹帅掘，hsahmap會根據(jù)數(shù)據(jù)量選擇存儲結(jié)構(gòu)
if (binCount >= TREEIFY_THRESHOLD - 1)
當符合這個條件的時候委煤，把鏈表變成treemap，這樣查找效率從o(n)變成了o(log n)
