jdk1.7中的底層實(shí)現(xiàn)過(guò)程（底層基于數(shù)組+鏈表）
在我們new HashMap()時(shí)，底層創(chuàng)建了默認(rèn)長(zhǎng)度為16的一維數(shù)組Entry[ ] table。當(dāng)我們調(diào)用map.put(key1,value1)方法向HashMap里添加數(shù)據(jù)的時(shí)候：
首先，調(diào)用key1所在類(lèi)的hashCode()計(jì)算key1的哈希值，通過(guò)key1的hash值與數(shù)組的最大索引進(jìn)行位運(yùn)算以后，得到了在 Entry數(shù)組中的存放位置：
如果此位置上的數(shù)據(jù)為空，此時(shí)的key1-value1添加成功。
如果此位置上的數(shù)據(jù)不為空（意味著此位置已經(jīng)存在一個(gè)或多個(gè)數(shù)據(jù)），比較key1和已經(jīng)存在的一個(gè)或多個(gè)數(shù)據(jù)的哈希值：
如果key1的哈希值與已經(jīng)存在的數(shù)據(jù)的哈希值都不相同，此時(shí)key1-value1添加成功。
如果key1的哈希值與已經(jīng)存在的數(shù)據(jù)的某一個(gè)數(shù)據(jù)的哈希值相同，繼續(xù)比較：調(diào)用key1所在類(lèi)的equals()方法：
如果equals()返回false，此時(shí)key1-value1添加成功；
如果equals()返回true，使用value1替換value2。
需要注意的是，若原來(lái)位置已有數(shù)據(jù)，則此時(shí)key1-value1和原來(lái)的數(shù)據(jù)以鏈表的方式存儲(chǔ)。
在不斷的添加過(guò)程中，會(huì)涉及到擴(kuò)容問(wèn)題，當(dāng)數(shù)組容量大于數(shù)組現(xiàn)有長(zhǎng)度乘以加載因子（如16*0.75，默認(rèn)的加載因子為0.75）的時(shí)候，就會(huì)進(jìn)行數(shù)組擴(kuò)容，以減少哈希沖突（哈希沖突是指哈希函數(shù)算出來(lái)的地址被別的元素占用了），提高查詢(xún)效率。默認(rèn)的擴(kuò)容方式，擴(kuò)容為原來(lái)容量的2倍，并將原有的數(shù)據(jù)復(fù)制過(guò)來(lái)。
jdk1.8的底層實(shí)現(xiàn)過(guò)程（底層基于數(shù)組+鏈表+紅黑樹(shù)）
jdk1.8與jdk1.7中底層的創(chuàng)建過(guò)程相似，但有不同，首先，new HashMap()底層沒(méi)有創(chuàng)建出一個(gè)長(zhǎng)度為16的數(shù)組，在調(diào)用put()方法時(shí)，判斷數(shù)組是否存在，如果不存在創(chuàng)建長(zhǎng)度為16的Node[ ]數(shù)組。接下來(lái)的過(guò)程與jdk1.7相似。最后，當(dāng)某一個(gè)索引位置上的元素以鏈表形式存在的數(shù)據(jù)個(gè)數(shù)>8且當(dāng)前數(shù)組的長(zhǎng)度>64時(shí)，此時(shí)此索引位置上的所有數(shù)據(jù)改為使用紅黑樹(shù)存儲(chǔ)。
在jdk1.7中，即使在“數(shù)組容量大于數(shù)組現(xiàn)有長(zhǎng)度乘以加載因子”時(shí)擴(kuò)容，也不可避免地會(huì)有哈希沖突存在，因此，在jdk1.8中引入紅黑樹(shù)是為了進(jìn)一步減少哈希沖突，提高查詢(xún)效率。
紅黑樹(shù)是一種自平衡的二叉查找樹(shù)，是一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組。根節(jié)點(diǎn)必須是黑色，其他每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。
結(jié)論：HashMap鍵是不能重復(fù)的，去除重復(fù)的條件是依賴(lài)鍵的hashCode方法和equals方法，如果鍵是自己的對(duì)象類(lèi)型，必須要重寫(xiě)hashCode方法和equals方法，否則，不能去除重復(fù)的鍵。
