數組：其實所謂的數組指的就是一組相關類型的變量集合，并且這些變量彼此之間沒有任何的關聯。存儲區間連續，占用記憶體嚴重，數組有下标，查詢資料快，但是增删比較慢；
連結清單：一種常見的基礎資料結構，是一種線性表，但是不會按照線性的順序存儲資料，而是每一個節點裡存到下一個節點的指針。存儲區間離散，占用記憶體比較寬松，使用連結清單查詢比較慢，但是增删比較快；
哈希表：Hash table 既滿足了資料的快速查詢（根據關鍵碼值key value 而直接進行通路的資料結構），也不會占用太多的記憶體空間，十分友善。哈希表是數組加連結清單組成。
HashMap結構及原理
HashMap是基于哈希表的Map接口的非同步實作。實作HashMap對資料的操作，允許有一個null鍵，多個null值。
HashMap底層就是一個數組結構，數組中的每一項又是一個連結清單。數組+連結清單結構，建立一個HashMap的時候，就會初始化一個數組。Entry就是數組中的元素，每個Entry其實就是一個key-value的鍵值對，它持有一個指向下一個元素的引用，這就構成了連結清單，HashMap底層将key-value當成一個整體來處理，這個整體就是一個Entry對象。HashMap底層采用一個Entry【】數組來儲存所有的key-value鍵值對，當需要存儲一個Entry對象時，會根據hash算法來決定在其數組中的位置，在根據equals方法決定其在該數組位置上的連結清單中的存儲位置；當需要取出一個Entry對象時，也會根據hash算法找到其在數組中的存儲位置， 在根據equals方法從該位置上的連結清單中取出Entry;
HashMap的存儲
put：（key-value）方法是HashMap中最重要的方法，使用HashMap最主要使用的就是put，get兩個方法。
- 判斷鍵值對數組table[i]是否為空或者為null，否則執行resize（）進行擴容；
- 根據鍵值key計算hash值得到插入的數組索引 i ,如果table[i] == null ，直接建立節點添加即可，轉入6，如果table[i] 不為空，則轉向3；
- 判斷table[i] 的首個元素是否和key一樣，如果相同（hashCode和equals）直接覆寫value，否則轉向4；
- 判斷table[i] 是否為treeNode，即table[i]是否為紅黑樹，如果是紅黑樹，則直接插入鍵值對，否則轉向5；
- 周遊table[i] ,判斷連結清單長度是否大于8，大于8的話把連結清單轉換成紅黑樹，進行插入操作，否則進行連結清單插入操作；便利時遇到相同key直接覆寫value；
- 插入成功後，判斷實際存在的鍵值對數量size是否超過了threshold，如果超過，則擴容；
看一下put源碼
get方法取值過程：
int hash = key.hashCode（）；
int index = hash%Entry[].length;
- 指定key通過hash函數得到key的hash值；
- 調用内部方法getNode（），得到桶号（一般為hash值對桶數求摸）；
- 比較桶的内部元素是否和key相等，如不相等，則沒有找到，相等，則取出相等記錄的value；
- 如果得到key所在桶的頭結點恰好是紅黑樹節點，就調用紅黑樹節點的getTreeNode（）方法，否則就周遊連結清單節點。getTreeNode（）方法通過調用樹形節點的find（）方法進行查找。由于之前添加時已經保證這個樹是有序的，是以查找時基本就是折半查找，效率高；
- 如果對比節點的哈希值和要查找的哈希值相等，就會判斷key是否相等，相等就直接傳回；不相等就從子樹中遞歸查找；
HashMap中直接位址用hash函數生成，沖突用比較函數解決。如果每個桶内部隻有一個元素，那麼查找的時候隻有一次比較。當許多桶内沒有值得時候，許多查詢就會更快
addEntry方法
- 添加新元素前，判斷是否需要對map的數組進行擴容，如果需要擴容，則擴容多大？
- 對于新增key-value鍵值對，如果可以的hash值相同，則構造單向清單；
源碼分析：
createEntry
該方法主要完成兩個功能，一個是添加新的key到Entry數組中，第二個就是對于不同的key的hash值相同的情況下，在同一個數組下标出，建構單向連結清單進行存儲；
源碼如下：
HashMap碰撞以及解決方法（開放定址法，在哈希法，鍊位址法，建立一個公共溢出區）
當兩個對象的hashCode相同時，他們的bucket位置相同，hash碰撞就會發生。因為HashMap使用LinkedList存儲對象，這個Entry（存儲鍵值對的Map.Entry對象）會存儲在LinkedList中。這兩個對象算hashCode相同，但是他們可能并不相等。那麼如何擷取這兩個對象的值呢？當我們調用get（）方法，HashMap會使用鍵值對象的hashCode找到bucket位置，周遊LinkedList一直找到值對象。找到bucket位置以後，會調用keys.equals（）方法去找到LinkedList中正确的節點，最終找到要找的值對象，使用final修飾，并采用合适的equals（）和hashCOde（）方法，減少碰撞。
HashMap擴容機制
擴容必須滿足兩個條件
- 存放新值的時候目前已有元素必須大于門檻值；
- 存放新值的時候目前存放資料發生hash碰撞（目前key計算的hash值計算出的數組索引位置已經存在值）
- HashMap在添加值的時候，它預設能存儲16個鍵值對，直到你使用這個HashMap時，它才會給HashMap配置設定16個鍵值對的存儲空間，（負載因子為0.75,門檻值為12），當16個鍵值對已經存儲滿了，我們在添加第17個鍵值對的時候才會發生擴容現象，因為前16個值，每個值在底層數組中分别占據一個位置，并沒有發生hash碰撞。
- HashMap也有可能存儲更多的鍵值對，最多可以存儲26個鍵值對，我們來算一下：存儲的前11個值全部發生hash碰撞，存到數組的同一個位置中，（這時元素個數小于門檻值12，不會擴容），之後存入15個值全部分散到數組剩下的15個位置中，（這時元素個數大于等于門檻值，但是每次存入元素并沒有發生hash碰撞，不會擴容），11+15=26，當我們存入第27個值得時候滿足以上兩個條件，HashMap才會發生擴容；