什么是HashMap，文章內(nèi)HashMap源碼主要來自Android 7.0
HashMap是開發(fā)中常用的一個類，那么他究竟是什么呢？
HashMap是一個存儲key-value的集合，底層實現(xiàn)的是數(shù)組，所以可以看作HashMap是對數(shù)組的一種封裝。
構(gòu)造方法
不管調(diào)用的是哪一個方法， 最終都會回調(diào)兩個參數(shù)的這個構(gòu)造函數(shù)，第一個參數(shù)是容量，第二個參數(shù)是閾值（用于擴容的時候計算容量）
先看看HashMap主要的成員變量
/**
* HashMap默認容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 4;
/**
* HashMap最大可存儲的容量值 1<<30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 加載因子（閾值）如果put進來的元素數(shù)量>=總數(shù)量*0.75的時候， 就會進行擴容了
*/
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;
/**
* 這個size表示容量值，put了幾次，這個size就是幾，所以我們方法中用的size() 就是返回的這個值
*/
transient int size;
因為HashMap常用的就是get和put，所以主要分析一下這兩個方法，在講這個之前，先看一下HashMapEntry這個類吧
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開始引入了紅黑樹, 當節(jié)點>8個的時候會轉(zhuǎn)為紅黑樹, 節(jié)點<6個的時候又會轉(zhuǎn)回為鏈表, 紅黑樹跳這里HashMap在Api26后的應用---紅黑樹篇)，所以存儲數(shù)據(jù)的時候是這樣的
關(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;
}
整個put的方法并不長，首次進來時會判斷table是不是EMPTY_TABLE，就是上面那兩數(shù)組，然后會執(zhí)行inflatetable方法，這個方法就不看了。。。只有第一次put時候才會進入，因為只有那個時候table==EMPTY_TABLE，在inflatetable里，table就會被重新賦值
接下來看第二個判斷 key==null
看看這個方法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)有了一個 key為null的元素，那么就會替換他的value值，所以HashMap只能由一個空key。
sun.misc.Hashing.singleWordWangJenkinsHash(key);這個方法就是根據(jù)key計算hash值，然后通過indexFor方法算出key在table中的下標。由于數(shù)組的存儲方式大概是這樣的
但是由于下標是根據(jù)key的hash和數(shù)組長度計算來的，所以有可能下標會一樣，這個時候HashMapEntry這個鏈表的用處就體現(xiàn)出來了，如果下標一樣的時候，那么就會比對HashMapEntry的key值是否一致，如果一致，就替換原key-value，如果沒有與新添加的key一致的值，就會在HashMapEntry中新加一個節(jié)點，所以現(xiàn)在的存儲方式變成了這樣
如果是替換就value，會直接吧舊的value返回回去，如果不是的話就會走addEntry方法， 這個方法有三個作用
- 擴容
- 拷貝數(shù)據(jù)
- 插入新數(shù)據(jù)
跟進一下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, 所以只有兩個條件成立的時候才會進行擴容
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ù)組的長度兩倍，到這里，就進行擴容完畢了，但是新數(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;
}
}
}
看到了吧，或進行一個雙層循環(huán)，先循環(huán)數(shù)組，然后在循環(huán)里面節(jié)點，直到next==null的時候，會跳出當前循環(huán)，進行下一次循環(huán)，直到循環(huán)完畢，也就是新數(shù)據(jù)賦值完畢
再回到resize方法，再看下面的代碼，把新數(shù)組newTable又給了table，threshold又得到了擴容后新的閾值，到這一步，擴容和拷貝數(shù)據(jù)就已經(jīng)完成了。
再回看addEntry方法，又會更具新數(shù)組的大小和key的hash值重新計算下標，傳遞給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é)束了，回頭看看。。。其實還算蠻簡單的哈
那么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)用這個getEntry方法，看看里面的方法是不是很眼熟，計算hash，比對key。
對！就是這么簡單，同樣也是根據(jù)hash和數(shù)組長度獲取下標，然后就是這么一個循環(huán)，只要hash值一樣并且key有一樣的就會返回這個元素，否則就是返回null
總結(jié)一下：
put添加元素的操作為：
計算key的hash ==> 根據(jù)hash和數(shù)組長度計算對應的數(shù)組下標 ==> 如果當前下標內(nèi)容為null，就直接添加，否則的話會進入一個循環(huán)，在這個循環(huán)中去尋找鏈表內(nèi)有沒有當前key值，有的話替換原value，沒有的話插入到最后一個節(jié)點
get獲取元素
計算key的hash ==> 根據(jù)hash和數(shù)組長度計算對應的數(shù)組下標 ==> 如果當前下標元素不為null，進入循環(huán)，在這個循環(huán)中去尋找鏈表內(nèi)有沒有當前key值，有的話返回，沒有的話就返回null
get就不畫了啊 自行體會
話說你們畫圖都用啥啊。。。 我這大晚上的用截圖工具扣扣畫畫好累，win10自帶的畫圖工具感覺用不來
