Чому важливо, щоб хеш-функція була швидкою?

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

#Якщо функція повільна, страждає все

1. При кожному зверненні до таблиці потрібно обчислити хеш, а отже, навіть доступ "за O(1)" перетворюється на тривалий процес.
2. Хеш-таблиця перестає бути ефективною: її перевага - швидкість, і саме вона втрачається.
3. При великому обсязі даних (мільйони ключів) навіть зайві мікросекунди на обчислення хешу дають величезні затримки.

#Мета

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

#Висновок

Швидка хеш-функція - це основа продуктивності хеш-таблиці. Якщо вона повільна, хеш-таблиця втрачає сенс - простіше було б використовувати звичайний список або дерево.