How to properly use double coordinates as a key in a HashMap?

Question

I have a class defining a node (a point with three double coordinates).

public class Node {
    private final double x, y, z;

    public Node() {
    }

    public Node(final double x, final double y, final double z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public void setCoordinates(final double x, final double y, final double z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

I need to create a lot of nodes and give them integer IDs, but I must avoid duplicates.

The method to create a node looks like this:

private Node vertex = new Node(0, 0, 0);
private final AtomicInteger nodeCounter = new AtomicInteger();
private final Map<Node, Integer> nodeList = new HashMap<>();

public int addNode(final double x, final double y, final double z) {
    vertex.setCoordinates(x, y, z);

    int nodeId;

    if(nodeList.get(vertex) == null) {
        nodeId = nodeCounter.incrementAndGet();
        nodeList.put(new Node(x, y, z), nodeId);
    } else {
        nodeId = nodeList.get(vertex);
    }

    return  nodeId;
}

Of course, this does not work because the getfunction of the HashMap always returns null.

So I guess I need to override the hashCode method in the Node class.

I have seen here how to do it for a single double, but I don't know how to create a hash function that would take into account the three coordinates of the node.

Do I also have to override the equals function? Or is the hashCode function enough?

First of all: a `double` is a 64-bit type, `int` (the return type of `hashCode()`) is a 32-bit type. Thus, a colission-free mapping is not possible, especially if you need to map three `double` s to one `int`. Second: if you override `hashCode()`, yon do not need to override `equals(...)` because: ["*The general contract of hashCode is: ... If two objects are equal according to the `equals(Object)` method, then calling the `hashCode` method on each of the two objects must produce the same integer result.*"](https://docs.oracle.com/javase/9/docs/api/java/lang/Object.html#hashCode--) — Turing85, Jan 07 '18 at 23:46
@Turing85 *" if you override `hashCode()`, yon do not need to override `equals(...)`"* is a typo hopefully. Your quote says the opposite... — Timothy Truckle, Jan 07 '18 at 23:52
@TimothyTruckle Nope. If you read the contract carefully, you will see that this statement is indeed true (unless you write a `hashCode()`-method that even disregards `==` semantics, which I would regard as forcefully breaking the system). The comment makes a statement starting with "*if tow objects are equal according to `equals(...)`*", but OP did not override `equals(...)`. — Turing85, Jan 07 '18 at 23:56
The obvious question would be "how are you generating these double values?". If "equal" values are just reassigned with no modification, it's no problem, but if there's any arithmetic involved in generating them, you're probably going to have less values that are equal or have the same hash code, and more values that differ by like 0.00000000000001%, which you probably want to consider to be equal, in which case I'd recommend the advice given in [the accepted answer of the linked post](https://stackoverflow.com/a/1074834/1711796). — Bernhard Barker, Jan 07 '18 at 23:57
*"If you read the contract carefully, you will see that this statement is indeed true"* No I can't see that. And especialy as comment to theOPs queistion it is simply **wrong**, because `HashMap` uses `equals` to find the key within the bucket selected by `hashcode` and will not find it with the default `equals` implementation. — Timothy Truckle, Jan 08 '18 at 00:14
You could technically override hashCode without overriding equals, but it would be pretty useless to do so. — Louis Wasserman, Jan 08 '18 at 00:35

Sergey Kalinichenko · Accepted Answer · 2018-01-07T23:54:17.813

7

So I guess I need to override the hashCode method in the Node class.

That's only part of the deal. You also need to override equals in order to make your class work as a key of hash map:

@Override
public int hashCode() {
    return 31*31*Double.valueOf(x).hashCode()
          +   31*Double.valueOf(y).hashCode()
          +      Double.valueOf(z).hashCode();
}
@Override
public boolean equals(Object other) {
    if (!(other instanceof Node)) {
        return false;
    }
    Node n = (Node)other;
    return x == n.x && y == n.y && z == n.z;
}

In Java 8+, Double.valueOf(x).hashCode() should be replaced with Double.hashCode(x) to avoid unnecessary boxing:

@Override
public int hashCode() {
    return 31*31*Double.hashCode(x)
          +   31*Double.hashCode(y)
          +      Double.hashCode(z);
}

Do I also have to override the equals function? Or is the hashCode function enough?

Yes, you must always override equals along with hashCode (why?)

edited Jan 07 '18 at 23:54

answered Jan 07 '18 at 23:45

Sergey Kalinichenko

714,442
84
1,110
1,523

It is the other way around: you need to override `hashCode(...)` if you modify `equals(...)`. You should always override both for consistency, but it is not part of the contract between `hashCode(...)` and `equals(...)`. – Turing85 Jan 07 '18 at 23:48
In Java 8+, `Double.valueOf(x).hashCode()` should be replaced with `Double.hashCode(x)` to avoid unnecessary boxing of the value. – Andreas Jan 07 '18 at 23:52
2

Why not just `return Objects.hash(x, y, z);`? – Mick Mnemonic Jan 08 '18 at 00:20
@MickMnemonic You are right - it's better than pre-8 version. I think Java-8 approach is slightly more efficient, because there's no boxing going on. Thank you for the comment! – Sergey Kalinichenko Jan 08 '18 at 00:25

How to properly use double coordinates as a key in a HashMap?

1 Answers1