Hashmap
JDK1.7中
使用一個Entry數(shù)組來存儲數(shù)據(jù)峭梳，用key的hashcode取模來決定key會被放到數(shù)組里的位置铡羡，如果hashcode相同拭嫁，或者hashcode取模后的結果相同，那么這些key會被定位到Entry數(shù)組的同一個格子里浮入，這些key會形成一個鏈表龙优；
在hash函數(shù)特別差的情況下，比如說所有key的hashcode都相同事秀，這個鏈表可能會很長彤断，那么put/get操作都可能需要遍歷這個鏈表，也就是最差情況下時間復雜度為O（n）易迹。
JDK1.8中
使用一個Node數(shù)組來存儲數(shù)據(jù)宰衙，但是這個Node可能是鏈表結構，也可能是紅黑樹結構睹欲；如果插入的元素key的hashcode值相同供炼，那么這些key也會被定位到Node數(shù)組的同一個格子里，如果不超過8個使用鏈表存儲窘疮，超過8個袋哼，會調(diào)用treeifyBin函數(shù)，將鏈表轉換為紅黑樹闸衫。那么即使所有key的hashcode完全相同涛贯，由于紅黑樹的特點，查找某個特定元素楚堤，也只需要O（logn）的開銷疫蔓。
紅黑樹：
每個節(jié)點不是紅的就是黑的；
根節(jié)點是黑的身冬；
葉節(jié)點都是黑色衅胀，葉子節(jié)點指的是為空的節(jié)點；
如果一個節(jié)點是紅色的酥筝，那么子節(jié)點必須為黑色滚躯；
從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。
ConcurrentHashMap
JDK1.7中
使用segment+hashentry來實現(xiàn)嘿歌。ConcurrentHashMap在初始化時掸掏，計算出segement數(shù)組的大小ssize和每個segment中HashEntry數(shù)組的大小cap，并初始化segement數(shù)組的第一個元素宙帝，其中ssize大小為2的冪次方丧凤，默認為16，cap大小也是2的冪次方步脓，最小值為2愿待。segement在實現(xiàn)上繼承了ReetrantLock浩螺，這樣就自帶了鎖的功能。
put實現(xiàn)：當執(zhí)行put方法插入數(shù)據(jù)的時候仍侥，先通過hash值在segment中找到對應的位置要出，然后如果相應位置的segment還未初始化，則通過CAS進行賦值农渊，接著執(zhí)行segment對象的put方法通過加鎖機制插入數(shù)據(jù)患蹂。
size實現(xiàn)：因為concurrenthashmap是可以并發(fā)插入數(shù)據(jù)的，所以準確計算元素時有一定的難度砸紊，所以是先采用不加鎖的方式传于，連續(xù)計算元素的個數(shù)，最多計算3次批糟，如果前后兩次計算結果相同格了，那么說明元素個數(shù)是準確的；如果前后兩次計算結果都不相同徽鼎，則給每個segment加鎖盛末，再計算一次元素的個數(shù)。
JDK1.8中
放棄了segment的設計否淤，取而代之的是Node+CAS+Synchronized來保證并發(fā)安全悄但。只有在執(zhí)行第一次put方法時，才會調(diào)用initTable（）初始化Node數(shù)組石抡。
put實現(xiàn)：
如果Node還未初始化檐嚣，那么通過CAS插入相應的數(shù)據(jù)；
如果Node不為空啰扛，且當前該節(jié)點不處于移動狀態(tài)嚎京，那么對該節(jié)點加synchronized鎖，如果該節(jié)點hash不小于0隐解，則遍歷鏈表更新節(jié)點或者插入新節(jié)點鞍帝；
如果該節(jié)點是TreeBin類型的節(jié)點，說明是紅黑樹結構煞茫，則通過putTreeVal方法往紅黑樹中插入節(jié)點帕涌；
如果binCount不為0，說明put操作對數(shù)據(jù)產(chǎn)生了影響续徽，如果當前鏈表的個數(shù)達到8個蚓曼，則通過treeifyBin方法轉化為紅黑樹，如果oldVal不為空钦扭，說明是一次更新操作纫版，沒有對元素個數(shù)產(chǎn)生影響，則直接返回舊值客情；
如果插入的是一個新節(jié)點其弊，則執(zhí)行addCount()方法嘗試更新元素個數(shù)baseCount会涎；
size實現(xiàn)：1.8中使用一個volatile類型的變量baseCount記錄元素的個數(shù)，當插入新數(shù)據(jù)或則刪除數(shù)據(jù)時瑞凑，會通過addCount()方法更新baseCount。因為元素個數(shù)保存baseCount中概页，部分元素的變化個數(shù)保存在CounterCell數(shù)組中籽御，通過累加baseCount和CounterCell數(shù)組中的數(shù)量，即可得到元素的總個數(shù)惰匙。
PS.兩者在1.8之前都是頭插技掏，1.8之后都是尾插。
