Hashmap
原理
hashmap的底層數據結構散列表，即：數組+鍊表，創建的時候初始化一個數組，每個節點可以為一個鍊表
當一鍵值對發生put操作時，
首先根據key的hash值得到這個元素在數組中的位置（即下標），如果這個位置上已經存在其他元素，將進行下一步操作。
由於同一點是鍊表方式存儲，會將原來的元素向後推然後新的元素放在這個位置上put操作可能會出現衝突，衝突分兩種：
不同的key值，通過hash函數得出相同的index，這種衝突通過上面所說的鍊表方式存儲。相同的key值，直接覆蓋。所以為了減少衝突，儘量將hashmap 的長度設置為2的次方，因為如果不是2的次方，經過hash & 操作，最後一位總是0如下圖，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，而且這樣可以使用的位置比數組長度小了很多，增加了衝突的機率，故減慢的查詢的效率（如果每一個節點都不存在鍊表，則不需要循環，查詢效率會高，所以儘量均勻分布）。
同理，當一鍵值對發生get操作時，會經過hash函數計算得到index，如果節點為鍊表有多個元素，則迭代用key.equals()比較獲取。
容量
源碼多了噁心，少量如下：
Java代碼
static final int DEFAULT_INITIAL_CAPACITY = 16; static final int MAXIMUM_CAPACITY = 1 << 30; static final float DEFAULT_LOAD_FACTOR = 0.75f; 三個常量中可以看出，默認的容器大小是16，最大長度是2的30次方，load factor默認是0.75，擴充的臨界值是16*0.75=12，
如果put操作檢測出hashmap的容量不足，就把數組的大小擴展為2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知hashmap中元素的個數，那麼預設元個數能夠有效的提高hashmap的性能。
實戰總結
所以如果我們想初始化一個容量大小為13的容量，合理的方式是什麼呢？
1.Map<String, String> map1 = new HashMap<>(13);
2.Map<String, String> map2 = new HashMap<>(13, 1);
3.Map<String, String> map3 = Maps.newHashMapWithExpectedSize(13);
以上是三種初始化方式
第一種
直接根據構造方法初始化，那麼map會初始化一個容量大小為16的map，在超過16*0.75即12的時候發生擴容，這顯然不是我們想看到的。
第二種
在構造容量為13的基礎上，將負載因子的值設為1，那麼map將會在超過16個元素後開發擴容，可以滿足我們的預期效果，但這種情況一旦發生擴容，隨著元素的增多，碰撞的機率就會升高，鍊表就會很長，這樣就大大的降低了性能。
第三種
使用guava的方式初始化一個map，根據源碼發現guava已經幫我算好了，真正需要擴容的臨界點，
可以滿足我們的期望，同時也不需要修改負載因子的值，所以無特殊情況下，建議使用此方式。
LinkedHashMap
其底層實現基本與hashmap一致，但是linkedHashMap多維護了一張雙向的鍊表
LinkedHashMap成員變量
增加accessOrder屬性，默認為false，當為false時，按插入順序排序，當為true時，
按LRU+插入順序排序
LRU：最近最少使用算法
Entry
其保存的Entry對象增加了兩個屬性，before和after
存數據
LinkedHashMap沒有重寫put方法，而是重寫了addEntry()方法，把新的Entry也加到header
鍊表結構裡面去
取數據
1、先調用hashmap的getEntry()方法獲取Entry
當accessOrder為true時，把最近使用的當前Entry移到header的before位置，而LinkedHashIterator遍歷的方式是從header.after開始遍歷，先得到最近使用的Entry
最近使用：accessOrder為true時，get(Object key)方法會導致Entry最近使用put(K key, V value)/putForNullKey(value)只有是覆蓋操作時會導致Entry最近使用。它們都會觸發recordAccess方法從而導致Entry最近使用
刪除
LinkedHashMap沒有重寫remove(Object key)方法，重寫了被remove調用的recordRemoval方法，刪除了雙向鍊表中的before和after。
HahsMap remove(Object key)把數據從橫向數組 * 豎向next鍊表裡面移除之後（就已經完成工作了，所以HashMap裡面recordRemoval是空的實現調用了此方法
LinkedHashMap的遍歷
總結
1、什麼是LRU+插入順序？
put(K key, V value)/putForNullKey(value)只有覆蓋操作時會導致Entry最近使用，即為插入順序；accessOrder為true時，get(Object key)方法會導致Entry最近使用，即為LRU
2、LinkedHashMap和HashMap的區別
LinkedHashMap繼承HashMap，結構2裡數據結構的變化交給HashMap就行了。結構1裡數據結構的變化就由LinkedHashMap裡重寫的方法去實現。簡言之：LinkedHashMap比HashMap多維護了一個鍊表。