Как убедиться, что hashcode() не разрешает одно и то же значение в Java?

У меня есть реализация хэш-кода для класса, и реализация хэш-кода согласуется с тем, что генерирует eclipse, а также с наиболее распространенной практикой, как обсуждалось здесь

Вот моя реализация хэш-кода (все идентификаторы, используемые в этом методе, составляют ключ для объекта):

public int hashCode() {
    final int prime = 31;
    int hashCode = 1;
    if(uId != null){
        hashCode = prime * hashCode + uId.hashCode();
    }
    if(rId != null){
        hashCode = prime * hashCode + rId.hashCode();
    }
    if(bId != null){
        hashCode = prime * hashCode + bId.hashCode();
    }
    if(reId != null){
        hashCode = prime * hashCode + reId.hashCode();
    }
    if(cId != null){
        hashCode = prime * hashCode + cId.hashCode();
    }
    return hashCode;
}

Я столкнулся со сценарием, когда я тестировал очень большой набор данных, и в моей коллекции не было ожидаемого количества объектов этого класса. При внимательном рассмотрении приведенные ниже два набора данных привели к одному и тому же хэш-коду: 50268236873, и, следовательно, запись была заменена последней, которая была добавлена ​​в коллекцию, поскольку их хэш-коды были одинаковыми.

  Existing record :
  Record@2c0781cd[uId=54046,rId=10967,bId=177,reId=1728,cId=50194] 

  Record being inserted into the collection :
  Record@20dad050[uId=53806,rId=18389,bId=177,reId=19026,cId=50194]

Both of these had the hashCode value = 50268236873

Итак, вопросы:

1] Это явный случай, когда хэш-коды двух разных объектов имеют одинаковое значение. Так как же гарантировать, что этого не произойдет ни с одним набором данных? Должно ли простое число быть больше?

2] Если мы внимательно посмотрим, переменная hashCode в реализации имеет тип данных int, наибольшее значение которого равно 2^31 - 1 = 2147483647, что больше, чем хэш-код, вычисленный для приведенный выше набор данных = 50268236873, поэтому происходит переполнение. Есть ли какие-либо последствия для использования long в качестве типа значения hashCode?

спасибо

Редактировать :

Я использую HashSet и после прочтения опубликованных ответов я просмотрел реализацию equals, как показано ниже, и я думаю, потому что в equals я проверяю, совпадают ли хэш-коды двух объектов, и использую это, чтобы определить, являются ли они одни и те же объекты приводят к этой проблеме.

Кто-нибудь из вас, ребята, может это подтвердить?

@Override
    public boolean equals(Object paramObject) {
        boolean equals = false;
        if (paramObject != null) {
            ACRecord other = (ACRecord) paramObject;
            if ((this.hashCode() == other.hashCode()) // I think this is where I am going wrong
                    || (this.uId.equals(other.getUId())
                            && this.rId.equals(other.getRId())
                            && this.reId.equals(other.getReId())
                            && this.bId.equals(other.getBId()) 
                            && this.cId.equals(other.getCId))) {
                equals = true;
            }
        }
        return equals;
    }

Решение. Реализация метода equals была неправильной, так как я использовал hashCode, чтобы определить, равны ли два объекта. Исправление реализации метода equals решило мою проблему, когда hashset заменял существующую запись.


java jakarta-ee java-ee-7 hashcode hash-code-uniqueness
person Nohsib    schedule 20.03.2015    source источник
comment
какая коллекция использовалась? В коллекциях используется только метод equals для обнаружения дубликатов, хеши используются только для ускорения процесса.   -  person Zielu    schedule 20.03.2015
comment
Кроме того: в вашем хеш-коде есть (спорный) логический недостаток. Возможно, вам придется рассмотреть случай, когда каждый идентификатор имеет значение null, если вы хотите сохранить относительную позицию каждого идентификатора в хеше. Таким образом, каждое предложение if может быть лучше сделано как hashCode = prime * hashCode + (id == null ? 0 : id.hashCode());. В качестве бонуса это облегчает чтение метода.   -  person Paul Hicks    schedule 20.03.2015
comment
@Zielu: я использую HashSet.   -  person Nohsib    schedule 20.03.2015
comment
@Paul Hicks: спасибо, я последую твоему совету.   -  person Nohsib    schedule 20.03.2015
comment
Тогда проблема в ваших равных. Вы не можете использовать hashCode для проверки на равенство.   -  person Zielu    schedule 20.03.2015
comment
Вы можете сделать наоборот if (this.hashCode() != other.hashCode()) { return false; }, но вы не можете останавливаться на достигнутом. Вы должны проверить равенство без использования hashCode.   -  person Paul Hicks    schedule 20.03.2015
comment
Да, вы правильно определили, что эта строка в вашем методе equals неверна, и вам следует просто избавиться от нее.   -  person Louis Wasserman    schedule 20.03.2015
comment
Спасибо @LouisWasserman   -  person Nohsib    schedule 20.03.2015

Ответы (5)


arrow_upward
9
arrow_downward

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

