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

StackOverflow https://stackoverflow.com/questions/113511

  •  02-07-2019
  •  | 
  •  

Вопрос

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

Это было полезно?

Решение

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

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

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

Другие советы

Если вас устраивает эффективная реализация 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), но работает так же.

Лучше использовать функциональные возможности 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, вот хорошая ссылка из моего Гитхаба...

@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));
}

Сначала убедитесь, что равенство реализовано правильно.От статья 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, вы сказали

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

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

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

но

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

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

Источник -> Создать хеш-код() и равенство().

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

Есть хорошая реализация Эффективная Java's hashcode() и equals() логика в Язык Apache Commons.Проверить HashCodeBuilder и Равностроитель.

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

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

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

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

Если ваш класс коллекции расширяет AbstractList, вам не нужно об этом беспокоиться: уже существует реализация методаquals() и 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;
   }

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

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 Равностроитель и HashCodeBuilder.

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

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

Я использую крошечную обертку вокруг 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.

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

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

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

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

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

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

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():если методquals() возвращает true для двух объектов, то hashCode() должен возвращать одно и то же значение.Если методquals() возвращает false, то hashCode() должен возвращать другие значения.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top