Java HashMap指南

1.概述

在本文中,我們將看到如何在Java中使用HashMap ,並且將研究它在內部如何工作。

HashMap非常相似的類是Hashtable 。請參考我們的其他幾篇文章,以了解有關java.util.Hashtable類本身以及HashMapHashtable之間的區別的更多信息。

2.基本用法

首先讓我們看一下HashMap是地圖的含義。映射是鍵-值映射,這意味著每個鍵都被精確映射到一個值,並且我們可以使用該鍵從映射中檢索相應的值。

有人可能會問為什麼不將值簡單地添加到列表中。為什麼我們需要HashMap ?原因很簡單。如果要在列表中查找特定元素,則時間複雜度為O(n) ,如果列表已排序,則使用例如二進制搜索將其變為O(log n)

HashMap的優點是插入和檢索值的時間複雜度平均為O(1) 。我們將在稍後探討如何實現。首先讓我們看一下如何使用HashMap

2.1。設定

讓我們創建一個簡單的類,在整篇文章中都會用到:

public class Product {



 private String name;

 private String description;

 private List<String> tags;



 // standard getters/setters/constructors



 public Product addTagsOfOtherProdcut(Product product) {

 this.tags.addAll(product.getTags());

 return this;

 }

 }

2.2. Put方法

現在,我們可以使用String類型的鍵和Product類型的元素創建一個HashMap

Map<String, Product> productsByName = new HashMap<>();

並將產品添加到我們的HashMap中

Product eBike = new Product("E-Bike", "A bike with a battery");

 Product roadBike = new Product("Road bike", "A bike for competition");

 productsByName.put(eBike.getName(), eBike);

 productsByName.put(roadBike.getName(), roadBike);

2.3. Get方法

我們可以通過其鍵從地圖中檢索一個值:

Product nextPurchase = productsByName.get("E-Bike");

 assertEquals("A bike with a battery", nextPurchase.getDescription());

如果我們嘗試為地圖中不存在的鍵找到一個值,我們將得到一個值:

Product nextPurchase = productsByName.get("Car");

 assertNull(nextPurchase);

而且,如果我們使用相同的鍵插入第二個值,則只會得到該鍵的最後一個插入值:

Product newEBike = new Product("E-Bike", "A bike with a better battery");

 productsByName.put(newEBike.getName(), newEBike);

 assertEquals("A bike with a better battery", productsByName.get("E-Bike").getDescription());

2.4。null為Key

HashMap還允許我們將null作為鍵:

Product defaultProduct = new Product("Chocolate", "At least buy chocolate");

 productsByName.put(null, defaultProduct);



 Product nextPurchase = productsByName.get(null);

 assertEquals("At least buy chocolate", nextPurchase.getDescription());

2.5。具有相同鍵的值

此外,我們可以使用不同的鍵兩次插入同一對象:

productsByName.put(defaultProduct.getName(), defaultProduct);

 assertSame(productsByName.get(null), productsByName.get("Chocolate"));

2.6。刪除值

我們可以從HashMap中刪除鍵值映射:

productsByName.remove("E-Bike");

 assertNull(productsByName.get("E-Bike"));

2.7。檢查地圖中是否存在鍵或值

要檢查映射中是否存在鍵,我們可以使用containsKey()方法:

productsByName.containsKey("E-Bike");

或者,要檢查映射中是否存在值,可以使用containsValue()方法:

productsByName.containsValue(eBike);

在我們的示例中,兩個方法調用都將返回true 。儘管它們看起來非常相似,但是這兩個方法調用之間在性能上存在重要差異。檢查鍵是否存在的複雜度為O(1) ,而檢查元素的複雜度為O(n),因為有必要遍歷映射中的所有元素。

2.8。遍歷HashMap

有三種在HashMap中迭代所有鍵值對的基本方法。

我們可以遍歷所有鍵的集合:

for(String key : productsByName.keySet()) {

 Product product = productsByName.get(key);

 }

或者我們可以遍歷所有條目的集合:

for(Map.Entry<String, Product> entry : productsByName.entrySet()) {

 Product product = entry.getValue();

 String key = entry.getKey();

 //do something with the key and value

 }

最後,我們可以遍歷所有值:

List<Product> products = new ArrayList<>(productsByName.values());

3.key鍵值