Другими словами, если вы выполните map.get("foo") и возникнут коллизии, хеш-карта проверит каждый результат (не хешированный), чтобы убедиться, что он действительно соответствует "foo". Затем он возвращает только точные совпадения.

Также обратите внимание, что, хотя в контракте для хэш-кодов указано, что любые два объекта, которые отвечают true на equals(), должны иметь один и тот же хэш-код, обратное не обязательно верно.

person L. Blanc    schedule 20.03.2015
comment
Я не согласен с вашим ответом, потому что с таким языком, как java, который существует так долго и так широко используется, если коллекции не будут работать должным образом, потому что хэш-коды двух объектов одинаковы из-за конкретной реализации, тогда этот язык не будет использоваться и приниматься в ИТ-индустрии. Должно быть лучшее обоснование, чем ваш ответ. - person Nohsib; 20.03.2015
comment
@Nohsib - вы неправильно понимаете контракт хэш-кода - он предназначен для предоставления хэша, а не уникального идентификатора. Если вы используете коллекции Java, которые используют хэш-код, то, если вы также правильно реализовали equals, они могут решить, как хранить вещи без дубликатов и коллизий. Настоящая проблема с вашим кодом заключается не в реализации хэш-кода, а в том, как вы создаете свою коллекцию - не могли бы вы поделиться ею? - person Ashley Frieze; 20.03.2015
comment
@Носиб. Я должен был быть более ясным. Хэш-карта будет хранить конфликтующие ответы в виде списка, но она включает проверку, которая гарантирует, что вы не получите все в списке как совпадение, а только те, которые действительно совпадают. Другими словами, если вы выполните map.get(foo) и возникнут коллизии, хеш-карта проверит каждый результат (не хешированный), чтобы убедиться, что он действительно соответствует foo. Затем он возвращает только точные совпадения. - person L. Blanc; 20.03.2015
comment
@Nohsib Я не согласен с вашим комментарием, потому что ... обычно вы переопределяете hashCode() и equals(). вместе, чтобы избежать столкновений. - person Neilos; 20.03.2015
comment
@Neilios В ответ на этот другой парень гарантирует, что два равных объекта будут иметь один и тот же хэш. Обратное неверно. - person L. Blanc; 20.03.2015
comment
Спасибо пользователю 58273 и Эшли Фриз за эти разъяснения. Отредактировал вопрос с моей реализацией equals (я думаю, что я ошибаюсь), и я использую HashSet и просто вызываю для него API добавления после создания объекта, который я передаю в API для добавления. - person Nohsib; 20.03.2015

arrow_upward
3
arrow_downward

Вот контракт для hashCode из документов Java 8 (обобщено):

  1. Вызов метода дважды для одного и того же объекта должен привести к одному и тому же значению (для каждого экземпляра JVM).

  2. Если два объекта a и b равны согласно a.equals(b), хэш-коды должны быть одинаковыми.

Вот минимальное определение, удовлетворяющее приведенному выше:

public int hashCode() {
  return 0;
}

Все коллекции java.util.*, такие как HashTable и HashMap, соответствуют этому соглашению и никогда не удаляют элементы из-за повторяющихся хэш-кодов, даже если они дублируются чрезмерно, как в приведенном выше примере. Будет медленно, но правильно.

Вместо этого типичные причины неожиданных результатов при добавлении или извлечении из коллекции на основе хэшей включают:

  • Повторное использование/модификация объектов таким образом, что их хеш-коды меняются во время выполнения (нарушение №1)
  • Не переопределяет .equals(Object)
  • Использование коллекции с ошибками (за пределами java.*), которая предполагает больше о hashCode, чем указано в контракте.
person that other guy    schedule 20.03.2015

arrow_upward
0
arrow_downward

Нет требования, чтобы hashCode был уникальным, только если два объекта равны, их хеш также должен быть равен.

Столкновения хэшей следует ожидать, и это неизбежная причина, как вы заметили, может быть только 2 * maxint возможных значений, поэтому, если возможное пространство объекта превышает это число, должно быть столкновение.

Вы не можете изменить hashCode на long, поскольку он уже определен как int, и он будет использоваться.

Такие коллекции, как hashMap или HashSet, осведомлены о возможных коллизиях и не затрагиваются ими. Ваш пользовательский код также должен быть защищен от коллизий.

person Zielu    schedule 20.03.2015

arrow_upward
0
arrow_downward

Хэш-коды обычно отображают большой диапазон значений в меньший диапазон значений. Это означает, что даже самый совершенный алгоритм хеширования для ваших данных будет создавать коллизии при достижении n + 1 значений, где n — это количество возможных хеш-значений (которое будет 2^32 при использовании int в качестве хеш-кода).

Ваша реализация должна обрабатывать такие коллизии, выполняя полную проверку всех ваших членов вашего объекта, чтобы убедиться, что они действительно равны.

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

Краткое описание реализации хэш-карты см. в этом ответе.

person MarvinPohl    schedule 20.03.2015

arrow_upward
0
arrow_downward

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

person Derek_M    schedule 20.03.2015