一、什么是Java HashMap

Java HashMap是Java集合框架中最常用的實(shí)現(xiàn)Map接口的數(shù)據(jù)結(jié)構(gòu)，它使用哈希表實(shí)現(xiàn)，允許null作為鍵和值，可以存儲(chǔ)不同類型的鍵值對(duì)。HashMap提供了高效的存取方法，并且是非線程安全的。在Java中，HashMap被廣泛應(yīng)用于各種場景，如緩存、數(shù)據(jù)庫連接池、路由器等。

二、Java HashMap的實(shí)現(xiàn)原理

HashMap使用哈希表(Hash Table)實(shí)現(xiàn)，哈希表是一種以鍵值對(duì)(key-value)的形式進(jìn)行存儲(chǔ)和快速查找的數(shù)據(jù)結(jié)構(gòu)。HashMap內(nèi)部維護(hù)了一個(gè)數(shù)組，每個(gè)數(shù)組元素都是一個(gè)鏈表節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含一個(gè)鍵值對(duì)，以及指向下一個(gè)節(jié)點(diǎn)的指針。當(dāng)需要查找或插入一個(gè)元素時(shí)，HashMap首先計(jì)算該元素的哈希值，根據(jù)哈希值確定它在數(shù)組中的位置，然后在對(duì)應(yīng)的鏈表上進(jìn)行查找或插入操作。

1. 哈希值的計(jì)算方法

首先，HashMap會(huì)調(diào)用鍵對(duì)象的hashCode()方法，獲取到該對(duì)象的哈希碼。哈希碼是一個(gè)int類型的整數(shù)，用于表示該對(duì)象的標(biāo)識(shí)號(hào)。但是，由于哈希碼的范圍很大，因此通常需要對(duì)它進(jìn)行下一步處理，轉(zhuǎn)換成一個(gè)比較小的數(shù)值，以便存儲(chǔ)到數(shù)組中。這樣，就用到了哈希函數(shù)(Hash Function)，哈希函數(shù)用于將大范圍的哈希碼映射到較小的數(shù)組索引范圍內(nèi)。

HashMap的哈希函數(shù)有多種實(shí)現(xiàn)方式，其中一種常用的方法是將哈希碼與數(shù)組長度取模后的余數(shù)作為數(shù)組下標(biāo)，即：

index = hashCode % array.length

其中，array為HashMap內(nèi)部維護(hù)的數(shù)組，hashCode為鍵的哈希碼，index為鍵在數(shù)組中的下標(biāo)。這個(gè)方法的優(yōu)點(diǎn)是簡單、快速，但缺點(diǎn)也很明顯：當(dāng)哈希碼分布不均衡時(shí)，容易出現(xiàn)哈希沖突(Haah Collision)，即不同的鍵對(duì)象具有相同的哈希碼，導(dǎo)致它們被映射到同一個(gè)數(shù)組位置上，形成一個(gè)鏈表。

2. 解決哈希沖突的方法

為了解決哈希沖突，HashMap使用鏈表法(Chaining)來處理。鏈表法是將哈希沖突的元素以鏈表的形式組織起來，所有哈希值相同的元素作為同一個(gè)鏈表的節(jié)點(diǎn)，并按照插入順序排列。

鏈表法的實(shí)現(xiàn)非常簡單，每個(gè)數(shù)組元素都是一個(gè)鏈表節(jié)點(diǎn)，如果該元素已經(jīng)存在鏈表中，則將新元素插入到鏈表的末尾，否則創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將其插入到鏈表頭部。這種方式可以在O(1)的時(shí)間內(nèi)進(jìn)行查找、插入和刪除等操作。

當(dāng)鏈表長度變長時(shí)，查找、插入和刪除操作的效率會(huì)降低。為了解決這個(gè)效率問題，JDK1.8引入了紅黑樹(Red-Black Tree)的使用場景，當(dāng)鏈表長度超過閾值(默認(rèn)為8)時(shí)，將鏈表轉(zhuǎn)換為紅黑樹，以提高效率。

3. 數(shù)組擴(kuò)容

數(shù)組擴(kuò)容是HashMap內(nèi)部的一個(gè)重要操作，當(dāng)調(diào)用put()方法時(shí)，若當(dāng)前的元素?cái)?shù)量已經(jīng)達(dá)到了擴(kuò)容閾值，則需要進(jìn)行數(shù)組擴(kuò)容操作。其擴(kuò)容機(jī)制如下：