我們可以在HashMap中使用任何類作為鍵。但是,為了使地圖正常工作,我們需要提供equals()和****hashCode()的實現。假設我們想要一個以產品為鍵,價格為值的地圖:

HashMap<Product, Integer> priceByProduct = new HashMap<>();

 priceByProduct.put(eBike, 900);

讓我們實現equals()hashCode()方法:

@Override

 public boolean equals(Object o) {

 if (this == o) {

 return true;

 }

 if (o == null || getClass() != o.getClass()) {

 return false;

 }



 Product product = (Product) o;

 return Objects.equals(name, product.name) &&

 Objects.equals(description, product.description);

 }



 @Override

 public int hashCode() {

 return Objects.hash(name, description);

 }

請注意,僅對於我們要用作映射鍵的類,而不是僅在映射中用作值的類,需要覆蓋hashCode()equals()我們將在本文的第5部分中看到為什麼這樣做是必要的。

4.從Java 8開始的其他方法

Java 8在HashMap中添加了幾種功能樣式的方法。在本節中,我們將介紹其中一些方法。

對於每種方法,我們將看兩個示例。第一個示例顯示如何使用新方法,第二個示例顯示如何在Java的早期版本中實現相同的方法。

由於這些方法非常簡單,因此我們將不再看更詳細的示例。

4.1。 forEach()

forEach方法是一種功能樣式的方法,可以遍歷地圖中的所有元素:

productsByName.forEach( (key, product) -> {

 System.out.println("Key: " + key + " Product:" + product.getDescription());

 //do something with the key and value

 });

在Java 8之前:

for(Map.Entry<String, Product> entry : productsByName.entrySet()) {

 Product product = entry.getValue();

 String key = entry.getKey();

 //do something with the key and value

 }

我們的Java 8 forEach指南文章更詳細地介紹了forEach循環。

4.2。 getOrDefault()

使用getOrDefault()方法,如果給定鍵沒有映射,則可以從映射中獲取值或返回默認元素:

Product chocolate = new Product("chocolate", "something sweet");

 Product defaultProduct = productsByName.getOrDefault("horse carriage", chocolate);

 Product bike = productsByName.getOrDefault("E-Bike", chocolate);

在Java 8之前:

Product bike2 = productsByName.containsKey("E-Bike")

 ? productsByName.get("E-Bike")

 : chocolate;

 Product defaultProduct2 = productsByName.containsKey("horse carriage")

 ? productsByName.get("horse carriage")

 : chocolate;

4.3。 putIfAbsent()

使用此方法,我們可以添加一個新的映射,但前提是給定鍵還沒有映射:

productsByName.putIfAbsent("E-Bike", chocolate);

在Java 8之前:

if(productsByName.containsKey("E-Bike")) {

 productsByName.put("E-Bike", chocolate);

 }

我們的文章使用Java 8合併兩個地圖對這種方法進行了更仔細的研究。

4.4。merge()

並且通過merge(),如果存在映射我們可以修改給定鍵的值,否則可以添加新值:

Product eBike2 = new Product("E-Bike", "A bike with a battery");

 eBike2.getTags().add("sport");

 productsByName.merge("E-Bike", eBike2, Product::addTagsOfOtherProdcut);

在Java 8之前:

if(productsByName.containsKey("E-Bike")) {

 productsByName.get("E-Bike").addTagsOfOtherProdcut(eBike2);

 } else {

 productsByName.put("E-Bike", eBike2);

 }

4.5。compute()

使用compute()方法,我們可以計算給定鍵的值:

productsByName.compute("E-Bike", (k,v) -> {

 if(v != null) {

 return v.addTagsOfOtherProdcut(eBike2);

 } else {

 return eBike2;

 }

 });

在Java 8之前:

if(productsByName.containsKey("E-Bike")) {

 productsByName.get("E-Bike").addTagsOfOtherProdcut(eBike2);

 } else {

 productsByName.put("E-Bike", eBike2);

 }

值得注意的是,方法merge()compute()非常相似。 compute()方法接受兩個參數:和用於重新映射的BiFunction 。並且merge()接受三個參數: key ,如果該鍵尚不存在,則默認值添加到地圖上;以及一個BiFunction用於重新映射。

5. HashMap內部

在本節中,我們將研究HashMap在內部的工作方式,以及使用HashMap代替簡單列表的好處是什麼。

