Java HashMap 中使用自定义类作为键

大多数情况下，我们会选择使用基本数据类型的包装类或者字符串类型作为 HashMap 的 key，但有时我们也希望能自定义键的类型，或者仅仅想知道为什么选择 String 或者基本数据类型的包装类作为 HashMap 的键。

HashMap 结构

HashMap 存储的是 key-value 的键值对形式，在底层是 hash-objects 结构，即数组-链表。

Map 不允许出现重复 key，为此需要比较两个键是否相等。判断相等，我们首先想到的是 equals 方法，但是该方法性能较差，于是就想到了 hashCode()方法，该方法可以得到一个整数值，只有整数值相等的时候（哈希冲突），才会调用 equals() 方法进行更进一步相等校验。

上图中，有 4个对象计算出相同的 hash 码 101，它们被分到同一块区域，它们实际上组成了一个链表，取出 101 对应的对象，需要的时间复杂度为 O(n)。哈希码 315 只对应一个对象，这意味着取出 315 对应的对象，需要的时间复杂度为 O(1)。

插入新元素

向 HashMap 中添加新元素，我们会用到 put() 方法，该方法的逻辑是：

1. 调用 “key”.hashCode() 获取哈希值
2. 查找相同的哈希值的列表
3. 如果找到一个哈希值列表（存在哈希冲突），利用 equals 方法逐一判断元素值是否相等
   3.1 如果相等，就用新的元素替换旧的元素
   3.2 如果没有相等的，就插入该元素
   
4. 如果没有该哈希值，就作为新的元素插入
   

自定义 key

上面的例子中，我们大致可以得出结论，要为键使用的自定义类，必须合理实现 hashCode()和equals()。

其中，hashCode()显得更重要些，它应该要保证：

• 同一个对象，计算的 hash 值应该相同
• 相等的对象，计算的 hash 值应该相同
• 不等的对象，计算的 hash 尽可能不同

自定义key Coordinate

为了描述一个地址信息，我们时常会用到坐标系。Coordinate类，由 x 和 y 值组成，本次我们将其用作 HashMap 中的键：

Coordinate 类中的 equals() 和 hashCode() 是用 IDEA 自动生成的。

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

    // 省略 setters/getters

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = 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 Objects.hash(x, y);
    }
}

Coordinate 用作 HashMap 的键：

Map<Coordinate, Address> addressMap = new HashMap<>();
Coordinate coord = new Coordinate(1, 2);
addressMap.put(coord, new Address());

Coordinate 的 hashCode() 是利用了 x 和 y 综合作用的结果。我们理论上认为，hashCode() 计算的结果是不同的，这样的 HashMap 能达到最佳的查找效率，此时的结构可以这样描述：

如果我们将 hashCode()该写成如下形式：

@Override
public int hashCode() {
    return x*y;
}

此时 HashMap 可以正常工作，但是明显它存在冲突的可能：

private static void cosKey(){
    HashMap<Coordinate, Address> map = new HashMap<>();
    Coordinate cod = new Coordinate(1, 2);
    Coordinate cod2 = new Coordinate(2, 1);
    map.put(cod, new Address());
    map.put(cod2, new Address());
    System.out.println(map.size());
}

cod 和 cod2 将得到相同的 hash 码，但是不妨碍我们将数据放入 HashMap 中，因为 map 的 size() 方法返回 2，此时的结构可以这样描述：

当然还有更糟糕的情况，我们将 hashCode() 返回了固定值：

@Override
public int hashCode() {
    return 101;
}

hash 码的作用完全消失，所有数据被放入同一个链表中，此时的结构可以这样描述：

不可变类

对于同一个类，我们希望无论在何时，都能返回相同的 hash 码。这就需要确保作为 key 的对象一旦初始化后，状态不能被随意修改。

private static void modKey(){
    HashMap<Coordinate, Address> map = new HashMap<>();
    Coordinate cod = new Coordinate(1, 2);
    map.put(cod, new Address());
    System.out.println("修改前 " + map.get(cod));

    // 修改坐标值
    cod.setY(5);
    System.out.println("修改后 " + map.get(cod));
}

我们并没有对 map 进行任何修改，仅仅修改了坐标值，导致 HashMap 中数据 “丢失了”。

难道 HashMap 元素被删除了吗？将 map 打印到控制台：

{com.mapull.map.Coordinate@5=Address(code=null, houseNumber=null)}

实际上，元素没丢，只是 key 的变化，导致我们不能通过原来的 key 找到对应的 value 了。

因此，当对象被用作键时，不要更改对象的哈希码。一个简单的解决方案是将键类设计为不可变的，但这不是必需的，只要我们可以确保不会在键上发生操作即可。

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