Using a Custom Class as a Key in a Java HashMap – 在Java HashMap中使用一个自定义类作为键

最后修改: 2021年 10月 4日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

In this article, we’ll learn how HashMap internally manages key-value pairs and how to write custom key implementations.

在这篇文章中，我们将学习HashMap内部如何管理键值对，以及如何编写自定义键的实现。

2. Key Management

2.密钥管理

2.1. Internal Structure

2.1.内部结构

Maps are used to store values that are assigned to keys. The key is used to identify the value in the Map and to detect duplicates.

地图用于存储被分配给键的值。键是用来识别Map中的值，并检测重复的值。

While TreeMap uses the Comparable#compareTo(Object) method to sort keys (and also to identify equality), HashMap uses a hash-based structure that can be more easily explained using a quick sketch:

TreeMap使用Comparable#compareTo(Object)方法对键进行排序（也可识别平等性），而HashMap使用基于散列的结构，使用快速草图可以更容易解释。

A Map doesn’t allow duplicate keys, so the keys are compared to each other using the Object#equals(Object) method. Because this method has poor performance, invocations should be avoided as much as possible. This is achieved through the Object#hashCode() method. This method allows sorting objects by their hash values, and then the Object#equals method only needs to be invoked when objects share the same hash value.

Map不允许有重复的键，所以使用Object#equals(Object)方法将键相互比较。因为这个方法的性能很差，所以应尽量避免调用。这可以通过Object#hashCode()方法实现。这个方法允许通过哈希值对对象进行排序，然后Object#equals方法只需要在对象共享相同的哈希值时被调用。

This kind of key management is also applied to the HashSet class, whose implementation uses a HashMap internally.

这种密钥管理也适用于HashSet类，其实现内部使用HashMap。

2.2. Inserting and Finding a Key-Value Pair

2.2.插入并找到一个键值对

Let’s create a HashMap example of a simple shop that manages the number of stock items (Integer) by an article id (String). There, we put in a sample value:

让我们创建一个简单商店的HashMap例子，它通过一个物品ID（String）来管理库存物品的数量（Integer）。在那里，我们放入了一个样本值。

Map<String, Integer> items = new HashMap<>();
// insert
items.put("158-865-A", 56);
// find
Integer count = items.get("158-865-A");

The algorithm to insert the key-value pair:

插入键值对的算法。

  1. calls “158-865-A”.hashCode() to get the hash value
  2. looks for the list of existing keys that share the same hash value
  3. compares any key of the list with “158-865-A”.equals(key)
    1. The first equality is identified as already existing, and the new one replaces the assigned value.
    2. If no equality occurs, the key-value pair is inserted as a new entry.

To find a value, the algorithm is the same, except that no value is replaced or inserted.

要找到一个值，算法是一样的，只是没有替换或插入值。

3. Custom Key Classes

3.自定义键类

We can conclude that to use a custom class for a key, it is necessary that hashCode() and equals() are implemented correctly. To put it simply, we have to ensure that the hashCode() method returns:

我们可以得出结论，要使用自定义类的密钥，必须正确实现hashCode()和equals()。简单地说，我们必须确保hashCode()方法返回。

  • the same value for the object as long as the state doesn’t change (Internal Consistency)
  • the same value for objects that are equal (Equals Consistency)
  • as many different values as possible for objects that are not equal.

We can commonly say that hashCode() and equals() should consider the same fields in their calculation, and we must override both or neither of them. We can easily achieve this by using Lombok or our IDE’s generator.

我们通常可以说，hashCode()和equals()在计算中应该考虑相同的字段，我们必须覆盖这两个字段或者不覆盖。我们可以通过使用Lombok或我们IDE的生成器来轻松实现。

Another important point is: Do not change the hash code of an object while the object is being used as a key. A simple solution is to design the key class to be immutable, but this is not necessary as long as we can ensure that manipulation cannot take place at the key.

另一个重要的观点是。当一个对象被用作密钥时，不要改变该对象的哈希代码。一个简单的解决方案是将密钥类设计为immutable，但只要我们能够确保不能在密钥处进行操作，就没有必要这么做。

Immutability has an advantage here: The hash value can be calculated once on object instantiation, which could increase performance, especially for complex objects.

不变性在这里有一个优势。哈希值可以在对象实例化时计算一次，这可以提高性能，特别是对于复杂的对象。

3.1. Good Example

3.1.好例子

As an example, we’ll design a Coordinate class, consisting of an x and y value, and use it as a key in a HashMap:

作为一个例子，我们将设计一个Coordinate类，由x和y值组成，并将其作为HashMap中的一个键。

Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2);
pixels.put(coord, Color.CYAN);
// read the color
Color color = pixels.get(new Coordinate(1, 2));

Let’s implement our Coordinate class:

让我们来实现我们的Coordinate类。

public class Coordinate {
    private final int x;
    private final int y;
    private int hashCode;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
        this.hashCode = Objects.hash(x, y);
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        Coordinate that = (Coordinate) o;
        return x == that.x && y == that.y;
    }

    @Override
    public int hashCode() {
        return this.hashCode;
    }
}

As an alternative, we could make our class even shorter by using Lombok:

作为一个替代方案，我们可以通过使用龙目岛使我们的课程更短。

@RequiredArgsConstructor
@Getter
// no calculation in the constructor, but
// since Lombok 1.18.16, we can cache the hash code
@EqualsAndHashCode(cacheStrategy = CacheStrategy.LAZY)
public class Coordinate {
    private final int x;
    private final int y;
}

The optimal internal structure would be:

最佳的内部结构将是。

3.2. Bad Example: Static Hash Value

3.2.坏的例子 静态哈希值

If we implement the Coordinate class by using a static hash value for all instances, the HashMap will work correctly, but the performance will drop significantly:

如果我们通过对所有实例使用静态哈希值来实现Coordinate类，HashMap将正确工作，但性能将显著下降。

public class Coordinate {

    ...

    @Override
    public int hashCode() {
        return 1; // return same hash value for all instances
    }
}

The hash structure then looks like this:

然后，哈希结构看起来像这样。

That negates the advantage of hash values completely.

这完全否定了哈希值的优势。

3.3. Bad Example: Modifiable Hash Value

3.3.坏的例子 可修改的哈希值

If we make the key class mutable, we should ensure that the state of the instance never changes while it is used as a key:

如果我们让钥匙类变得可变，我们应该确保在它被用作钥匙的时候，实例的状态永远不会改变。

Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2); // x=1, y=2
pixels.put(coord, Color.CYAN);
coord.setX(3); // x=3, y=2

Because the Coordinate is stored under the old hash value, it cannot be found under the new one. So, the line below would lead to a null value:

因为Coordinate被存储在旧的哈希值下，它不能在新的哈希值下被找到。所以，下面这一行会导致一个空值。

Color color = pixels.get(coord);

And the following line would result in the object being stored twice within the Map:

而下面一行将导致对象在Map中被存储两次。

pixels.put(coord, Color.CYAN);

4. Conclusion

4.总结

In this article, we have clarified that implementing a custom key class for a HashMap is a matter of implementing equals() and hashCode() correctly. We’ve seen how the hash value is used internally and how this would be affected in both good and bad ways.

在这篇文章中，我们阐明了为HashMap实现自定义键类是一个正确实现equals()和hashCode()的问题。我们已经看到了哈希值是如何在内部使用的，以及这将在好的和坏的方面受到影响。

As always, the example code is available over on GitHub.

像往常一样，示例代码可在GitHub上获得。