首先，創(chuàng)建一個(gè)新的空數(shù)組，大小為原數(shù)組的兩倍；然后遍歷原數(shù)組中的每個(gè)元素，重新計(jì)算它們在新數(shù)組中的位置，然后將這些元素放到新數(shù)組中相應(yīng)的位置上；最后，再將新數(shù)組設(shè)置為HashMap內(nèi)部的數(shù)組。因此，在擴(kuò)容過程中，需要重新計(jì)算哈希值，重新映射數(shù)組下標(biāo)，并將元素復(fù)制到新數(shù)組，這個(gè)過程是很費(fèi)時(shí)間和空間的。因此，為了減少擴(kuò)容的次數(shù)，一般情況下，將HashMap的初始化容量設(shè)置為能夠存放預(yù)計(jì)元素?cái)?shù)量的1.5倍。

4. 加載因子

HashMap內(nèi)部還維護(hù)著一個(gè)加載因子(load factor)屬性，默認(rèn)為0.75。它表示當(dāng)元素?cái)?shù)量與數(shù)組長度的比值超過了這個(gè)閾值時(shí)，就會(huì)進(jìn)行擴(kuò)容操作，以便保持哈希表的性能。一般來說，較小的負(fù)載因子會(huì)增加哈希表的存儲(chǔ)空間，但會(huì)減少哈希沖突的發(fā)生機(jī)率，提高查詢效率；而較大的負(fù)載因子則會(huì)減少存儲(chǔ)空間，但會(huì)增加哈希沖突的概率，降低查詢效率。因此，在決定負(fù)載因子的大小時(shí)，需要根據(jù)應(yīng)用場景、數(shù)據(jù)量和時(shí)間復(fù)雜度等因素進(jìn)行合理的取舍。

三、Java HashMap的常用方法

HashMap提供了一些常見的操作方法，如put()、get()、remove()、size()等。下面對(duì)這些方法進(jìn)行簡要介紹：

• put(Object key, Object value)

將指定的鍵值對(duì)插入到HashMap中，如果該鍵已經(jīng)存在，則會(huì)用新的值替換已有的值。插入成功返回null，否則返回被替換的舊值。

HashMap<String, Integer> map = new HashMap<>();
map.put("tom", 90); // 插入鍵值對(duì)
map.put("jerry", 85);
int oldScore = map.put("tom", 95); // 替換鍵值對(duì)
System.out.println(map.get("tom")); // 輸出95

• get(Object key)

返回與指定鍵相關(guān)聯(lián)的值，如果該鍵不存在，則返回null。

HashMap<String, Integer> map = new HashMap<>();
map.put("tom", 90);
map.put("jerry", 85);
int score = map.get("tom");
System.out.println(score); // 輸出90

• remove(Object key)

刪除HashMap中與指定鍵相關(guān)聯(lián)的值，并返回被刪除的值。

HashMap<String, Integer> map = new HashMap<>();
map.put("tom", 90);
map.put("jerry", 85);
int score = map.remove("tom");
System.out.println(score); // 輸出90

• size()

返回HashMap中鍵值對(duì)的數(shù)量。

HashMap<String, Integer> map = new HashMap<>();
map.put("tom", 90);
map.put("jerry", 85);
int size = map.size();
System.out.println(size); // 輸出2

• clear()

刪除HashMap中所有鍵值對(duì)。

HashMap<String, Integer> map = new HashMap<>();
map.put("tom", 90);
map.put("jerry", 85);
map.clear();
System.out.println(map.size()); // 輸出0

四、Java HashMap的線程安全性

在多線程環(huán)境下，由于HashMap是非線程安全的數(shù)據(jù)結(jié)構(gòu)，會(huì)產(chǎn)生多線程訪問帶來的并發(fā)問題，因此在多線程環(huán)境下需要特別注意HashMap的線程安全性。

• HashMap的線程安全問題

HashMap是一種非線程安全（Not Thread-Safe）的數(shù)據(jù)結(jié)構(gòu)，因此，在多線程環(huán)境下使用它可能會(huì)導(dǎo)致多種并發(fā)問題，主要包括以下幾個(gè)方面：

（1）覆蓋和丟失：如果多個(gè)線程同時(shí)對(duì)同一個(gè)位置進(jìn)行寫入操作，最終只有一個(gè)線程的結(jié)果能夠生效，而其他的操作將被覆蓋或丟失。

（2）讀取過期數(shù)據(jù)：在HashMap中，讀取操作可以在讀取和修改操作之間進(jìn)行，也就是說，多個(gè)線程可以同時(shí)讀取同一個(gè)數(shù)據(jù)。然而，如果一個(gè)線程在讀取一個(gè)鍵的值時(shí)，另一個(gè)線程正在修改它，那么讀操作可能會(huì)讀取到過期的數(shù)據(jù)，從而導(dǎo)致程序出現(xiàn)問題。

（3）死鎖和饑餓：由于HashMap使用數(shù)組和鏈表（或紅黑樹）的結(jié)合實(shí)現(xiàn)，因此在多線程環(huán)境下，可能會(huì)出現(xiàn)死鎖和饑餓的情況，降低程序性能。

• HashMap的線程安全解決方案

為了解決HashMap的線程安全問題，Java提供了多種解決方案，以下是幾種常用的方式：

（1）使用ConcurrentHashMap

ConcurrentHashMap是Java 5中提供的一種線程安全的Map實(shí)現(xiàn)，它采用了鎖分段技術(shù)，在每個(gè)段（Segment）中都使用了一個(gè)獨(dú)立的鎖，以避免多個(gè)線程訪問同一段的問題，從而保證了并發(fā)性能和線程安全性。ConcurrentHashMap實(shí)現(xiàn)了Java中的ConcurrentMap接口，并提供了多個(gè)線程安全的方法，如putIfAbsent、remove、replace等。如果需要在多線程環(huán)境下使用Map，推薦使用ConcurrentHashMap。

（2）使用Collections.synchronizedMap()

Collections.synchronizedMap()是Java提供的一種將非線程安全的Map對(duì)象轉(zhuǎn)換為線程安全的Map對(duì)象的方法。它實(shí)際上是對(duì)Map對(duì)象的每個(gè)方法都添加了synchronized關(guān)鍵字，從而保證了并發(fā)性能和線程安全性。使用Collections.synchronizedMap()創(chuàng)建線程安全的Map對(duì)象的代碼如下：

Map<K, V> map = Collections.synchronizedMap(new HashMap<>());

這種方式適合于訪問頻率較低或者對(duì)線程安全性要求不高的場景。

（3）使用線程安全的并發(fā)集合

除了ConcurrentHashMap和synchronizedMap()外，Java還提供了其他多種線程安全的集合實(shí)現(xiàn)和映射實(shí)現(xiàn)，如CopyOnWriteArrayList、ConcurrentSkipListMap等。這些集合和映射實(shí)現(xiàn)都具有優(yōu)秀的性能和線程安全性，可以根據(jù)實(shí)際需求選擇使用。

• HashMap的并發(fā)測試

為了驗(yàn)證HashMap的線程安全問題，可以編寫并發(fā)測試程序來模擬多線程訪問HashMap時(shí)可能出現(xiàn)的問題。以下是一段示例代碼：

Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < 1000; i++) {
    final int index = i;
    new Thread(() -> map.put("key-" + index, index)).start();
}
for (int i = 0; i < 1000; i++) {
    final int index = i;
    new Thread(() -> System.out.println(map.get("key-" + index))).start();
}

該程序首先創(chuàng)建了1000個(gè)線程并發(fā)往HashMap中添加鍵值對(duì)，然后又創(chuàng)建了1000個(gè)線程并發(fā)讀取HashMap中的鍵值對(duì)。由于HashMap是非線程安全的數(shù)據(jù)結(jié)構(gòu)，可能會(huì)產(chǎn)生數(shù)據(jù)丟失、讀取過期數(shù)據(jù)等問題，因此，執(zhí)行上述代碼，有可能會(huì)輸出null或錯(cuò)誤的結(jié)果。

五、Java HashMap使用注意事項(xiàng)

• 鍵必須實(shí)現(xiàn)hashCode()方法和equals()方法

在使用HashMap時(shí)，鍵必須實(shí)現(xiàn)hashCode()方法和equals()方法，以便用于哈希表中的查找操作。hashCode()方法用于獲取對(duì)象的哈希碼，equals()方法用于判斷兩個(gè)對(duì)象是否相等。如果鍵沒有實(shí)現(xiàn)這兩個(gè)方法，則會(huì)出現(xiàn)查詢異常和哈希沖突等問題。

• 值可以為null在HashMap中，值可以為null，這意味著一個(gè)鍵可以映射到空值。但需要注意的是，如果多個(gè)鍵映射到null，則它們在HashMap中實(shí)際上是相等的，因?yàn)樗鼈兌紩?huì)被映射到同一個(gè)位置上。

• 迭代器操作時(shí)需要注意

