jdk1.7中的底層實作程序（底層基于陣列+鏈表）
在我們new HashMap()時，底層創建了默認長度為16的一維陣列Entry[ ] table，當我們呼叫map.put(key1,value1)方法向HashMap里添加資料的時候：
首先，呼叫key1所在類的hashCode()計算key1的哈希值，通過key1的hash值與陣列的最大索引進行位運算以后，得到了在 Entry陣列中的存放位置：
如果此位置上的資料為空，此時的key1-value1添加成功，
如果此位置上的資料不為空（意味著此位置已經存在一個或多個資料），比較key1和已經存在的一個或多個資料的哈希值：
如果key1的哈希值與已經存在的資料的哈希值都不相同，此時key1-value1添加成功，
如果key1的哈希值與已經存在的資料的某一個資料的哈希值相同，繼續比較：呼叫key1所在類的equals()方法：
如果equals()回傳false，此時key1-value1添加成功；
如果equals()回傳true，使用value1替換value2，
需要注意的是，若原來位置已有資料，則此時key1-value1和原來的資料以鏈表的方式存盤，
在不斷的添加程序中，會涉及到擴容問題，當陣列容量大于陣列現有長度乘以加載因子（如16*0.75，默認的加載因子為0.75）的時候，就會進行陣列擴容，以減少哈希沖突（哈希沖突是指哈希函式算出來的地址被別的元素占用了），提高查詢效率，默認的擴容方式，擴容為原來容量的2倍，并將原有的資料復制過來，
jdk1.8的底層實作程序（底層基于陣列+鏈表+紅黑樹）
jdk1.8與jdk1.7中底層的創建程序相似，但有不同，首先，new HashMap()底層沒有創建出一個長度為16的陣列，在呼叫put()方法時，判斷陣列是否存在，如果不存在創建長度為16的Node[ ]陣列，接下來的程序與jdk1.7相似，最后，當某一個索引位置上的元素以鏈表形式存在的資料個數>8且當前陣列的長度>64時，此時此索引位置上的所有資料改為使用紅黑樹存盤，
在jdk1.7中，即使在“陣列容量大于陣列現有長度乘以加載因子”時擴容，也不可避免地會有哈希沖突存在，因此，在jdk1.8中引入紅黑樹是為了進一步減少哈希沖突，提高查詢效率，
紅黑樹是一種自平衡的二叉查找樹，是一種資料結構，典型的用途是實作關聯陣列，根節點必須是黑色，其他每個節點要么是紅色，要么是黑色，
結論：HashMap鍵是不能重復的，去除重復的條件是依賴鍵的hashCode方法和equals方法，如果鍵是自己的物件型別，必須要重寫hashCode方法和equals方法，否則，不能去除重復的鍵，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/1014.html
標籤：面向對象
下一篇：Mybatis的sql映射