HashMap底層實現原理

JDK7中底層實現原理

HashMap map = new HashMap();

在實例化以後，底層創建了長度為16的一維數組Entry[] table

…..已經執行過put操作…..

map.put(key1 , value1);

調用key1所在類的hashCode()，計算key1哈希值，此哈希值經過某種演算法計算後，得到在Entry數組中的存放位置

如果此位置上為空，此時的key1-value1添加成功（存放的是entry，而entry裡面有key和value）
如果此位置上不為空（此位置上存在一個或多個數據（以鏈表形式存在）），比較當前key1和已經存在的數據的哈希值
- 如果key1的哈希值與已經存在的數據的哈希值都不相同，此時key1-value1添加成功
- 如果key1的哈希值與已經存在的某一個數據的哈希值都相同，調用key1所在類的equals()方法，進行比較
  - 如果equals()方法返回false，此時key1-value添加成功
  - 如果equals()方法返回true，使用value1替換相同的key的value值（修改的功能）

大致過程與HashSet類似
（具體的圖解可跳轉到如下網址）
//www.cnblogs.com/CrabDumplings/p/13390443.html

注意：

哈希值不同的添加成功情況和equals()返回false添加成功的兩種情況下：

此時key1-value1和原來的數據以鏈表的方式存儲

在不斷的添加過程中，會涉及擴容問題，當超出臨界值且要存放的位置非空時，需要擴容

默認的擴容方式：擴容到原來容量的2倍，並將數據複製過來

相較於jdk7，在底層實現方面的不同如下

HashMap map = new HashMap();

map.put(key1 , value1);

首次調用put方法時，底層創建長度為16的數組
jdk7底層結構：數組 + 鏈表

jdk8底層結構：數組 + 鏈表 + 紅黑樹

當數組的某一個索引位置上的元素以鏈表形式存在的數據個數大於8且當前數組的長度超過64，此時此索引位置上的所有數據改為使用紅黑樹存儲