#структура_данных #алгоритмы 

> Хеш-функция отображает строки на числа.

### Требования
- Хеш-функция неизменно связывает название с одним индексом . Каждый
раз, когда она вызывается для строки «авокадо», вы получаете обратно
одно и то же число.
- Хеш-функция связывает разные строки с разными индексами. «Авокадо»
связывается с индексом 4, а «молоко» с индексом О. Для каждой строки находится отдельная позиция массива,
- Хеш-функция знает размер массива и возвращает только действительные
индексы. Таким образом, если длина массива равна 5 элементам,
хеш-функция не вернет 100, потому что это значение не является действительным индексом в массиве.


Коллизия - ситуация, когда двум ключам назначается один элемент массива.
Стратегия обработки коллизий - если несколько ключей отображаются на один элемент, в этом элементе создается связанный список.


Выводы:
- выбор хеш-функции действительно важен. Хеш-функция, отображающая
все ключи на один элемент массива, никуда не годится. В идеале
хеш-функция должна распределять ключи равномерно по всему хешу;
- если связанные списки становятся слишком длинными, работа с хеш-
таблицей сильно замедляется. Но они не станут слишком длинными при
использовании хорошей хеш-функции!

Для предотвращения коллизий необходимы :
- низкий коэффициент заполнения
- хорошая хеш-функция

Хорошая хеш-функция должна обеспечивать равномерное распределение
значений в массиве.
![[Pasted image 20250110091724.png]]
Плохая хеш-функция создает скопления и порождает множество коллизий.
![[Pasted image 20250110091731.png]]

Ссылки:
- [[Хеш-таблица (Hash-table)]]
- [[Массив (Array)]]

Источники:
- [[Адитья Бхаргава - Грокаем Алгоритмы]]