Создание классов Java, используемых в качестве ключей для hashmap

Question

Я создал класс под названием Coordinates, который просто содержит целые числа x и y. Я хочу использовать это как ключ для HashMap.

Однако я заметил, что при создании двух различных экземпляров Coordinates с теми же x и y значений, они используются в качестве различных ключей по хэш-карте. То есть вы можете поместить две записи, даже если обе они имеют одинаковые координаты.

Я перекрываться equals():

public boolean equals(Object obj) { 
    if (!(obj instanceof Coord)) { 
     return false; 
    }else if (obj == this) { 
     return true; 
    } 
    Coord other = (Coord)obj; 
    return (x == other.x && y == other.y); 
} 

Но HashMap все еще использует два экземпляра, как если бы они были разными ключами. Что я делаю?

И я знаю, что вместо этого я мог бы использовать целочисленный массив из двух элементов. Но я хочу использовать этот класс.

Answer 1

Вам необходимо переопределить hashCode. Java 7 предоставляет для этого полезный метод.

@Override 
public int hashCode() { 
    return Objects.hash(x, y); 
} 

Answer 2

Вы также должны переопределить hashCode(), чтобы два равных экземпляра имели одинаковые hashCode(). Например .:

@Override 
public int hashCode() { 
    int result = x; 
    result = 31 * result + y; 
    return result; 
} 

Обратите внимание, что это не является строго обязательным для двух экземпляров, которые не равны, имеют разные хэш-коды, но меньше столкновений у вас есть, тем лучше производительность вы получите от вас HashMap.

Answer 3

Хэш карта использует метод hashCode объектов, чтобы определить, какие ведра поместить объект в. Если ваш объект не реализует hashCode, он наследует реализацию по умолчанию от Object. От docs:

Насколько разумно практично, метод hashCode, определенный классом Object, возвращает различные целые числа для разных объектов. (Обычно это реализуется путем преобразования внутреннего адреса объекта в целое число, но этот способ реализации не требуется языком программирования JavaTM.)

Таким образом, каждый объект будет отличаться.

Обратите внимание, что разные объекты могут возвращать то же самое hashCode. Это называется столкновение . Когда это произойдет, , то в дополнение к hashCode, реализация хэш-карты будет использовать метод equals, чтобы определить, равны ли два объекта.

Обратите внимание, что большинство IDE предлагают генерировать методы equals и hashCode из полей, определенных в вашем классе. На самом деле IntelliJ рекомендует определять эти два метода одновременно. Не зря. Эти два метода тесно связаны: и всякий раз, когда вы меняете один из них или реализуете один из них или переопределяете один из них, , вы должны просмотреть (и, скорее всего, изменить) другой.

Методы этого класса являются 100% сгенерированный код (по IntelliJ):

class Coord { 
    private int x; 
    private int y; 

    @Override 
    public boolean equals(Object o) { 
     if (this == o) return true; 
     if (o == null || getClass() != o.getClass()) return false; 

     Coord coord = (Coord) o; 

     if (x != coord.x) return false; 
     if (y != coord.y) return false; 

     return true; 
    } 

    @Override 
    public int hashCode() { 
     int result = x; 
     result = 31 * result + y; 
     return result; 
    } 
} 

Answer 4

Вы, вероятно, не переопределить метод hashCode. Почему это требуется? Чтобы ответить на это, вы должны понять, как работает хэш-таблица.

Хэш-таблица в основном представляет собой набор связанных списков. Каждое ведро в массиве соответствует конкретному значению hashCode % numberOfBuckets. Все объекты с одинаковыми hashCode % numberOfBuckets будут сохранены в связанном списке в ассоциированном ведре и будут распознаны (во время поиска для примера) на основе их метода equals. Поэтому точная спецификация - a.hashCode() != b.hashCode() => !a.equals(b), что эквивалентно a.equals(b) => a.hashCode() == b.hashCode().

Если вы используете стандартную реализацию hashCode, которая основана на ссылке, то два объекта, которые являются равными, но имеют другую ссылку (и, следовательно, скорее всего, другой хэш-код), будут храниться в другом ведре, в результате получается дубликат ключа.