Как доказать, что Object.hashCode() может создавать аналогичный хеш-код для двух разных объектов в Java?

Обсуждалось с интервьюером относительно внутренней реализации Java Hashmaps и того, как оно будет выглядеть, если мы переопределим equals(), но не метод HashCode() для объекта Employee.

Он сказал мне, что hashCode для двух разных объектов никогда не будет одинаковым для реализации object.hashCode() по умолчанию, если мы не переопределим hashCode().

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

Из того, что я вспомнил, я сказал ему, что контракты Java Hashcode говорят, что два разных объекта могут иметь один и тот же hashcode().

По словам моего интервьюера, объект object.hashcode() по умолчанию никогда не имеет одного и того же hashcode() для двух разных объектов. Это правда?

Можно ли даже удаленно написать код, демонстрирующий это. Из того, что я понимаю, Object.hashcode() может генерировать 2 ^ 30 уникальных значений, как возникает конфликт, с такой низкой вероятностью столкновения, чтобы продемонстрировать, что два разных объекта могут получить один и тот же hashcode() с помощью метода классов объектов.

Или он прав, с реализацией Object.HashCode() по умолчанию, у нас никогда не будет столкновения. Два разных объекта никогда не могут иметь один и тот же HashCode. Если да, то почему многие руководства Java явно не говорят об этом.

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

Ответы

Ответ 1

2 ^ 30 уникальные значения звучат как много, но проблема дня рождения означает, что нам не нужно много объектов, чтобы получить столкновение.

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

Как вы можете видеть из реализации класса Hashable, каждый из них гарантированно является уникальным, и все же есть еще столкновения.

class HashCollider
{
    static class Hashable
    {
        private static int curr_id = 0;
        public  final  int id;

        Hashable()
        {
            id = curr_id++;
        }
    }

    public static void main(String[] args)
    {
        final int NUM_OBJS = 200000; // birthday problem suggests
                                     // this will be plenty

        Hashable objs[] = new Hashable[NUM_OBJS];  
        for (int i = 0; i < NUM_OBJS; ++i) objs[i] = new Hashable();

        for (int i = 0; i < NUM_OBJS; ++i)
        {
            for (int j = i + 1; j < NUM_OBJS; ++j)
            {
                if (objs[i].hashCode() == objs[j].hashCode())
                {
                    System.out.println("Objects with IDs " + objs[i].id
                                     + " and " + objs[j].id + " collided.");
                    System.exit(0);
                }
            }
        }

        System.out.println("No collision");
    }
}

Ответ 2

Если у вас достаточно большая куча (при условии 64-битного адресного пространства), и объекты достаточно малы (наименьший размер объекта на 64-битной JVM составляет 8 байтов), тогда вы сможете представить более 2 ^ 32 объектов которые достижимы одновременно. В этот момент хэш-коды идентификаторов объектов не могут быть уникальными.

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

  • Алгоритм по умолчанию для hashcode в более старых версиях Java основан на адресе объекта при первом вызове hashcode. Если сборщик мусора перемещает объект, а другой создается на исходном адресе первого, и вызывается идентификаторHashCode, то два объекта будут иметь один и тот же идентификатор хэш-кода.

  • В текущем (Java 8) алгоритме по умолчанию используется PRNG. Формула "день рождения парадокса" скажет вам, что один идентификатор объекта hashcode совпадает с другим.

Опция -XXhashCode=n, упомянутая @BastianJ, имеет следующее поведение:

  • hashCode == 0: возвращает только что созданное псевдослучайное число

  • hashCode == 1: XOR - адрес объекта с псевдослучайным числом, которое иногда изменяется.

  • hashCode == 2: hashCode равен 1! (Отсюда @BastianJ "чит" ответ.)

  • hashCode == 3: Хэш-код является восходящим порядковым номером.

  • hashCode == 4: нижние 32 бита адреса объекта

  • hashCode >= 5: Это алгоритм по умолчанию для Java 8. Он использует PRNG xor-shift Marsaglia с конкретным потоком семян.

Если вы загрузили исходный код OpenJDK Java 8, вы найдете реализацию в hotspot/src/share/vm/runtime/synchronizer.cp. Найдите метод get_next_hash().

Так что это еще один способ доказать это. Покажите ему исходный код!

Ответ 3

Используйте Oracle JVM и установите -XX: hashCode = 2. Если я правильно помню, это выбирает реализацию по умолчанию "constant 1". Просто для того, чтобы доказать, что вы правы.

Ответ 4

Мне нечего добавить в Майкл ответить (+1), за исключением некоторого кода игры в гольф и статистики.

Статья Википедии о проблема с днем ​​рождения, с которой связан Майкл, имеет nice table количества событий, необходимых для получения столкновения, с желаемой вероятностью, с учетом пространства значений определенного размера. Например, Java hashCode имеет 32 бита, что дает значение в 4 миллиарда. Чтобы получить вероятность столкновения с вероятностью 50%, необходимо около 77 000 событий.

Вот простой способ найти два экземпляра Object, которые имеют одинаковый hashCode:

static int findCollision() {
    Map<Integer,Object> map = new HashMap<>();
    Object n, o;

    do {
        n = new Object();
        o = map.put(n.hashCode(), n);
    } while (o == null);

    assert n != o && n.hashCode() == o.hashCode();
    return map.size() + 1;
}

Это возвращает количество попыток, необходимых для получения столкновения. Я запускал это несколько раз и генерировал некоторую статистику:

    System.out.println(
        IntStream.generate(HashCollisions::findCollision)
                 .limit(1000)
                 .summaryStatistics());

IntSummaryStatistics{count=1000, sum=59023718, min=635, average=59023.718000, max=167347}

Это похоже на цифры из таблицы Википедии. Кстати, это заняло всего около 10 секунд, чтобы работать на моем ноутбуке, так что это далеко не патологический случай.

Вы были правы в первую очередь, но это повторяется: хэш-коды не уникальны!