什么是HashMap，文章內(nèi)HashMap源碼主要來自Android 7.0
HashMap是開發(fā)中常用的一個(gè)類巷屿，那么他究竟是什么呢导俘？
HashMap是一個(gè)存儲key-value的集合槐雾，底層實(shí)現(xiàn)的是數(shù)組巾遭，所以可以看作HashMap是對數(shù)組的一種封裝。
構(gòu)造方法
不管調(diào)用的是哪一個(gè)方法平道， 最終都會回調(diào)兩個(gè)參數(shù)的這個(gè)構(gòu)造函數(shù)睹欲，第一個(gè)參數(shù)是容量，第二個(gè)參數(shù)是閾值（用于擴(kuò)容的時(shí)候計(jì)算容量）
先看看HashMap主要的成員變量
/**
* HashMap默認(rèn)容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 4;
/**
* HashMap最大可存儲的容量值 1<<30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 加載因子（閾值）如果put進(jìn)來的元素?cái)?shù)量>=總數(shù)量*0.75的時(shí)候一屋， 就會進(jìn)行擴(kuò)容了
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* EMPTY_TABLE 看了一下窘疮，好像沒啥用。冀墨。考余。
*/
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
/**
* 這個(gè)size表示容量值，put了幾次轧苫，這個(gè)size就是幾楚堤，所以我們方法中用的size() 就是返回的這個(gè)值
*/
transient int size;
因?yàn)镠ashMap常用的就是get和put，所以主要分析一下這兩個(gè)方法含懊，在講這個(gè)之前身冬，先看一下HashMapEntry這個(gè)類吧
HashMapEntry
HashMapEntry繼承自Map.Entry
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
HashMapEntry<K,V> next;
int hash;
...
}
HashMapEntry的結(jié)構(gòu)是鏈表(在api25之前是鏈表,在api26開始引入了紅黑樹, 當(dāng)節(jié)點(diǎn)>8個(gè)的時(shí)候會轉(zhuǎn)為紅黑樹, 節(jié)點(diǎn)<6個(gè)的時(shí)候又會轉(zhuǎn)回為鏈表, 紅黑樹跳這里HashMap在Api26后的應(yīng)用---紅黑樹篇)，所以存儲數(shù)據(jù)的時(shí)候是這樣的
關(guān)于鏈表可參考其他文章
現(xiàn)在來講一講HashMap的put和get
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;
}
整個(gè)put的方法并不長岔乔，首次進(jìn)來時(shí)會判斷table是不是EMPTY_TABLE酥筝，就是上面那兩數(shù)組，然后會執(zhí)行inflatetable方法雏门，這個(gè)方法就不看了嘿歌。。茁影。只有第一次put時(shí)候才會進(jìn)入宙帝，因?yàn)橹挥心莻€(gè)時(shí)候table==EMPTY_TABLE，在inflatetable里募闲，table就會被重新賦值
接下來看第二個(gè)判斷 key==null
看看這個(gè)方法putForNullKey()
private V putForNullKey(V value) {
for (HashMapEntry<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;
}
如果已經(jīng)有了一個(gè) key為null的元素步脓，那么就會替換他的value值，所以HashMap只能由一個(gè)空key。
sun.misc.Hashing.singleWordWangJenkinsHash(key);這個(gè)方法就是根據(jù)key計(jì)算hash值靴患，然后通過indexFor方法算出key在table中的下標(biāo)仍侥。由于數(shù)組的存儲方式大概是這樣的
但是由于下標(biāo)是根據(jù)key的hash和數(shù)組長度計(jì)算來的，所以有可能下標(biāo)會一樣鸳君，這個(gè)時(shí)候HashMapEntry這個(gè)鏈表的用處就體現(xiàn)出來了农渊，如果下標(biāo)一樣的時(shí)候，那么就會比對HashMapEntry的key值是否一致或颊，如果一致砸紊，就替換原key-value，如果沒有與新添加的key一致的值饭宾，就會在HashMapEntry中新加一個(gè)節(jié)點(diǎn)批糟，所以現(xiàn)在的存儲方式變成了這樣
如果是替換就value格了，會直接吧舊的value返回回去看铆，如果不是的話就會走addEntry方法， 這個(gè)方法有三個(gè)作用
- 擴(kuò)容
- 拷貝數(shù)據(jù)
- 插入新數(shù)據(jù)
跟進(jìn)一下addEntry方法
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);
}
首先判斷的是size是否大于閾值（總?cè)萘?0.75）盛末，并且table[bucketIndex]弹惦！=null, 所以只有兩個(gè)條件成立的時(shí)候才會進(jìn)行擴(kuò)容
resize（）
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
newCapacity的大小等于就數(shù)組長度*2， 所以下方構(gòu)建的newTable的長度就是原數(shù)組的長度兩倍悄但，到這里棠隐，就進(jìn)行擴(kuò)容完畢了，但是新數(shù)組是有了檐嚣，但是沒數(shù)據(jù)爸蟆！不急嚎京，看transfer方法
transfer（）
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
看到了吧嗡贺，或進(jìn)行一個(gè)雙層循環(huán)，先循環(huán)數(shù)組鞍帝，然后在循環(huán)里面節(jié)點(diǎn)诫睬，直到next==null的時(shí)候，會跳出當(dāng)前循環(huán)帕涌，進(jìn)行下一次循環(huán)摄凡，直到循環(huán)完畢，也就是新數(shù)據(jù)賦值完畢
再回到resize方法蚓曼，再看下面的代碼亲澡，把新數(shù)組newTable又給了table，threshold又得到了擴(kuò)容后新的閾值纫版，到這一步谷扣，擴(kuò)容和拷貝數(shù)據(jù)就已經(jīng)完成了。
再回看addEntry方法，又會更具新數(shù)組的大小和key的hash值重新計(jì)算下標(biāo)会涎，傳遞給createEntry（hash, key, value, bucketIndex）方法中裹匙，
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
到此，hashmap的put就結(jié)束了末秃，回頭看看概页。。练慕。其實(shí)還算蠻簡單的哈
那么get方法呢惰匙？
get
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)用這個(gè)getEntry方法，看看里面的方法是不是很眼熟铃将，計(jì)算hash项鬼，比對key。
對劲阎！就是這么簡單绘盟，同樣也是根據(jù)hash和數(shù)組長度獲取下標(biāo)，然后就是這么一個(gè)循環(huán)悯仙，只要hash值一樣并且key有一樣的就會返回這個(gè)元素龄毡，否則就是返回null
總結(jié)一下：
put添加元素的操作為：
計(jì)算key的hash ==> 根據(jù)hash和數(shù)組長度計(jì)算對應(yīng)的數(shù)組下標(biāo) ==> 如果當(dāng)前下標(biāo)內(nèi)容為null，就直接添加锡垄，否則的話會進(jìn)入一個(gè)循環(huán)沦零，在這個(gè)循環(huán)中去尋找鏈表內(nèi)有沒有當(dāng)前key值，有的話替換原value货岭，沒有的話插入到最后一個(gè)節(jié)點(diǎn)
get獲取元素
計(jì)算key的hash ==> 根據(jù)hash和數(shù)組長度計(jì)算對應(yīng)的數(shù)組下標(biāo) ==> 如果當(dāng)前下標(biāo)元素不為null路操，進(jìn)入循環(huán)，在這個(gè)循環(huán)中去尋找鏈表內(nèi)有沒有當(dāng)前key值千贯，有的話返回屯仗，沒有的話就返回null
get就不畫了啊 自行體會
話說你們畫圖都用啥啊。丈牢。祭钉。 我這大晚上的用截圖工具扣扣畫畫好累，win10自帶的畫圖工具感覺用不來
