43 lines
2.9 KiB
Markdown
43 lines
2.9 KiB
Markdown
#структура_данных #алгоритмы
|
||
|
||
> Хеш-функция отображает строки на числа.
|
||
|
||
### Требования
|
||
- Хеш-функция неизменно связывает название с одним индексом . Каждый
|
||
раз, когда она вызывается для строки «авокадо», вы получаете обратно
|
||
одно и то же число.
|
||
- Хеш-функция связывает разные строки с разными индексами. «Авокадо»
|
||
связывается с индексом 4, а «молоко» с индексом О. Для каждой строки находится отдельная позиция массива,
|
||
- Хеш-функция знает размер массива и возвращает только действительные
|
||
индексы. Таким образом, если длина массива равна 5 элементам,
|
||
хеш-функция не вернет 100, потому что это значение не является действительным индексом в массиве.
|
||
|
||
|
||
Коллизия - ситуация, когда двум ключам назначается один элемент массива.
|
||
Стратегия обработки коллизий - если несколько ключей отображаются на один элемент, в этом элементе создается связанный список.
|
||
|
||
|
||
Выводы:
|
||
- выбор хеш-функции действительно важен. Хеш-функция, отображающая
|
||
все ключи на один элемент массива, никуда не годится. В идеале
|
||
хеш-функция должна распределять ключи равномерно по всему хешу;
|
||
- если связанные списки становятся слишком длинными, работа с хеш-
|
||
таблицей сильно замедляется. Но они не станут слишком длинными при
|
||
использовании хорошей хеш-функции!
|
||
|
||
Для предотвращения коллизий необходимы :
|
||
- низкий коэффициент заполнения
|
||
- хорошая хеш-функция
|
||
|
||
Хорошая хеш-функция должна обеспечивать равномерное распределение
|
||
значений в массиве.
|
||
![[Pasted image 20250110091724.png]]
|
||
Плохая хеш-функция создает скопления и порождает множество коллизий.
|
||
![[Pasted image 20250110091731.png]]
|
||
|
||
Ссылки:
|
||
- [[Хеш-таблица (Hash-table)]]
|
||
- [[Массив (Array)]]
|
||
|
||
Источники:
|
||
- [[Адитья Бхаргава - Грокаем Алгоритмы]] |