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

Для простого класса часто проще всего реализовать hashCode () на основе полей класса, которые проверяются реализацией equals ().

public class Zam {
    private String foo;
    private String bar;
    private String somethingElse;

    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }

        if (obj == null) {
            return false;
        }

        if (getClass() != obj.getClass()) {
            return false;
        }

        Zam otherObj = (Zam)obj;

        if ((getFoo() == null && otherObj.getFoo() == null) || (getFoo() != null && getFoo().equals(otherObj.getFoo()))) {
            if ((getBar() == null && otherObj. getBar() == null) || (getBar() != null && getBar().equals(otherObj. getBar()))) {
                return true;
            }
        }

        return false;
    }

    public int hashCode() {
        return (getFoo() + getBar()).hashCode();
    }

    public String getFoo() {
        return foo;
    }

    public String getBar() {
        return bar;
    }
}

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

@ about8: там довольно серьезная ошибка.

Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");

тот же хэш-код

ты, наверное, хочешь что-то вроде

public int hashCode() {
    return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();

(вы можете получить hashCode прямо из int в Java в наши дни? Я думаю, что он выполняет автокастинг ... в этом случае пропустите toString, это некрасиво.)

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

• Symmetry: For two references, a and b, a.equals(b) if and only if b.equals(a)
• Reflexivity: For all non-null references, a.equals(a)
• Transitivity: If a.equals(b) and b.equals(c), then a.equals(c)

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

• Consistency with hashCode(): Two equal objects must have the same hashCode() value

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

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

Если я рассмотрю вопрос как-сделать-я-создать-хеш-таблицу-в-Java и особенно Запись часто задаваемых вопросов jGuru, я считаю, что некоторые другие критерии, по которым можно судить о хэш-коде, следующие:

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

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

Если я правильно понимаю ваш вопрос, у вас есть собственный класс коллекции (т.е. новый класс, который расширяется от интерфейса Collection), и вы хотите реализовать метод 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);
}

любой метод хеширования, который равномерно распределяет хеш-значение по возможному диапазону, является хорошей реализацией. См. Эффективную java (http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=ru&sa=X&ult&result=news&result&result&result=ru&sa=X&result&result&result=news), там есть хороший совет для реализации хэш-кода (пункт 9, я думаю ...).

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

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

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

В Apache Commons Lang есть хорошая реализация логики hashcode() и equals()Эффективная Java. Оформить заказ HashCodeBuilder и EqualsBuilder.

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

if equals() returns true for two objects, then hashCode() should return the same value. If equals() returns false, then hashCode() should return different values

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

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

но

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

Я предпочитаю использовать служебные методы из Библиотека Google Collections из класса Objects, которые помогают мне поддерживать мой код в чистоте. Очень часто методы equals и hashcode создаются из шаблона IDE, поэтому их трудно читать.

Используйте методы отражения в Apache Commons EqualsBuilder и HashCodeBuilder.

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

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

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

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

При объединении хеш-значений я обычно использую метод объединения, который используется в библиотеке boost C++, а именно:

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

Это достаточно хорошо для обеспечения равномерного распределения. Некоторое обсуждение того, как работает эта формула, можно найти в сообщении StackOverflow: Магическое число в бусте :: hash_combine

Хорошее обсуждение различных хеш-функций: http://burtleburtle.net/bob/hash/doobs.html

Если вас устраивает эффективная реализация Java, рекомендованная dmeister, вы можете использовать вызов библиотеки вместо собственного:

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

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

Хотя это связано с Документация 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;

}

РЕДАКТИРОВАТЬ

Обычно, когда вы переопределяете 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));
}

Я использую крошечную оболочку вокруг Arrays.deepHashCode(...), потому что она правильно обрабатывает массивы, предоставленные в качестве параметров

public static int hash(final Object... objects) {
    return Arrays.deepHashCode(objects);
}

Вот еще одна демонстрация подхода JDK 1.7+ с учётом логики суперкласса. Я считаю это довольно удобным с учётом класса объекта hashCode (), чистой зависимостью от JDK и без дополнительной ручной работы. Обратите внимание, что Objects.hash() является нулевым допуском.

Я не включил какую-либо реализацию equals(), но на самом деле она вам, конечно, понадобится.

import java.util.Objects;

public class Demo {

    public static class A {

        private final String param1;

        public A(final String param1) {
            this.param1 = param1;
        }

        @Override
        public int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param1);
        }

    }

    public static class B extends A {

        private final String param2;
        private final String param3;

        public B(
            final String param1,
            final String param2,
            final String param3) {

            super(param1);
            this.param2 = param2;
            this.param3 = param3;
        }

        @Override
        public final int hashCode() {
            return Objects.hash(
                super.hashCode(),
                this.param2,
                this.param3);
        }
    }

    public static void main(String [] args) {

        A a = new A("A");
        B b = new B("A", "B", "C");

        System.out.println("A: " + a.hashCode());
        System.out.println("B: " + b.hashCode());
    }

}

Стандартная реализация слабая, и ее использование приводит к ненужным конфликтам. Представьте себе

class ListPair {
    List<Integer> first;
    List<Integer> second;

    ListPair(List<Integer> first, List<Integer> second) {
        this.first = first;
        this.second = second;
    }

    public int hashCode() {
        return Objects.hashCode(first, second);
    }

    ...
}

Сейчас же,

new ListPair(List.of(a), List.of(b, c))

и

new ListPair(List.of(b), List.of(a, c))

имеют тот же hashCode, а именно 31*(a+b) + c, поскольку множитель, используемый для List.hashCode, здесь используется повторно. Очевидно, столкновения неизбежны, но создавать ненужные столкновения просто ... излишне.

Нет ничего особенного в использовании 31. Множитель должен быть нечетным, чтобы избежать потери информации (любой четный множитель теряет по крайней мере самый старший бит, кратные четырем теряют два и т. д.). Можно использовать любой нечетный множитель. Небольшие множители могут привести к более быстрым вычислениям (JIT может использовать сдвиги и добавления), но, учитывая, что умножение имеет задержку всего в три цикла на современных Intel / AMD, это вряд ли имеет значение. Маленькие множители также приводят к большему количеству конфликтов для небольших входов, что иногда может быть проблемой.

Использование простого числа бессмысленно, поскольку простые числа не имеют смысла в кольце Z / (2 ** 32).

Итак, я бы рекомендовал использовать случайно выбранное большое нечетное число (не стесняйтесь брать простое). Поскольку процессоры i86 / amd64 могут использовать более короткие инструкции для подгонки операндов в один знаковый байт, есть небольшое преимущество в скорости для таких множителей, как 109. Для минимизации коллизий возьмите что-то вроде 0x58a54cf5.

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