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

Question

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

Answer 1

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

Answer 2

@ 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, это ужасно.)

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

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.

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

Answer 7

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

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

Answer 8

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

}

Answer 9

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

Answer 10

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

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

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

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