Java HashMap指南

1.概述

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

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

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。put和get操作摘要

讓我們總結一下put和get操作的工作方式。

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

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

六，結論

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

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