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

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

 Diablo17 мар. 2016 г., 12:45
с Java 7+, наверноеObjects.hashCode(collection) должно быть идеальным решением!
 cbreezier19 апр. 2016 г., 07:35
@Diablo Я не думаю, что это вообще отвечает на вопрос - этот метод просто возвращаетcollection.hashCode() (hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/…)

Ответы на вопрос(20)

Любой метод хеширования, который равномерно распределяет значение хеша по возможному диапазону, является хорошей реализацией. См эффективный 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 = результат ), есть хороший совет для реализации хэш-кода (пункт 9, я думаю ...).

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

 03 июн. 2016 г., 21:04
Хорошие комментарии, но будьте осторожны с использованием термина «разные объекты»; ... потому что equals () и, следовательно, реализация hashCode () не обязательно относятся к разным объектам в контексте ОО, но обычно больше относятся к их представлениям модели предметной области (например, два человека могут считаться одинаковыми, если они совместно используют код страны и ID страны - хотя это могут быть два разных «объекта» в JVM - они считаются «равными» и имеют заданный hashCode) ...
 15 сент. 2015 г., 13:55
Это должен быть просто комментарий к вышеупомянутому посту Грею. Хорошая информация, но она на самом деле не отвечает на вопрос
 29 апр. 2013 г., 10:45
Если(A != B) and (A.hashcode() == B.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, это уродливо.)

 22 сент. 2008 г., 09:25
Я дважды посмотрел на вопрос, но не нашел там ошибки ...
 22 сент. 2008 г., 19:40
Так что это мета-обсуждение и вообще не имеет отношения к вопросу? ;-)
 23 сент. 2008 г., 00:13
Это исправление предложенного ответа, которое имеет довольно существенный недостаток.
 15 сент. 2015 г., 13:58
Это очень ограниченная реализация
 22 сент. 2008 г., 15:53
ошибка в длинном ответе about8.blogspot.com - получение хеш-кода из конкатенации строк оставляет вас с хеш-функцией, одинаковой для любой комбинации строк, которые складываются в одну и ту же строку.

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

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

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

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

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

 04 февр. 2012 г., 02:31
Если вы собираетесь использовать это, имейте в виду, что отражение стоит дорого. Честно говоря, я бы не использовал это ни для чего, кроме выбрасывания кода.

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

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, есть небольшое преимущество в скорости.

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

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

 27 янв. 2014 г., 22:05
+1 Согласен с Quantum7, но я бы сказал, что очень хорошо понимать, что делает реализация, сгенерированная Eclipse, и откуда она получает подробности своей реализации.
 03 июн. 2016 г., 20:59
Извините, но ответы, связанные с "функциональностью, предоставленной [некоторыми IDE]" не очень актуальны в контексте языка программирования в целом. Существуют десятки IDE, и это не отвечает на вопрос ... а именно потому, что это больше касается алгоритмического определения и напрямую связано с реализацией equals () - о чем IDE ничего не будет знать.
 07 апр. 2011 г., 02:31
+1 Хорошее практическое решение. Решение dmeister более полное, но я склонен забывать обрабатывать пустые значения, когда пытаюсь написать хеш-коды самостоятельно.

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

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

 10 дек. 2017 г., 20:25
@ KrzysztofJab & # x142; o & # x144; Ski Right. Кроме того, обменfoo а такжеbar производит ненужное столкновение тоже.
 30 апр. 2013 г., 08:34
Вроде SquareCog уже заметили. Если хеш-код генерируется один раз из конкатенации двух строк, чрезвычайно легко генерировать массу коллизий:("abc"+""=="ab"+"c"=="a"+"bc"==""+"abc"), Это серьезный недостаток. Было бы лучше оценить хеш-код для обоих полей, а затем рассчитать их линейную комбинацию (предпочтительно с использованием простых чисел в качестве коэффициентов).
Решение Вопроса

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

Практически во всех случаях разумная хорошая реализация была предложена вJosh Bloch& APOS; sEffective Java в пункте 8 (второе издание). Лучше всего искать это там, потому что автор объясняет, почему подход хорош.

A short version

Create a int result and assign a non-zero value.

For every field f tested in the equals() method, calculate a hash code c by:

If the field f is a boolean: calculate (f ? 0 : 1); If the field f is a byte, char, short or int: calculate (int)f; If the field f is a long: calculate (int)(f ^ (f >>> 32)); If the field f is a float: calculate Float.floatToIntBits(f); If the field f is a double: calculate Double.doubleToLongBits(f) and handle the return value like every long value; If the field f is an object: Use the result of the hashCode() method or 0 if f == null; If the field f is an array: see every field as separate element and calculate the hash value in a recursive fashion and combine the values as described next.

Combine the hash value c with result:

result = 37 * result + c

Return result

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

 15 февр. 2013 г., 15:08
