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

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

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

Практически во всех случаях разумная хорошая реализация была предложена в « Эффективной 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 if f == null;
   • Если поле f является массивом : рассмотрите каждое поле как отдельный элемент и вычислите значение хеш-функции рекурсивным способом и объедините значения, как описано далее.

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

   result = 37 * result + c

4. Возвращение result

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

Если вы довольны реализацией Effective 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), но работает так же.

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

Хотя это связано с 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));
}

Сначала убедитесь, что 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 ()

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

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

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

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

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

но

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

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

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

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

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

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

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

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

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

@ 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, это уродливо.)

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

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

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

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

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

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

Вот еще одна демонстрация подхода JDK 1.7+ с учетом логики суперкласса. Я считаю это довольно удобным с учетом класса Object 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.

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

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

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

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

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

Для простого класса часто проще всего реализовать 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 () должен возвращать разные значения.