1

Как известно, ситуация, когда у разных объектов одинаковые хеш-коды называется — коллизией. Вероятность возникновения коллизии зависит от используемого алгоритма генерации хеш-кода.

Но вот вопрос, почему она возникает? Неужели тяжко придумать "защиту" от возникновения коллизии? Кто что думает?

4
  • 3
    Результат хеш-функции может быть короче ее аргумента. Коллизий избежать невозможно.
    – user239133
    30 окт 2017 в 22:11
  • Вообще, есть perfect hash function (идеальная хэш-функция)
    – zRrr
    31 окт 2017 в 0:33
  • Вероятность возникновения коллизии зависит от используемого алгоритма генерации хеш-кода. Нет. Если алгоритмы хэширования не содержат статистических, математических и прочих погрешностей, вероятность коллизии зависит только от длины формируемого хэша.
    – Akina
    31 окт 2017 в 5:01
  • Неужели тяжко придумать "защиту" от возникновения коллизии? Да элементарно. Просто длина хэша должна быть не меньше максимальной длины хэшируемых данных (с учётом пэддинга).
    – Akina
    31 окт 2017 в 5:02

1 ответ 1

17

Хеш код в java создается методом

  public int hashCode()

У integer диапазон от -2147483648 до 2147483647, т.е. округлив получаем 4 миллиарда разных целых чисел.

А теперь представим ситуацию, у вас 8-10 миллиардов объектов. Вопрос: как каждому из них дать уникальный хеш код используя диапазон в 4 миллиарда?

Ответ: никак.

При этом вы не знаете сколько объектов вашего класса могут создать пользователи.

Если ваш класс будет использоваться в Hash структурах как ключ, вы так же должны постараться обеспечить объекты такими хеш кодами, чтобы они попадали в разные корзины и получить равномерное заполнение структуры.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.