@ SimonAndr & # xE9; Форсберг Ну, вычисляемый хеш-код не всегда может быть уникальным :) Это хеш-код. Однако у меня возникла идея: простое число имеет только один множитель, в то время как не простое имеет как минимум два. Это создает дополнительную комбинацию для оператора умножения, чтобы привести к тому же хешу, то есть вызвать коллизию.
 15 февр. 2013 г., 14:58
@dma_k Причина использования простых чисел и метода, описанного в этом ответе, заключается в том, чтобы гарантировать, чтоcomputed hashcode will be unique, При использовании не простых чисел вы не можете гарантировать это. Неважно, какое простое число вы выберете, в числе 37 нет ничего волшебного (очень жаль, что 42 не является простым числом, а?)
 22 сент. 2008 г., 19:25
Да, мне особенно любопытно, откуда пришло число 37.
 04 окт. 2010 г., 16:39
Я использовал пункт 8 «Эффективной Java» Джоша Блоха. книга.
 23 сент. 2008 г., 01:55
Я не знаю ни одного доказательства. Число 37 произвольно, но оно должно быть простым. Зачем? Я не совсем уверен, но это имеет отношение к модулю артрита и свойствам простых чисел, которые приводят к распределению го.

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

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

synchronization (does the algo support concurrent access or not) ? fail safe iteration (does the algo detect a collection which changes during iteration) null value (does the hash code support null value in the collection)
 11 сент. 2012 г., 10:20
странно, что такие важные аспекты не были одобрены.

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

}

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

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

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

@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));
}
 18 июл. 2017 г., 11:14
Документация Android теперь не включает в себя вышеуказанный код, так что здесь есть кэшированная версия изWayback Machine - Android Documentation (Feb 07, 2015)
 04 апр. 2018 г., 16:31
идеальный фрагмент кода

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

 11 мар. 2014 г., 01:06
@ justin.hughey ты, кажется, запутался. Единственный случай, который вы должны переопределитьhashCode если у вас есть обычайequalsи это именно то, для чего предназначены эти библиотечные методы. В документации совершенно ясно об их поведении по отношению кequals, Реализация библиотеки не претендует на то, чтобы освободить вас от знания, какие характеристики правильногоhashCode реализация есть - эти библиотеки делают этоeasier для вас, чтобы реализовать такую соответствующую реализацию для большинства случаев, когдаequals переопределяется
 04 нояб. 2015 г., 20:00
Лучший ответ IMO, хотя в качестве примера я бы предпочел JDK7java.util.Objects.hash(...) метод, чем гуаваcom.google.common.base.Objects.hashCode(...) метод. Я думаю, что большинство людей предпочли бы стандартную библиотеку за дополнительную зависимость.
 28 янв. 2014 г., 14:23
Если у кого-то нет веских причин не использовать их, в любом случае следует обязательно их использовать. (Формулировка более сильная, как это ИМХО должна быть сформулирована.) Применяются типичные аргументы для использования стандартных реализаций / библиотек (лучшие практики, хорошо протестированные, менее подверженные ошибкам и т. Д.).
 21 дек. 2015 г., 12:48
Если есть два или более аргументов и если какой-либо из них является массивом, результат может быть не тем, что вы ожидаете, потому чтоhashCode() для массива это просто егоjava.lang.System.identityHashCode(...).
 05 февр. 2015 г., 06:30
Для всех разработчиков Android, которые смотрят на класс java.util.Objects, он был представлен только в API 19, поэтому убедитесь, что вы работаете на KitKat или выше, в противном случае вы получите NoClassDefFoundError.

Хорошая реализацияEffective Java& APOS; shashcode() а такжеequals() логика вApache Commons Lang, Проверять, выписыватьсяHashCodeBuilder а такжеEqualsBuilder.

 17 мар. 2016 г., 12:26
до недавнего времени это был мой любимый подход. Я столкнулся с StackOverFlowError при использовании критериев для ассоциации SharedKey OneToOne. Более того,Objects класс обеспечиваетhash(Object ..args) & Амп;equals() методы из Java7 на. Они рекомендуются для любых приложений, использующих jdk 1.7+
 04 февр. 2012 г., 02:35
Недостатком этого API является то, что вы платите стоимость создания объекта каждый раз, когда вызываете метод equals и hashcode (если только ваш объект не является неизменяемым и вы предварительно вычисляете хеш), что может быть много в некоторых случаях.
 10 дек. 2017 г., 20:12
@Diablo Я думаю, ваша проблема заключалась в цикле в графе объектов, и вам не повезло с большинством реализаций, так как вам нужно игнорировать некоторые ссылки или прерывать цикл (IdentityHashMap). FWIW Я использую хэш-код на основе идентификатора и равняется для всех сущностей.

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

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

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

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

 10 окт. 2017 г., 21:52
Это вопрос о Java, а не о C ++.

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

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

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

Ваш ответ на вопрос