Уникальность hashCode

Ответ 1

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

Использование адреса памяти - это просто способ получить небольшое случайное число. Источник Sun JDK имеет переключатель, позволяющий использовать защищенный генератор случайных чисел или константу. Я полагаю, что IBM (используется?) Использует быстрый генератор случайных чисел, но он не был абсолютно безопасным. Упоминание в документах адреса памяти имеет исторический характер (около десяти лет назад было необычно иметь дескрипторы объектов с фиксированными местоположениями).

Вот код, который я написал несколько лет назад, чтобы продемонстрировать столкновения:

class HashClash {
    public static void main(String[] args) {
        final Object obj = new Object();
        final int target = obj.hashCode();
        Object clash;
        long ct = 0;
        do {
            clash = new Object();
            ++ct;
        } while (clash.hashCode() != target && ct<10L*1000*1000*1000L);
        if (clash.hashCode() == target) {
            System.out.println(ct+": "+obj+" - "+clash);
        } else {
            System.out.println("No clashes found");
        }
    }
}

RFE, чтобы уточнить документы, потому что это происходит слишком часто: CR 6321873

Ответ 2

Я думаю, что docs для метода hashCode объекта сообщает ответ.

"Насколько это разумно практично, метод hashCode, определенный классом Объект возвращает разные целые числа для отдельных объектов. (Это обычно реализуется путем преобразования внутренний адрес объекта в целое число, но это техника реализации не требуемый программным обеспечением JavaTM язык)."

Ответ 3

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

Sun JVM либо основывает хэш-код Object на устойчивом дескрипторе объекта, либо кэширует исходный хэш-код. Уплотнение во время GC не изменит hashCode(). Все сломается, если это произойдет.

Ответ 4

Возможно ли это?

Да.

Случается ли это с любой разумной частотой?

Нет.

Ответ 5

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

Таким образом, им не нужно быть действительно уникальными - они должны быть достаточно уникальными, чтобы не генерировать много столкновений (что сделает реализацию HashMap неэффективной).

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

Также см. ответ Кена о равенстве, требующем идентичные хэш-коды.

Ответ 6

Вы говорите о фактическом классе Object или объектах вообще? Вы используете оба вопроса. (И в реальных приложениях обычно не создается много экземпляров Object)

Для объектов вообще обычно писать класс, для которого вы хотите переопределить equals(); и если вы это сделаете, вы также должны переопределить hashCode(), чтобы два разных экземпляра этого класса, "равных", также должны иметь один и тот же хэш-код. В этом случае вы, вероятно, получите "повторяющийся" хеш-код, среди экземпляров одного и того же класса.

Кроме того, при реализации hashCode() в разных классах они часто основаны на чем-то в объекте, поэтому вы получаете меньше "случайных" значений, что приводит к "повторяющимся" хэш-кодам среди экземпляров разных классов (или не те объекты "равны" ).

В любом реальном приложении нет ничего необычного в том, чтобы находить разные объекты с одним и тем же хэш-кодом.

Ответ 7

Если было столько хэш-кодов, сколько адресов памяти, тогда для хранения самого хэша потребовалась бы вся память.: -)

Итак, да, хэш-коды иногда должны совпадать.