如我們所見,我們可以通過鍵從HashMap檢索元素。一種方法是使用列表,遍歷所有元素,然後在找到與鍵匹配的元素時返回。此方法的時間和空間複雜度均為O(n)

使用HashMap ,我們可以實現放置獲取操作的平均時間複雜度O(1)以及O(n)的空間複雜度。讓我們看看它是如何工作的。

5.1 The Hash Code and Equals

HashMap不會遍歷其所有元素,而是嘗試根據其鍵來計算值的位置。

天真的方法是擁有一個列表,其中可以包含盡可能多的鍵。例如,假設我們的密鑰是小寫字符。然後,有了一個大小為26的列表就足夠了,如果我們想使用鍵“ c”訪問該元素,我們會知道它是位置3的元素,我們可以直接檢索它。

但是,如果我們擁有更大的鍵空間,這種方法將不會非常有效。例如,假設我們的密鑰是一個整數。在這種情況下,列表的大小將必須為2,147,483,647。在大多數情況下,我們的元素也要少得多,因此分配的內存中有很大一部分將保持未使用狀態。

HashMap將元素存儲在所謂的存儲桶中,存儲桶的數量稱為Capacity

當我們在地圖上放置一個值時,鍵的hashCode()方法用於確定將值存儲在其中的存儲桶。

為了檢索值, HashMap使用相同的方式(使用hashCode())計算存儲桶。然後,遍歷該存儲桶中找到的對象,並使用鍵的equals()方法找到完全匹配的對象。

5.2。鍵的不變性

在大多數情況下,我們應該使用不可變鍵。或者至少,我們必須意識到使用可變密鑰的後果。

讓我們看看使用鍵將值存儲在地圖中後,鍵發生更改時會發生什麼。

在此示例中,我們將創建MutableKey

public class MutableKey {

 private String name;



 // standard constructor, getter and setter



 @Override

 public boolean equals(Object o) {

 if (this == o) {

 return true;

 }

 if (o == null || getClass() != o.getClass()) {

 return false;

 }

 MutableKey that = (MutableKey) o;

 return Objects.equals(name, that.name);

 }



 @Override

 public int hashCode() {

 return Objects.hash(name);

 }

 }

然後進行測試:

MutableKey key = new MutableKey("initial");



 Map<MutableKey, String> items = new HashMap<>();

 items.put(key, "success");



 key.setName("changed");



 assertNull(items.get(key));

如我們所見,一旦密鑰更改,我們將不再能夠獲得相應的值,而是返回null這是因為HashMap在錯誤的存儲桶中搜索。

如果我們對HashMap的內部工作方式沒有很好的了解,那麼上述測試案例可能會令人驚訝。

5.3。碰撞

為了使它正常工作,相等的鍵必須具有相同的哈希,但是,不同的鍵可以具有相同的hash 。如果兩個不同的鍵具有相同的哈希,則屬於它們的兩個值將存儲在同一存儲桶中。在存儲桶中,值存儲在列表中,並通過遍歷所有元素來檢索。這是O(n)的代價。

從Java 8開始(請參閱JEP 180 ),如果存儲桶包含8個或更多值,則存儲一個存儲桶中的值的數據結構將從列表更改為平衡樹,如果存儲桶中包含8個或更多值,則將其更改回列表在某一點上,存儲桶中只剩下6個值。這將性能提高為O(log n)

5.4。容量和負載係數

為避免有多個帶有多個值的存儲桶,如果75%(負載因子)的存儲桶為非空,則容量將增加一倍。負載因子的默認值為75%,默認初始容量為16。兩者均可在構造函數中設置。

5.5。putget操作摘要

讓我們總結一下putget操作的工作方式。

當我們向地圖添加元素時, HashMap將計算存儲桶。如果存儲桶中已經包含一個值,則將該值添加到屬於該存儲桶的列表(或樹)中。如果負載係數大於地圖的最大負載係數,則容量將增加一倍。

當我們想從地圖上獲取一個值時, HashMap會計算存儲桶並從列表(或樹)中使用相同的鍵來獲取值。

六,結論

在本文中,我們了解瞭如何使用HashMap及其在內部的工作方式。 HashMapArrayList一起是Java中最常用的數據結構之一,因此對如何使用它以及如何在後台工作有很好的了解非常方便。我們的文章The Java HashMap Under the Hood更詳細地介紹了HashMap的內部。

像往常一樣,可以在Github上獲得完整的源代碼。