寫在前面
HashMap源碼分析，可以說是面試中必問的題目。作為以key/value存儲方式的集合，HashMap的集成了鏈表的思想；此外1.8引入了紅黑樹的思想。今天這篇文章著重聊一聊1.8之前的HashMap~
接下來會用到的幾個常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final int MAXIMUM_CAPACITY = 1 << 30;
正文
HashMap的思路
我們put的key/value會被封裝成一個叫做Entry的內部類。這個Entry由一個變量名為table數組管理。我們每次put會通過一系列的計算，計算一個table數組的index下標用於放Entry，如果出現hash衝突使用鏈表法解決。get時，可以理解是一個反向的put過程。
put(K key, V value)
1、初始化
走到這一步，相當於我們的第一次put的初始化過程完成。那麼接著讓我們看下一步操作。
2、key為null
當然這一步的前面還有一個key為null的情況。因為實在是太直白，就不單獨展開，代碼如下：
這裡我們可以得到一個信息，key為null的Entry會放在table[0]的位置上。
3、index下標計算
走到這一步，我們所要做的就是先計算我們這個key/value應該放在table的那個位置。也就是說，在真正包裝成Entry之前，我們需要確定這個Entry的應該再哪個坑裡。
計算hash值的hash方法如下：
計算完hash之後，就是通過hash計算我們Entry應該在那個下標中：
走到這一步我們Entry該放在哪個位置已經明確了，這裡有很多位運算…根據效果來看，這樣的計算方式保證了，Entry更少的衝突。
4、插入Entry
既然上訴2的過程已經確定了插入位置，那麼毫無疑問，我們該插入這個Entry了。
4.1、重複key處理
既然插入，那麼勢必有可能遇到重複問題，比如說，我們插入同一個key。這裡就是一個比較常見的問題，Map可不可以使用重複key，或者Map怎樣處理重複key的問題。
因此關於key重複的問題，我們就可以得到答案。Map的操作是替換舊的value並返回老的value。
4.2、擴容
上訴步驟我們處理的key重複的問題。那麼接下來，就是Map的擴容過程。這裡會用到一個變量threshold，我們知道初始化table之後，這個變量 = 數組長度*0.75。記住這個值，它就是擴容的閾值。
4.3、創建並添加
首先獲取index下標下的Entry，我們明白這裡的e有可能為空。（而這裡沒有對null這種情況進行判斷，也就是說這裡為不為空都無所謂）
拿到e之後，進行new Entry()把e，以及hash，key，value傳了進來。
這裡我們看一個e，放在了哪裡？
這裡說明一個什麼問題？那就是當hash衝突之後，我們的Entry是在鏈表的頭還是尾。根據代碼來看，很明顯是在鏈表的頭，這也說明了，為什麼e為null這種情況沒有做特別處理。
我們對put的分析就到此為止，既然分析了put，那麼接下來就是get。
get(Object key)
1、處理key為null的情況
關於key為null的情況，其實我們也能看出，比較簡單明瞭。接下來就是key不為null的情況。
2、key不為null
代碼思路比較的明確，其實就是一個反向的put過程。我們先通過key計算hash，然後計算對應Entry在數組中的index，然後遍歷對應鏈，找出匹配的value即可。
get方法我們可以看出，是比較簡單的。
尾聲
分析完put/get其實基本上HashMap就梳理完畢。
這裡我們進行一點總結：
- 1、put時，key可以為空。並且放在table[0]的這個位置
- 2、擴容策略是，size>=當前容量*0.75並且當前table[index]不為null。擴容大小為2倍。
- 3、JDK1.7的HashMap使用鏈表法解決衝突，並且新插入的Entry是在鏈表的表頭。
閱讀更多 碼農登陸 的文章
