HashMap
HashMap是基于哈希表的Map接口的非同步實現(xiàn)。實現(xiàn)HashMap對數(shù)據(jù)的操作，允許有一個null鍵，多個null值。
HashMap底層就是一個數(shù)組結(jié)構(gòu)，數(shù)組中的每一項又是一個鏈表。數(shù)組+鏈表結(jié)構(gòu)，新建一個HashMap的時候，就會初始化一個數(shù)組。Entry就是數(shù)組中的元素，每個Entry其實就是一個key-value的鍵值對，它持有一個指向下一個元素的引用，這就構(gòu)成了鏈表，HashMap底層將key-value當(dāng)成一個整體來處理，這個整體就是一個Entry對象。HashMap底層采用一個Entry【】數(shù)組來保存所有的key-value鍵值對，當(dāng)需要存儲一個Entry對象時，會根據(jù)hash算法來決定在其數(shù)組中的位置，在根據(jù)equals方法決定其在該數(shù)組位置上的鏈表中的存儲位置；當(dāng)需要取出一個Entry對象時，也會根據(jù)hash算法找到其在數(shù)組中的存儲位置， 在根據(jù)equals方法從該位置上的鏈表中取出Entry;
put：（key-value）方法是HashMap中最重要的方法，使用HashMap最主要使用的就是put，get兩個方法。
判斷鍵值對數(shù)組table[i]是否為空或者為null，否則執(zhí)行resize（）進行擴容；
根據(jù)鍵值key計算hash值得到插入的數(shù)組索引 i ,如果table[i] == null ，直接新建節(jié)點添加即可，轉(zhuǎn)入6，如果table[i] 不為空，則轉(zhuǎn)向3；
判斷table[i] 的首個元素是否和key一樣，如果相同（hashCode和equals）直接覆蓋value，否則轉(zhuǎn)向4；
判斷table[i] 是否為treeNode，即table[i]是否為紅黑樹，如果是紅黑樹，則直接插入鍵值對，否則轉(zhuǎn)向5；
遍歷table[i] ,判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換成紅黑樹，進行插入操作，否則進行鏈表插入操作；便利時遇到相同key直接覆蓋value；
插入成功后，判斷實際存在的鍵值對數(shù)量size是否超過了threshold，如果超過，則擴容；
也可參考HashSetput過程：
http://www.itdecent.cn/p/419a448414da
get方法取值過程：
int hash = key.hashCode（）；
int index = hash%Entry[].length;
指定key通過hash函數(shù)得到key的hash值；
調(diào)用內(nèi)部方法getNode（），得到桶號（一般為hash值對桶數(shù)求摸）；
比較桶的內(nèi)部元素是否和key相等，如不相等，則沒有找到，相等，則取出相等記錄的value；
如果得到key所在桶的頭結(jié)點恰好是紅黑樹節(jié)點，就調(diào)用紅黑樹節(jié)點的getTreeNode（）方法，否則就遍歷鏈表節(jié)點。getTreeNode（）方法通過調(diào)用樹形節(jié)點的find（）方法進行查找。由于之前添加時已經(jīng)保證這個樹是有序的，因此查找時基本就是折半查找，效率高；
如果對比節(jié)點的哈希值和要查找的哈希值相等，就會判斷key是否相等，相等就直接返回；不相等就從子樹中遞歸查找；
HashMap中直接地址用hash函數(shù)生成，沖突用比較函數(shù)解決。如果每個桶內(nèi)部只有一個元素，那么查找的時候只有一次比較。當(dāng)許多桶內(nèi)沒有值得時候，許多查詢就會更快
addEntry方法
- 添加新元素前，判斷是否需要對map的數(shù)組進行擴容，如果需要擴容，則擴容多大？
- 對于新增key-value鍵值對，如果可以的hash值相同，則構(gòu)造單向列表；
TreeMap
實現(xiàn)了SortedMap接口，是一個有序的集合，是一個紅黑樹接口，每個key-vlaue作為紅黑樹的節(jié)點，沒有指定順序則是根據(jù)key執(zhí)行自然排序。默認自然排序
- 繼承了AbstractMap類，實現(xiàn)了接口
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
可以自然排序，可以定制排序，Entry root = null 紅黑樹的根節(jié)點；size存放鍵值對的數(shù)量。
- 自然排序：所有的key必須實現(xiàn)Comparable接口，所有的key都是同一類的對象；
-
定制排序：創(chuàng)建TreeMap對象傳入一個Comparator對象，改對象負責(zé)key進行排序，采用定制排序不要去key實現(xiàn)comparable接口。
- 自定義排序時候，需要將Comparator對象傳進集合中當(dāng)作參數(shù)，進而進行排序。Comparator的對象也需要傳進兩個實體類對象，進行兩兩比較。，return 比較的結(jié)果，如果是正數(shù)就是從下到大排序，等于0說明兩個數(shù)的一摸一樣，直接去重，如果是負數(shù)，說明一個數(shù)小，此刻return返回一個負數(shù)，排序的是時候么就是按照倒序排序的。
- 主要方法：
put():
get():根據(jù)不同的排序比較方法定位需要的數(shù)據(jù)，檢索速度時間復(fù)雜度為O(log(n))；
remove():
TreeMap默認是自然排序，沒有查找方法；無需遍歷
- 紅黑樹
是一個更高效檢索二叉樹，每個節(jié)點只能是紅色或者黑色；根節(jié)點永遠是黑色；所有葉子的子節(jié)點都是空節(jié)點，并且都是黑色；每個紅色節(jié)點的兩個子節(jié)點都是黑色，沒有連續(xù)的紅色節(jié)點；從人一個節(jié)點到其子樹中的每個葉子節(jié)點的路徑中所包含相同數(shù)量的黑色節(jié)點。
HashMap和TreeMap比較
（1）HashMap:適用于在Map中插入、刪除和定位元素。 默認亂序
（2）Treemap:適用于按自然順序或自定義順序遍歷鍵（key）。 默認自然排序，如果插入的是基本類型，按照 大小排序。如果是引用類型，則按照插入順序
（3）HashMap通常比TreeMap快一點（樹和哈希表的數(shù)據(jù)結(jié)構(gòu)使然），建議多使用HashMap,在需要排序的Map時候才用TreeMap.**
（4）HashMap 非線程安全 TreeMap 非線程安全
（5）HashMap的結(jié)果是沒有排序的，而TreeMap輸出的結(jié)果是排好序的。
在HashMap中通過get（）來獲取value,通過put（）來插入value,ContainsKey（）則用來檢驗對象是否已經(jīng)存在。可以看出，和ArrayList的操作相比，HashMap除了通過key索引其內(nèi)容之外，別的方面差異并不大。
Treemap的方法是在hashmap的基礎(chǔ)上進行補充的
