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

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

Источник

20 ответов

Решение

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

Практически во всех случаях разумная хорошая реализация была предложена в " Эффективной 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

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

Источник

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

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

Это требует либо гуавы (com.google.common.base.Objects.hashCode(...)) или JDK7 (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));
}
Источник

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

Источник

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

Источник

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

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

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

Источник

Есть хорошая реализация эффективной Javahashcode() а также equals() логика в Apache Commons Lang. Оформить заказ HashCodeBuilder и EqualsBuilder.

Источник

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

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

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

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

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

public static int hash(final Object... objects) {
    return Arrays.deepHashCode(objects);
}
Источник

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

Источник

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

Источник

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

Источник

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

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.

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

Источник

Любой метод хеширования, который равномерно распределяет значение хеша по возможному диапазону, является хорошей реализацией. См. Действующий Java там для реализации хэш-кода (пункт 9, я думаю...).

Источник

Вот еще одна демонстрация подхода 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());
    }

}
Источник

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

Источник

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

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

Это делает довольно хорошую работу по обеспечению равномерного распределения. Для некоторого обсуждения того, как эта формула работает, см. Сообщение Stackru: Магическое число в 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() должен возвращать разные значения.

Источник
Другие вопросы по тегам