@Pantene742

Hash талица это асоциативный массив индексов и адрессов в памяти?

Изучаю алгоритмы и никак не могу понять как работают Хеш таблицы.

Есть некие данные расбросанны в памяти с определенными адресами.... и асоциативный массив где хранятся индексы полученные хеш функцией и закрепленные за ними адреса в памяти. Так как же тогда производительность Хеш таблиц в книгах и уроках описывается как O(1) если нам для получения адреса в памяти при том что индексы(ключи) отсортированны нужно применить бинарный поиск кпримеру. log2 от длины массива...
  • Вопрос задан
  • 239 просмотров
Решения вопроса 2
EreminD
@EreminD
Кое-что умею
Хэш-функция определяет индекс в массиве.
Обращение к элементу по индексу происходит за О(1)

Вы передаете ключ-значение на запись "key1" -> "value1"
Хэш от "key1" выдал на значение 12. Вот в массив, в элемент с индексом 12 записывается значение/ссылка на "value1"
Запрашиваем из мэпы значение для "key1" - вычисляется хэш от "key1" (получили 12), вычитали из массива элемент 12 - получили значение
Ответ написан
@Mercury13
Программист на «си с крестами» и не только
Производительность хэш-таблиц — O(1) в среднем. Усреднённое по всем возможным наборам данных, если хэш-функция хорошо перемешивает.

Хэш-таблица действует так. Допустим, у нас выпало значение хэш-функции 1234 и у нас в хэш-таблице 100 гнёзд. Тогда наш элемент где-то в гнезде 34. Когда расширим таблицу до 200 гнёзд, элемент останется в гнезде 34, а когда расширим до 1000 — он переедет в гнездо 234.

Как разрешаются коллизии (два элемента в одном гнезде) — зависит от реализации: например, в гнезде могут быть связанные списки элементов.

Для словарей, если тот строится раз и до конца своей (не)долгой жизни, можно применить и другой способ, совершенно неубиенный и дешёвый по памяти. Взять массив, построить и отсортировать. Бинарный поиск — O(log n).
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы