2.9 KiB
2.9 KiB
#структура_данных #алгоритмы
Хеш-функция отображает строки на числа.
Требования
- Хеш-функция неизменно связывает название с одним индексом . Каждый раз, когда она вызывается для строки «авокадо», вы получаете обратно одно и то же число.
- Хеш-функция связывает разные строки с разными индексами. «Авокадо» связывается с индексом 4, а «молоко» с индексом О. Для каждой строки находится отдельная позиция массива,
- Хеш-функция знает размер массива и возвращает только действительные индексы. Таким образом, если длина массива равна 5 элементам, хеш-функция не вернет 100, потому что это значение не является действительным индексом в массиве.
Коллизия - ситуация, когда двум ключам назначается один элемент массива. Стратегия обработки коллизий - если несколько ключей отображаются на один элемент, в этом элементе создается связанный список.
Выводы:
- выбор хеш-функции действительно важен. Хеш-функция, отображающая все ключи на один элемент массива, никуда не годится. В идеале хеш-функция должна распределять ключи равномерно по всему хешу;
- если связанные списки становятся слишком длинными, работа с хеш- таблицей сильно замедляется. Но они не станут слишком длинными при использовании хорошей хеш-функции!
Для предотвращения коллизий необходимы :
- низкий коэффициент заполнения
- хорошая хеш-функция
Хорошая хеш-функция должна обеспечивать равномерное распределение
значений в массиве.
!
Плохая хеш-функция создает скопления и порождает множество коллизий.
!
Ссылки:
Источники: