一、什么是Java HashMap

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

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

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

1. 哈希值的計算方法

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

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

index = hashCode % array.length

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

2. 解決哈希沖突的方法

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

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

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

3. 數(shù)組擴容

數(shù)組擴容是HashMap內部的一個重要操作，當調用put()方法時，若當前的元素數(shù)量已經(jīng)達到了擴容閾值，則需要進行數(shù)組擴容操作。其擴容機制如下：

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

4. 加載因子

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

三、Java HashMap的常用方法

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

• put(Object key, Object value)

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

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

• get(Object key)

返回與指定鍵相關聯(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中與指定鍵相關聯(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中鍵值對的數(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中所有鍵值對。

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ù)結構，會產生多線程訪問帶來的并發(fā)問題，因此在多線程環(huán)境下需要特別注意HashMap的線程安全性。

• HashMap的線程安全問題

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

（1）覆蓋和丟失：如果多個線程同時對同一個位置進行寫入操作，最終只有一個線程的結果能夠生效，而其他的操作將被覆蓋或丟失。

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

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

• HashMap的線程安全解決方案

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

（1）使用ConcurrentHashMap

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

（2）使用Collections.synchronizedMap()

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

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

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

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

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

• HashMap的并發(fā)測試

為了驗證HashMap的線程安全問題，可以編寫并發(fā)測試程序來模擬多線程訪問HashMap時可能出現(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個線程并發(fā)往HashMap中添加鍵值對，然后又創(chuàng)建了1000個線程并發(fā)讀取HashMap中的鍵值對。由于HashMap是非線程安全的數(shù)據(jù)結構，可能會產生數(shù)據(jù)丟失、讀取過期數(shù)據(jù)等問題，因此，執(zhí)行上述代碼，有可能會輸出null或錯誤的結果。

五、Java HashMap使用注意事項

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

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

• 值可以為null在HashMap中，值可以為null，這意味著一個鍵可以映射到空值。但需要注意的是，如果多個鍵映射到null，則它們在HashMap中實際上是相等的，因為它們都會被映射到同一個位置上。

• 迭代器操作時需要注意

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

• 初始化容量和加載因子的設置

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

• 避免哈希沖突

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

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

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

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

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集合框架中實現(xiàn)了Map接口的有序哈希表，它具有HashMap的所有特性，并且支持按照插入順序或者訪問順序遍歷鍵值對。在使用LinkedHashMap時，可以通過構造函數(shù)來指定其遍歷順序，并且可以通過覆蓋removeEldestEntry()方法來實現(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());
}

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

以上就是Java HashMap詳解及實現(xiàn)原理的詳細內容，更多關于Java HashMap的資料請關注腳本之家其它相關文章！

最新評論