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

Question

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

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

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, так что является переполнением. Есть ли какое-либо следствие долгое использование типа значения hashCode?

благодаря
Nohsib

Edit:

Я использую HashSet и после прочтения ответов вывешенных, я посмотрел на реализации 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; 
    } 

Решения: My равно реализация методы была ошибочной, так как я использовал хэш-код, чтобы определить, если два объекта были equal.Correcting реализация методы равно решена моя проблема была HashSet заменяла запись exisintg.

Answer 1

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

Здесь contract for hashCode из Java-8 (документы суммированы):

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

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

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

public int hashCode() { 
    return 0; 
} 

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

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

• Многократного/модификации объектов таким образом, что их хэш-коду изменять во время выполнения (нарушение # 1)
• Не отвергая .equals(Object)
• Использование коллекции багги (за пределами java.*), что предполагает более о hashCode, чем то, что контракт определяет.

Answer 5

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