likes
comments
collection
share

Java HashMap 使用指南

作者站长头像
站长
· 阅读数 29

1. 概述

在本文中，我们将了解如何在 Java 中使用HashMap，并了解其内部工作原理。

与HashMap非常相似的一个类是Hashtable。HashMap 和 Hashtable 都是Java中常用的数据结构，它们都是基于哈希表的实现，用于存储键值对。但它们有一些关键区别：

1. 线程安全性:

  • HashMap 是非线程安全的，这意味着在多线程环境中，多个线程同时访问 HashMap 可能导致数据不一致。
  • Hashtable 是线程安全的，它使用 synchronized 关键字来同步所有方法，因此在多线程环境中可以安全使用。

2. 允许 null 键值:

  • HashMap 允许键和值都为 null。
  • Hashtable 不允许键或值为空。如果尝试插入 null 键或值，会抛出 NullPointerException。

3. 迭代器:

  • HashMap 的迭代器是 fail-fast 的，这意味着如果在迭代期间修改了 HashMap，迭代器会抛出 ConcurrentModificationException。
  • Hashtable 的迭代器是 fail-safe 的，这意味着即使在迭代期间修改了 Hashtable，迭代器也不会抛出异常，而是返回一个迭代时状态的副本。

4. 性能:

  • HashMap 通常比 Hashtable 性能更高，因为它没有线程同步的开销。
  • Hashtable 由于线程同步，性能较低。

5. 继承:

  • HashMap 继承自 AbstractMap 类。
  • Hashtable 继承自 Dictionary 类。

6. 总结:

  • 如果需要线程安全的哈希表，使用 Hashtable。
  • 如果需要更高效的哈希表，并且应用程序是单线程的，使用 HashMap。
  • 如果应用程序是多线程的，但不需要线程安全性，可以使用 ConcurrentHashMap，它是 HashMap 的线程安全版本，性能比 Hashtable 更好。

2.基本用法

首先我们来看一下HashMap是一个映射，它的含义是什么。映射是一种键值映射，这意味着每个键都映射到一个值，我们可以使用该键从映射中检索相应的值。

有人可能会问为什么不直接将值添加到列表中。为什么我们需要 HashMap  ？ 原因很简单，就是性能。如果我们想在列表中查找特定元素，时间复杂度为O(n)  ，如果列表已排序，则使用二分搜索等方法，时间复杂度为O(log n) 。

HashMap的优点是插入和检索值的时间复杂度平均为O(1) 。稍后我们将介绍如何实现这一点。首先让我们看看如何使用HashMap。

2.1. setup创建

让我们创建一个将在整篇文章中使用的简单类：

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());复制

如果我们尝试查找映射中不存在的键的值，我们将得到一个空值：

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. remove删除一个值

我们可以从HashMap中删除一个键值映射：

productsByName.remove("E-Bike");
assertNull(productsByName.get("E-Bike"));复制

2.7 检查 Map 中是否存在某个键或值

要检查映射中是否存在某个键，我们可以使用 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
}

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);
}

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 ** *****() 方法接受两个参数：键和用于重新映射的BiFunction。merge () 接受三个参数：键、如果键尚不存在则添加到映射的默认值以及用于重新映射的BiFunction 。

5. HashMap内部原理

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

如我们所见，我们可以通过键从HashMap中检索元素。一种方法是使用列表，遍历所有元素，并在找到与键匹配的元素时返回。这种方法的时间和空间复杂度均为O(n) 。

使用HashMap ，我们可以实现 put和get操作的平均时间复杂度为O  (1) ，空间复杂度为O(n) 。 ******让我们看看它是如何工作的。

5.1. HashCode 和 Equals

HashMap不会迭代所有元素，而是尝试根据键计算值的位置。

最简单的方法是创建一个列表，该列表可以包含与键数相同的元素。例如，假设我们的键是小写字符。那么有一个大小为 26 的列表就足够了，如果我们想访问键为“c”的元素，我们会知道它是位置 3 的元素，我们可以直接检索它。

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

HashMap将元素存储在所谓的存储桶 (bucket) 中，存储桶的数量称为容量 (Capacity) 。 当我们将一个值放入映射中时，将使用键的hashCode() 方法来确定将存储该值的存储桶。

为了检索值，HashMap以相同的方式计算存储桶 - 使用hashCode() 。然后它遍历该存储桶中找到的对象并使用键的equals() 方法找到精确匹配。

5.2. Key Immutability密钥的不变性

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

让我们看看当我们使用键将值存储在映射中后，如果键发生变化，会发生什么。

对于此示例，我们将创建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 发生变化，我们就无法获取相应的 value，而是返回null 。 这是因为HashMap在错误的 bucket 中搜索。

如果我们不太了解HashMap 的内部工作原理，上述测试用例可能会令人惊讶。

5.3. 碰撞

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

从 Java 8 开始（参见JEP 180），如果存储桶包含 8 个或更多值，则存储桶内值的数据结构将从列表更改为平衡树；如果某个时候存储桶中只剩下 6 个值，则数据结构将变回列表。这可将性能提高到O(log n) 。

5.4. 容量和负载因子

为了避免出现多个具有多个值的 bucket，如果 75%（负载因子）的 bucket 变为非空，则容量将加倍。负载因子的默认值为 75%，默认初始容量为 16。两者都可以在构造函数中设置。

5.5. put和get操作总结

让我们总结一下put和get操作的工作原理。

当我们向 Map 添加元素时，  HashMap会计算 bucket。如果 bucket 中已经包含一个值，则该值将添加到属于该 bucket 的列表（或树）中。如果负载因子大于 Map 的最大负载因子，则容量将加倍。

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

6. 结论

在本文中，我们了解了如何使用HashMap以及它的内部工作原理。与ArrayList一样，HashMap是 Java 中最常用的数据结构之一，因此了解如何使用它以及它的内部工作原理非常有帮助。

转载自:https://juejin.cn/post/7388488504056217636
评论
请登录