编程

Java HashMap 指南

94 2024-06-04 03:17:00

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 和用于重新映射的 BiFunctionmerge() 接受三个参数:key,如果 key 还不存在,则添加到映射中的默认值,以及用于重新映射的 BiFunction

5. HashMap 内部

在本节中,我们将研究 HashMap 是如何在内部工作的,以及使用 HashMap 而不是简单列表的好处是什么。
正如我们所看到的,我们可以通过 HashMap 的键来检索元素。一种方法是使用列表,迭代所有元素,并在找到键匹配的元素时返回。这种方法的时间和空间复杂性都是 O(n)。
使用 HashMap,我们可以实现 putget 操作的平均时间复杂度为 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. Keys’ Immutability

在大多数情况下,我们应该使用不可变的键。或者至少,我们必须意识到使用可变(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. putget 操作的总结

让我们总结一下 put 和 get 操作是如何工作的。
当我们向 Map 中添加一个元素时,HashMap 会计算 bucket。如果 bucket 已经包含一个值,则该值将添加到属于该 bucket 的列表(或树)中。如果负载系数大于 Map 的最大负载系数,则容量将加倍。
当我们想从 Map 中获取值时,HashMap 会计算 bucket,并从列表(或树)中获取具有相同键的值。

6. 结论

本文中,我们了解了如何使用 HashMap 及其内部工作方式。与 ArrayList 一起,HashMap 是 Java 中最常用的数据结构之一,因此了解如何使用它以及它如何在后台工作是非常方便的。
和往常一样,完整的源代码可以在 Github 上获得。