Java HashMap 指南

1.概述

在这篇文章中，我们将看到如何在Java中使用HashMap，我们将看看它是如何在内部工作的。

与HashMap 非常相似的一个类是Hashtable。请参阅我们的其他几篇文章以了解有关 java.util.Hashtable 类 本身和 HashMap 和 Hashtable 之间的差异。

2.基本使用方法

我们先来看看HashMap是一个map是什么意思。map是一种键值映射，这意味着每个键都精确地映射到一个值，我们可以使用键从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

我们现在可以创建一个HashMap，键的类型为String，元素的类型为Product。

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

我们可以通过键值从map中检索出一个值。

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

如果我们试图为一个不存在于map中的键找到一个值，我们会得到一个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中

要检查map中是否存在键，我们可以使用 containsKey() 方法：

productsByName.containsKey("E-Bike");

或者，为了检查一个值是否存在于map中，我们可以使用containsValue()方法。

productsByName.containsValue(eBike);

在我们的示例中，这两个方法调用都将返回 true。尽管它们看起来非常相似，但这两个方法调用在性能上存在重要差异。检查键是否存在的复杂度为 O(1)，而检查元素是否存在的复杂度为O(n)，因为有必要遍历map中的所有元素。

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中的键。然而，为了使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
}

我们的文章Guide to 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合并两张map对这一方法进行了仔细的研究。

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，一个default value，如果键还不存在的话，就添加到map中，以及一个BiFunction用于重映射。

5.HashMap的内部结构

在这一节中，我们将看看HashMap的内部工作原理，以及使用HashMap以及使用HashMap而不是简单的列表等有哪些好处。

正如我们所看到的，我们可以通过键从HashMap中检索一个元素。一种方法是使用一个列表，遍历所有的元素，当我们找到一个与键相匹配的元素时返回。这种方法的时间和空间复杂性都是O(n)。

通过HashMap，我们可以实现O(1)的平均时间复杂度，用于put和get的操作，空间复杂度为O(n)。让我们看看效果如何。

5.1. 哈希码和equals

HashMap不是在其所有元素上进行迭代，而是试图根据一个值的键来计算它的位置。

天真的方法是拥有一个列表，该列表可以包含尽可能多的元素。 举个例子，假设我们的键是一个小写的字符。那么有一个大小为26的列表就足够了，如果我们想访问键值为‘c'的元素，我们就知道它是在第3位，我们可以直接检索它。

然而，如果我们有一个更大的键空间，这种方法就不太有效了。例如，假设我们的键是一个整数。在这种情况下，列表的大小必须是2,147,483,647。在大多数情况下，我们的元素也会少得多，所以分配的内存有很大一部分是未使用的。

HashMap将元素存储在所谓的桶中，桶的数量被称为容量。

当我们把一个值放到map中时，键的hashCode()方法被用来确定该值将被存储在哪个桶中。

为了检索该值，HashMap以同样的方式计算桶 – 使用hashCode()。然后，它遍历在该桶中的对象，并使用key的equals()方法来找到完全匹配的对象。

5.2.键的不变性

在大多数情况下，我们应该使用不可变的键。或者至少，我们必须意识到使用可变键的后果。

让我们看看，当我们用键在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));

正如我们所看到的，一旦键发生变化，我们就无法再获取相应的值，而是返回 null。 这是因为 HashMap 在错误的桶中搜索。

如果我们对HashMap的内部工作方式没有很好的理解，上述测试案例可能会让人感到惊讶。

5.3.碰撞

为使其正常工作，相等的键必须有相同的哈希值，然而，不同的键可以有相同的哈希值。如果两个不同的键有相同的哈希值，属于它们的两个值将被存储在同一个桶中。在一个桶内，值被存储在一个列表中，并通过在所有元素上循环来检索。这样做的成本是O(n)。

从Java 8开始（见JEP 180），如果一个桶中包含8个或更多的值，那么存储一个桶中的值的数据结构将从列表变为平衡树，如果在某一时刻，桶中只剩下6个值，那么它将变回列表。这使得性能提高到O（log n）。

5.4.容量和负载率

为了避免许多桶有多个值，如果75%（负载系数）的桶成为非空的，容量就会翻倍。负载因子的默认值是75%，默认的初始容量是16。两者都可以在构造函数中设置。

5.5.put和get操作的总结

让我们来总结一下put和get操作是如何工作的。

当我们向map添加一个元素时， HashMap会计算桶。如果该桶已经包含了一个值，该值就会被添加到属于该桶的列表（或树）中。如果负载因子变得比map的最大负载因子大，那么容量就会增加一倍。

当我们想从map中获取一个值时， HashMap计算桶，并从列表（或树）中获取具有相同键的值。

6.结语

在这篇文章中，我们看到了如何使用HashMap以及它的内部工作方式。与ArrayList一起，HashMap是Java中最常用的数据结构之一，所以掌握如何使用它以及它在内部如何工作的知识是非常方便的。我们的文章Java HashMap Under the Hood更详细地介绍了HashMap的内部情况。

像往常一样，完整的源代码可以在Github上获得。