Лучшая реализация метода hashCode для коллекции

Question

Как мы выбираем наилучшую реализацию метода hashCode() для коллекции (при условии, что метод equals был корректно переопределен)?

Answer 1

Лучшая реализация? Это сложный вопрос, поскольку он зависит от модели использования.

A для почти всех случаев разумная хорошая реализация была предложена в Джош Блох Эффективная Java в пункте 8 (второе издание). Лучше всего посмотреть на это там, потому что автор объясняет, почему подход хорош.

короткая версия

1. Создайте int result и присвойте ненулевое значение.

2. Для каждого поля f, проверенного по методу equals(), вычислить хеш-код c по:

   • Если поле f является boolean: рассчитать (f ? 0 : 1);
   • Если поле f является byte, char, short или int: вычислить (int)f;
   • Если поле f является long: вычислить (int)(f ^ (f >>> 32));
   • Если поле f является float: вычислить Float.floatToIntBits(f);
   • Если поле f является double: вычислить Double.doubleToLongBits(f) и обработать возвращаемое значение, как каждое длинное значение;
   • Если поле f является объектом : используйте результат метода hashCode() или 0, если f == null;
   • Если поле f является массивом : посмотрите каждое поле как отдельный элемент и вычислите значение хеша рекурсивным способом и объедините значения, как описано далее.

3. Объедините хеш-значение c с result:

   result = 37 * result + c
   

4. Возврат result

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

Answer 2

Если вы довольны реализацией Effective Java, рекомендованной dmeister, вы можете использовать библиотечный вызов вместо собственного:

@Override
public int hashCode() {
    return Objects.hashCode(this.firstName, this.lastName);
}

Для этого требуется либо Гуава (com.google.common.base.Objects.hashCode), либо стандартная библиотека в Java 7 (java.util.Objects.hash), но она работает аналогично.

Answer 3

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

Answer 4

Хотя это связано с Android документацией (Wayback Machine) и Моим собственным кодом на Github , он будет работать для Java в целом. Мой ответ является расширением ответа dmeister с помощью всего лишь кода, который намного легче читать и понимать.

@Override 
public int hashCode() {

    // Start with a non-zero constant. Prime is preferred
    int result = 17;

    // Include a hash for each field.

    // Primatives

    result = 31 * result + (booleanField ? 1 : 0);                   // 1 bit   » 32-bit

    result = 31 * result + byteField;                                // 8 bits  » 32-bit 
    result = 31 * result + charField;                                // 16 bits » 32-bit
    result = 31 * result + shortField;                               // 16 bits » 32-bit
    result = 31 * result + intField;                                 // 32 bits » 32-bit

    result = 31 * result + (int)(longField ^ (longField >>> 32));    // 64 bits » 32-bit

    result = 31 * result + Float.floatToIntBits(floatField);         // 32 bits » 32-bit

    long doubleFieldBits = Double.doubleToLongBits(doubleField);     // 64 bits (double) » 64-bit (long) » 32-bit (int)
    result = 31 * result + (int)(doubleFieldBits ^ (doubleFieldBits >>> 32));

    // Objects

    result = 31 * result + Arrays.hashCode(arrayField);              // var bits » 32-bit

    result = 31 * result + referenceField.hashCode();                // var bits » 32-bit (non-nullable)   
    result = 31 * result +                                           // var bits » 32-bit (nullable)   
        (nullableReferenceField == null
            ? 0
            : nullableReferenceField.hashCode());

    return result;

}

EDIT

Как правило, когда вы переопределяете hashcode(...), вы также хотите переопределить equals(...). Так что для тех, кто будет или уже внедрил equals, вот хороший справочник от моего Github ...

@Override
public boolean equals(Object o) {

    // Optimization (not required).
    if (this == o) {
        return true;
    }

    // Return false if the other object has the wrong type, interface, or is null.
    if (!(o instanceof MyType)) {
        return false;
    }

    MyType lhs = (MyType) o; // lhs means "left hand side"

            // Primitive fields
    return     booleanField == lhs.booleanField
            && byteField    == lhs.byteField
            && charField    == lhs.charField
            && shortField   == lhs.shortField
            && intField     == lhs.intField
            && longField    == lhs.longField
            && floatField   == lhs.floatField
            && doubleField  == lhs.doubleField

            // Arrays

            && Arrays.equals(arrayField, lhs.arrayField)

            // Objects

            && referenceField.equals(lhs.referenceField)
            && (nullableReferenceField == null
                        ? lhs.nullableReferenceField == null
                        : nullableReferenceField.equals(lhs.nullableReferenceField));
}

Answer 5

Сначала убедитесь, что функция equals реализована правильно. Из статьи IBM DeveloperWorks :

• Симметрия: для двух ссылок, a и b, a.equals (b) тогда и только тогда, когда b.equals (a)
• Отражательная способность: Для всех ненулевых ссылок a.equals (a)
• Транзитивность: если a.equals (b) и b.equals (c), то a.equals (c)

Затем убедитесь, что их связь с hashCode учитывает контакт (из той же статьи):

• Согласованность с hashCode (): два равных объекта должны иметь одинаковое значение hashCode ()

Наконец, хорошая хеш-функция должна стремиться приблизиться к идеальной хеш-функции .

Answer 6

about8.blogspot.com, вы сказали

если equals () возвращает true для двух объектов, то hashCode () должен возвращать одно и то же значение. Если equals () возвращает false, то hashCode () должен возвращать разные значения

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

Если A равно B, тогда A.hashcode должен быть равен B.hascode

но

если A.hashcode равен B.hascode, это не означает, что A должно равняться B

Answer 7

Если вы используете Eclipse, вы можете сгенерировать equals() и hashCode(), используя:

Source -> Generate hashCode () и equals ().

Используя эту функцию, вы можете решить , какие поля вы хотите использовать для вычисления равенства и хеш-кода, и Eclipse генерирует соответствующие методы.

Answer 8

Существует хорошая реализация логики Effective Java * hashcode() и equals() в Apache Commons Lang . Оформить заказ HashCodeBuilder и EqualsBuilder .

Answer 9

Просто краткое примечание для завершения другого более подробного ответа (в терминах кода):

Если я рассмотрю вопрос how-do-i-create-a-has-table-in-java и особенно запись jGuru FAQ , я считаю, что некоторые другие критерии какой хеш-код может быть оценен:

• синхронизация (поддерживает ли параллельный доступ или нет)?
• отказоустойчивая итерация (обнаруживает ли алгоритм коллекцию, которая изменяется во время итерации)
• нулевое значение (поддерживает ли хеш-код пустое значение в коллекции)

Answer 10

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

Если ваш класс коллекции расширяет AbstractList, вам не нужно об этом беспокоиться, уже есть реализация equals () и hashCode (), которая работает путем перебора всех объектов и добавления их hashCodes () вместе.

   public int hashCode() {
      int hashCode = 1;
      Iterator i = iterator();
      while (i.hasNext()) {
        Object obj = i.next();
        hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
      }
  return hashCode;
   }

Теперь, если то, что вы хотите, является наилучшим способом вычисления хеш-кода для определенного класса, я обычно использую оператор ^ (побитовый исключающий или) для обработки всех полей, которые я использую в методе equals:

public int hashCode(){
   return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}