一、實作原理
以JDK1.7源碼為例進行分析
(一)Hashing的概念
将字元串轉換成固定長度(一般是更短的長度)的數值或索引值的方法,也稱為散列法或哈希法。常用于資料庫中建索引,或是用于各種加解密算法中。
完成轉換功能的函數一般稱為哈希函數,哈希函數設計的好壞将直接影響到哈希表的優劣。
(二)哈希表
可高效進行增加、删除、查找等操作的資料結構,不考慮哈希沖突的情況下,僅需要一次定位即可完成,時間複雜度為O(1)。
哈希表的主幹是數組,在數組中根據下标查找某個元素,一次定位即可達到,正是利用這種特性,達到高效的操作。
(三)哈希沖突
兩個不同元素,通過hashing後,有極小的機率得到相同的數值(實際的存儲位址),對這個存儲位址進行插入操作時,發現已經被其他元素占用,這就是所謂的哈希沖突,也叫哈希碰撞。
好的哈希函數會盡量保證計算簡單和散列位址分布均勻,但也不能保證得到的存儲位址絕對沒有沖突。
HashMap解決哈希沖突采用的是鍊位址法,即數組+連結清單的方式。
(四)原理分析
1、HashMap實際上是一個“連結清單散列”的資料結構,即數組和連結清單的結合體。數組是主體,連結清單是為了解決哈希沖突。如果定位到的數組位置不含連結清單(Entry的指針指向null),此時操作僅需一次尋址即可;如果定位到的位置包含連結清單,則周遊連結清單,通過key對象的equals方法逐一對比查找,此時時間複雜度為O(n)。是以HashMap中出現連結清單越少,其性能越好。
結構圖如下:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHL9cmeOh3ZE9EeBRVT3V1MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL2cDO4QDNwATM4ETMwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
Entry代碼片斷及解析:
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;//final
V value;
Entry<K,V> next;//指針(也可以叫引用)
int hash;//key對應的hash值
Entry(int h, K k, V v, Entry<K,V> n) {
……//略,構造方法體
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
}
上面equals方法中, if 判斷k1 == k2、v1 == v2這2處,旨在說明“null==null”傳回true,在此進行說明,并且我們在平時編碼中也應該注意這一點。
(五)幾個重要屬性(字段)
1、static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
預設初始容量,必須是2的次方
2、static final float DEFAULT_LOAD_FACTOR = 0.75f;
預設裝載因子,大小為0.75。
3、static final Entry<?,?>[] EMPTY_TABLE = {};
預設初始化的空表Entry
4、transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
HashMap實際存儲資料的表,長度必須總是2的幂,預設為空表
5、transient int size;
實際的鍵值對數量
6、int threshold;
擴容臨界值:下一個要調整大小的值(總容量*裝載因子),當鍵值對數量size達到此值時(size >= threshold),對容量進行擴容操作(resize(2 * table.length))
特此說明:
上述對“臨界值”的描述看似正确,而實際上并非如此。假設目前容量為8,裝載因子0.75,則threshold=6,當size為6時會對HashMap進行擴容嗎?經實驗證明,不一定會。
檢視源碼,在put操作時擴容的條件為“(size >= threshold) && (null != table[bucketIndex])”,也就是說還需要同時滿足後面條件,那麼bucketIndex又是什麼呢?直譯為“桶的下标”,即下一個存放Entry的桶的位置,這個位置的擷取來自方法“indexFor”,如下:
static int indexFor(int h, int length) {//hash值,table的總容量
return h & (length-1);
}
length-1的二進值低位都是1,h & (length-1)的與運算,實質就是h% (length-1),隻要hash不相等,理想情況下,需要容量被全部占用時才會擴容。
簡而言之,僅當size >= threshold且發生Hash值%(length-1)沖突(或修改已存在的值或)時,才會進行擴容。
關于擴容的驗證,請參見文章:https://blog.csdn.net/u010188178/article/details/86527792
7、final float loadFactor;
裝載因子,當使用容量達到總容量*裝載因子容量時,可能會對集合進行擴容操作;如果執行個體化時不指定裝載因子的大小,其初始化為預設大小0.75。
(六)構造方法
1、直接構造(指定容量+裝載因子)
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;//裝載因子指派
threshold = initialCapacity;//擴容臨界值指派
init();
}
此處threshold指派為傳入的初始值,比如傳入5,初始化時,threshold=5,而在第一次put操作時,通過5計算HashMap的初始容量應該為8(2的冥且>=5),再通過裝載因子(預設0.75)計算出擴容臨界值threshold=6。
并且執行個體化時并沒有為數組table配置設定記憶體空間,而是在put第一個元素時才建構table數組。
2、直接構造(指定容量)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
3、無參構造
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
4、通過實作Map接口的對象構造
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
二、JDK1.8的主要改動
1、資料結構
JDK1.7使用數組+連結清單的資料結構,而1.8使用數組+連結清單+紅黑樹。
如果插入key的hashcode相同,使用連結清單方式解決沖突,當連結清單長度達到8個(預設設定的門檻值)時,調用treeifyBin函數,将連結清單轉換為紅黑樹。紅黑樹的時間複雜度為O(log n),即put/get最壞時間複雜度為O(log n)。
2、資料存儲機制
發生hash沖突時,JDK1.7采用鍊位址法+頭插法,而1.8采用鍊位址法+尾插法+紅黑樹。
頭插入法插入效率較高,但容易出現逆序且環形連結清單死循環問題,尾插法可避免此問題。
三、HashMap使用誤區
1、如果使用的HashMap容量可能會很大,執行個體化時設定初始容量,比如new HashMap(2048)。
這樣建議的理由無非就是說,當容器持續增長時,可能會導緻其頻繁擴容,影響性能。而實際生産中是否有這樣的必要呢?先做個實驗。
JDK1.7環境下,插入元素數量16777216,其對應預設臨界值為12582912
(1)設定初始值的情況
public static void testHashMap(){
//插入元素數量16777216,其對應預設臨界值為12582912
int size = 16777216;
long start = System.currentTimeMillis();
Map<Integer, Integer> map2 = new HashMap<>(12582912);
for(int i=0; i<size; i++){
map2.put(i, i);
}
long end = System.currentTimeMillis();
System.out.println("設定初始值耗時:"+(end-start));
}
以上情況需要擴容一次,運作時長:18270(多次運作,時長18000ms左右)
(2)不設定初始值的情況
public static void testHashMap1(){
//插入元素數量16777216,其對應預設臨界值為12582912
int size = 16777216;
long start = System.currentTimeMillis();
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<size; i++){
map.put(i, i);
}
long end = System.currentTimeMillis();
System.out.println("不設定初始值耗時:"+(end-start));
}
以上情況需要擴容很多次,運作時長:14057(多次運作,時長在此值左右)
現在将JDK環境修改為1.8,再次測試,2次運作結果分别如下:
設定初始值耗時:20866
不設定初始值耗時:17707
是以:
在JDK1.7、1.8環境下,對較大容量HashMap設定初始值(實質上為擴容臨界值),并不會對實際效率有所提高。
2、我在檢視同僚的源碼時經常看到new HashMap(4),new HashMap(6)之類的寫法。
我肯定他們的初衷是在知道容器存放總量的情況下,設定初始容量以減少記憶體消耗。但這裡需要注意的是:
入參并不是容器的初始容量,而是擴容臨界值。在執行個體化HashMap時,并不會初始化其容量,此時預設容量為0;在執行第一次put操作時,預設裝載因子為0.75的情況下,其初始容量由傳入的參數除以0.75,得到的值為N,再計算2的冥得到Y,保證Y>=N且Y最接近N,此時的Y才是HashMap的初始容量;用Y乘以0.75得到真實擴容臨界值。
四、細枝末節
1、HashMap可以接受null鍵值和值,而Hashtable則不能
2、HashMap是非synchronized
3、String、Integer這樣的包裝類适合作為key。它們由final修飾,具有不可變性;内部重寫了equals()、hashCode()方法 ,具有計算準确性,有效減少了發生Hash碰撞的機率。