Java hashCode doesn't work with HashMap?

Question

I'm attempting to implement a sparse grid using HashMap, however it seems that overriding hashCode() doesn't work quite how I expect. I've boiled down my issue to the following code:

public class Main {

private static class Coord {
    int x, y;

    public Coord(int x, int y) {
        this.x = x;
        this.y = y;
        }

        @Override
        public int hashCode() {
            // See https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function
            return (((x + y) * (x + y + 1)) / 2) + y;
        }
    }

    public static void main(String[] args) {
        HashMap<Coord, String> grid = new HashMap<Coord, String>();
        grid.put(new Coord(0, 0), "A");
        System.out.println(grid.get(new Coord(0, 0)));
    }
}

I'm expecting the output to be:

A

However, the output is:

null

Both the "new Coord(0, 0)" instances should return the same hashCode(), but it doesn't seem to work how I expected. Why doesn't it work as I expect?

Answer 1

A HashMap cannot work on hashCode alone. It relies on equals as well.

To explain why, let's consider a HashMap<String, ?>. Supposing for a second that one has infinite memory, one can create an infinite number of keys for this map, but only 4.3 million or so possible hash codes (the number of possible ints). Thus, there will be collisions. This is why equals is required in order to make sure that we're getting the value for the correct key.