Чому ідеальна хеш-функція на практиці неможлива?

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

На практиці це неможливо, тому що:

1. Ключів нескінченно багато, а комірок обмежена кількість.

• Таблиця має скінченний розмір N, а кількість можливих вхідних даних (рядки, числа, об'єкти) - практично нескінченна.
• Отже, різні ключі неминуче потраплятимуть в одну й ту саму комірку.

2. Хеш-функція - компроміс між швидкістю і рівномірністю.

• Щоб бути швидкою, вона має працювати просто (арифметичні операції, бітові зсуви).
• Але простота робить неможливим абсолютно рівномірний розподіл.

3. Дані непередбачувані.

• Неможливо заздалегідь знати, які саме ключі будуть використовуватися, а отже, неможливо побудувати універсальну "ідеальну" функцію.

4. Будь-яке обмеження діапазону (через % N) створює перетини.

• Навіть якщо хеші унікальні в 64-бітному просторі, при приведенні до діапазону таблиці (наприклад, 0-999) колізії все одно з'являться.

#Висновок

Ідеальна хеш-функція існує лише для заздалегідь відомого і фіксованого набору ключів. Для всіх інших випадків доводиться використовувати наближення: функції, які мінімізують колізії, але не можуть усунути їх повністю.