在使用HashMap的迭代器遍歷鍵值對(duì)時(shí)，需要注意當(dāng)在遍歷過程中插入或刪除元素時(shí)，可能會(huì)導(dǎo)致ConcurrentModificationException異常的發(fā)生。這是因?yàn)樵诒闅v過程中，遍歷器會(huì)對(duì)HashMap的修改操作進(jìn)行快照，并在遍歷結(jié)束后進(jìn)行檢查，如果與快照不一致，則拋出異常。為了避免這種情況的發(fā)生，可以使用Iterator接口提供的remove()方法來刪除元素，而不是直接調(diào)用HashMap的remove()方法。

• 初始化容量和加載因子的設(shè)置

在創(chuàng)建HashMap對(duì)象時(shí)，需要根據(jù)實(shí)際業(yè)務(wù)場景合理地設(shè)置初始化容量和加載因子，以便提高HashMap的性能。如果預(yù)計(jì)插入的元素?cái)?shù)量很大，那么初始化容量應(yīng)該足夠大，以減少數(shù)組擴(kuò)容的次數(shù)；同時(shí)，可以將加載因子設(shè)置為較小的值，以提高查詢效率。但是，需要注意不要將初始化容量設(shè)置過大或加載因子設(shè)置過小，否則會(huì)浪費(fèi)內(nèi)存資源或增加哈希沖突的概率，影響性能。

• 避免哈希沖突

哈希沖突是指不同的鍵對(duì)象具有相同的哈希碼，導(dǎo)致它們被映射到同一個(gè)數(shù)組位置上，形成一個(gè)鏈表。當(dāng)鏈表長度變長時(shí)，查詢效率會(huì)降低。為了避免哈希沖突，可以在設(shè)計(jì)鍵對(duì)象時(shí)，盡可能地使其哈希值范圍分布均勻，并且盡可能減少哈希沖突的發(fā)生。例如，在字符串類型的鍵中，可以采用漢明距離等算法來計(jì)算鍵的哈希值，并增加隨機(jī)數(shù)來打亂散列結(jié)果，從而減少哈希沖突的發(fā)生。

• hashCode()方法和equals()方法的重寫

在使用HashMap時(shí)，為了保證其正確性和性能，通常需要重寫鍵對(duì)象的hashCode()方法和equals()方法。hashCode()方法用于計(jì)算鍵對(duì)象的哈希碼，而equals()方法用于比較兩個(gè)對(duì)象是否相等。如果兩個(gè)鍵對(duì)象的哈希碼相同，但equals()方法返回false，則會(huì)導(dǎo)致哈希沖突的發(fā)生。因此，在重寫hashCode()方法時(shí)，需要保證對(duì)于相等的對(duì)象其哈希碼相等；而在重寫equals()方法時(shí)，需要保證對(duì)于相等的對(duì)象其equals()方法返回true。

例如，在自定義類型的鍵中，可以將鍵的各個(gè)字段的哈希碼按照不同的權(quán)重組合起來，生成一個(gè)唯一的哈希值。同時(shí)，重寫equals()方法時(shí)需要判斷兩個(gè)對(duì)象的各個(gè)字段是否相等，以確保它們是相等的。

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null || getClass() != obj.getClass())
            return false;
        Person person = (Person) obj;
        return age == person.age && Objects.equals(name, person.name);
    }
}

• LinkedHashMap的使用

LinkedHashMap是Java集合框架中實(shí)現(xiàn)了Map接口的有序哈希表，它具有HashMap的所有特性，并且支持按照插入順序或者訪問順序遍歷鍵值對(duì)。在使用LinkedHashMap時(shí)，可以通過構(gòu)造函數(shù)來指定其遍歷順序，并且可以通過覆蓋removeEldestEntry()方法來實(shí)現(xiàn)緩存淘汰策略。

LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("tom", 90);
map.put("jerry", 85);
map.put("bob", 88);
System.out.println(map.get("tom")); // 輸出90
map.get("jerry");
for (Map.Entry<String, Integer> entry: map.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

在上面這個(gè)例子中，創(chuàng)建了一個(gè)容量為16、負(fù)載因子為0.75、按照訪問順序排序的LinkedHashMap對(duì)象。然后依次插入三個(gè)鍵值對(duì)，其中“tom”對(duì)應(yīng)的值為90。接著，訪問“tom”鍵，并通過遍歷LinkedHashMap來輸出所有的鍵值對(duì)，可以看到“tom”的位置已經(jīng)發(fā)生

以上就是Java HashMap詳解及實(shí)現(xiàn)原理的詳細(xì)內(nèi)容，更多關(guān)于Java HashMap的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論