Java HashMap 指南
1. 概述
本文中，我们将了解如何在 Java 中使用 HashMap，以及它在内部的工作方式。
Hashtable 是一个与 HashMap 非常相似的类。要了解 Hashtable 类本身以及 HashMap 和 Hashtable 之间的区别，看参照此文。
2. 基本使用
我们先来看看 HashMap 是一个映射指的着什么。Map 是键值对映射，这意味着每个键都映射到一个值，我们可以使用该键从映射中检索相应的值。
人们可能会问，为什么不简单地将值添加到列表中呢。为什么我们需要 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 addTagsOfOtherProduct(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());如果我们试图为映射中不存在的键查找值，我们将得到一个 null 值：
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 作为键
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. 检测键或者值是否存在于 Map 中
要检测键(key)是否在 Map 中，可以使用 containsKey() 方法中：
productsByName.containsKey("E-Bike");要检测值(value)是否在 Map 中，可以使用 containsVlue() 方法中：
productsByName.containsValue(eBike);在我们的示例中，两个方法调用都将返回 true。尽管它们看起来非常相似，但这两个方法调用之间的性能有一个重要的区别。检查 key 是否存在的复杂度为 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. 键
我们可以使用任何类作为 HashMap 中的键。然而，为了使该 Map 正常工作，我们需要提供 equals() 和 hashCode() 的实现。假设我们想要一个以产品为键、以价格为值的 Map：
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() 只需要为我们想用作 Map 键的类重写，而不需要为仅用作 Map 中值的类重写。我们将在本文的第 5 节中了解为什么这是必须的。
4. Java 8 的其他方法
Java 8 向 HashMap 添加了几个函数式方法。在本节中，我们将研究其中的一些方法。
对于每个方法，我们将对照两个示例。第一个示例演示了如何使用此新方法，第二个示例演示如何在早期版本的 Java 中实现相同的方法。
由于这些方法非常简单，我们不看更详细的例子。
4.1. forEach()
forEach 方法是用来在 Map 中迭代所有元素的函数式方法：
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
}4.2. getOrDefault()
使用 getOrDefault() 方法，我们可以从 Map 中获取值，或者在给定键没有映射的情况下返回默认元素：
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);
}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::addTagsOfOtherProduct);Java 8 之前：
if(productsByName.containsKey("E-Bike")) {
productsByName.get("E-Bike").addTagsOfOtherProduct(eBike2);
} else {
productsByName.put("E-Bike", eBike2);
}
4.5. compute()
使用 compute() 方法，我们可以计算给定键的值：
productsByName.compute("E-Bike", (k,v) -> {
if(v != null) {
return v.addTagsOfOtherProduct(eBike2);
} else {
return eBike2;
}
});Java 8 之前：
if(productsByName.containsKey("E-Bike")) {
productsByName.get("E-Bike").addTagsOfOtherProduct(eBike2);
} else {
productsByName.put("E-Bike", eBike2);
}
值得注意的是，方法 merge() 和 compute() 非常相似。compute() 方法接受两个参数：key 和用于重新映射的 BiFunction。merge() 接受三个参数：key，如果 key 还不存在，则添加到映射中的默认值，以及用于重新映射的 BiFunction。
5. HashMap 内部
在本节中，我们将研究 HashMap 是如何在内部工作的，以及使用 HashMap 而不是简单列表的好处是什么。
正如我们所看到的，我们可以通过 HashMap 的键来检索元素。一种方法是使用列表，迭代所有元素，并在找到键匹配的元素时返回。这种方法的时间和空间复杂性都是 O(n)。
使用 HashMap，我们可以实现 put 和 get 操作的平均时间复杂度为 O(1)，空间复杂度为 O(n)。让我们看看它是如何工作的。
5.1. Hash Code 和 Equals
HashMap 尝试根据值的键来计算值的位置，而不是迭代他的所有元素。
简单的方法是有一个列表，其中可以包含尽可能多的键元素。举个例子，假设我们的 key 是小写字符。那么，有一个大小为 26 的列表就足够了，如果我们想访问 key 为 “c” 的元素，我们就会知道它是位于位置 3 的那个，我们可以直接检索它。
然而，如果我们有一个更大的 key 空间，这种方法将不会非常有效。例如，假设我们的 key 是一个整数。在这种情况下，列表的大小必须是 2147483647。在大多数情况下，我们的元素也会少得多，因此分配的内存的很大一部分将保持未使用状态。
HashMap 将元素存储在所谓的 bucket 中，bucket 的数量称为容量(capacity)。
当我们在映射中放入一个值时，键(key)的 hashCode() 方法用于确定存储该值的 bucket。
为了检索值，HashMap 以相同的方式计算 bucket——使用 hashCode()。然后，它遍历在该 bucket 中找到的对象，并使用 key 的 equals() 方法来找到完全匹配的对象。
5.2.不可变的 Key
在大多数情况下，我们应该使用不可变的键。或者至少，我们必须意识到使用可变(mutable) key 的后果。
让我们看看当我们的 key 在映射(Map)中存储值后发生更改时会发生什么。
本例中，我们创建了 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));正如我们所看到的，一旦 key 发生更改，我们就无法再获得相应的值，而是返回 null。这是因为 HashMap 在错误的 bucket 中进行搜索。
如果我们对 HashMap 的内部工作方式没有很好的了解，那么上面的测试用例可能会令人惊讶。
5.3. 冲突
为了正确工作，相等的 key 必须具有相同的哈希，但是，不同的 key 可以具有相同的哈希。如果两个不同的 key 具有相同的 hash，则属于它们的两个值将存储在同一个 bucket 中。在 bucket 中，值存储在列表中，并通过循环遍历所有元素来检索。这样做的成本是 O(n)。
从 Java 8(见 JEP 180)开始，如果一个 bucket 包含 8 个或更多值，则存储一个 bucket 盒内的值的数据结构将从列表变为平衡树，如果在某个时刻存储桶中只剩下 6 个值，则数据结构将变回列表。这将性能提高到 O(log n)。
5.4. 容量和负载系数
为了避免具有多个值的多个 bucket，如果 75%(负载系数)的 bucket 变为非空，则容量将加倍。负载系数的默认值为 75%，默认初始容量为 16。两者都可以在构造函数中设置。
5.5. put 和 get 操作的总结
让我们总结一下 put 和 get 操作是如何工作的。
当我们向 Map 中添加一个元素时，HashMap 会计算 bucket。如果 bucket 已经包含一个值，则该值将添加到属于该 bucket 的列表(或树)中。如果负载系数大于 Map 的最大负载系数，则容量将加倍。
当我们想从 Map 中获取值时，HashMap 会计算 bucket，并从列表(或树)中获取具有相同键的值。
6. 结论
本文中，我们了解了如何使用 HashMap 及其内部工作方式。与 ArrayList 一起，HashMap 是 Java 中最常用的数据结构之一，因此了解如何使用它以及它如何在后台工作是非常方便的。
上一篇 
QQ 空间
QQ 好友
微博