Using a Custom Class as a Key in a Java HashMap

1. 概述

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

2. 键管理

2.1. 内部结构

地图用于存储由键分配的值。键用于在Map中标识值，并检测重复。

虽然TreeMap使用Comparable#compareTo(Object)方法对键进行排序（并确定相等性），但HashMap使用基于哈希的结构，这可以通过快速草图来更好地解释：

Map不允许重复键，因此使用Object#equals(Object)方法比较键。由于这个方法性能较差，应尽可能避免调用。这是通过Object#hashCode()方法实现的。此方法允许根据对象的哈希值进行排序，然后只有当对象具有相同的哈希值时才调用Object#equals方法。

这种键管理方式也应用于内部使用HashMap的HashSet类。

2.2. 插入和查找键值对

让我们创建一个简单的商店示例，使用文章ID（String）管理库存项目数量（Integer）。我们插入一个示例值：

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

插入键值对的算法如下：

调用"158-865-A".hashCode()获取哈希值
查找具有相同哈希值的现有键列表
比较列表中的任何键与"158-865-A".equals(key)：
- 第一次相等被识别为已存在，新值替换现有值。
- 如果没有相等发生，键值对作为新条目插入。

查找值的算法相同，只是不替换或插入值。

3. 自定义键类

我们可以得出结论，为了在HashMap中使用自定义类作为键，必须正确实现hashCode()和equals()方法。简单来说，我们需要确保hashCode()方法返回：

对象状态不变时，始终返回相同的值（内部一致性）
对于相等的对象，返回相同的值（相等一致性）
对于不相等的对象，尽可能返回不同的值。

通常可以说，hashCode()和equals()方法的计算应考虑相同的字段，并且我们必须重写两者之一或两者都不重写。我们可以通过使用Lombok或IDE生成器轻松实现这一点。

另一个重要点是：在对象作为键使用期间，不要更改其哈希代码。一个简单的解决方案是设计键类为不可变对象，但这并不是必需的，只要我们能确保不会在键上进行操作即可。

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

3.1. 好例子

作为一个例子，我们将设计一个包含x和y值的Coordinate类，并将其用作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));

让我们实现我们的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;
    }
}

或者，我们可以通过使用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;
}

理想的内部结构将是：

3.2. 坏例子：静态哈希值

如果我们使用所有实例的静态哈希值实现Coordinate类，HashMap将正常工作，但性能会显著下降：

public class Coordinate {

    ...

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

这时的哈希结构如下：

这完全消除了哈希值的优势。

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

如果使键类可变，我们应该确保在键作为键使用时，实例的状态永远不会改变：

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

因为Coordinate存储在旧的哈希值下，它无法在新的哈希值下找到。所以，以下行会导致null值：

Color color = pixels.get(coord);

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

pixels.put(coord, Color.CYAN);

4. 总结

在这篇文章中，我们明确了在HashMap中实现自定义键类的问题，即正确实现equals()和hashCode()方法。我们了解了哈希值在内部是如何使用的，以及在好与坏的情况下它会产生什么影响。

如往常一样，示例代码可在GitHub上获取。

Persistence

REST

Security