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

Question

[Pantene742]

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

Есть некие данные расбросанны в памяти с определенными адресами.... и асоциативный массив где хранятся индексы полученные хеш функцией и закрепленные за ними адреса в памяти. Так как же тогда производительность Хеш таблиц в книгах и уроках описывается как O(1) если нам для получения адреса в памяти при том что индексы(ключи) отсортированны нужно применить бинарный поиск кпримеру. log2 от длины массива...

Answer 1

[Дмитрий Еремин]

Хэш-функция определяет индекс в массиве.
Обращение к элементу по индексу происходит за О(1)

Вы передаете ключ-значение на запись "key1" -> "value1"
Хэш от "key1" выдал на значение 12. Вот в массив, в элемент с индексом 12 записывается значение/ссылка на "value1"
Запрашиваем из мэпы значение для "key1" - вычисляется хэш от "key1" (получили 12), вычитали из массива элемент 12 - получили значение

Comments

[Pantene742]

Ну да !!! но для этого нам надо теперь получить адресс елемента в памяти... мы идем в массив индексов перебераем их находим нужный и тогда получаем адресс в памяти который закреплен за индексом.... а если мы ищем нужный индекс можем не перебирать весь массив а сделать бинарный поиск (если массив ключей отсортирован) то тут уже log2 от N... но ни как не O(1)

[Pantene742]

Давай в контексте языка C..... так как наши интерпритаторы JS, Python даже компилятор Go написанный на C.
Я понимаю что в JS быстрая выборка по индексу.... Я не об этом...

[Дмитрий Еремин]

Pantene742, вот
Access в Array происходит за О(1). Поиск по массиву, это когда мы ищем значение элемента массива. Индексы известны заранее. Поэтому и обращение по индексу выполняется быстро

[Pantene742]

Давай даже так.... Индекс(название свойства в обьекте) это что то на подобие уже адреса в памяти в языке C....

[Дмитрий Еремин]

вот представь массив
|0|1|2|3|4| - индекс
|a|b|c|d|e| - значение элемента

Вот обращение по индексу за О(1)
Да, поиск по массиву за O(n) - мы перебираем значения и сравниваем

[Pantene742]

Дмитрий Еремин, Тогда получается Хеш функция генерирует адресс в памяти, а что сгенерированые адресса заняты ???

[Pantene742]

Дмитрий Еремин, это обращение индексу но не по адрессу в памяти

[Дмитрий Еремин]

Pantene742, в упрощенном понимании, да, хэш-функция решает, куда запишет и где потом искать значение

А если по текущему индексу уже есть значение? Коллизия. Это обычно прям следующая тема после темы хэш.

[Дмитрий Еремин]

Pantene742, угу. достали элемент из массива по индексу за О(1). Получили адрес в памяти. Обращение по адресу происходит за какую-то константу

[Pantene742]

Дмитрий Еремин, Я так понимаю что у нас вообще создается массив просто из адресов... когда получаем результат функции при поиске, мы находим начало массива умножаем адрресс на результат хеш функции и находим адресс памяти где хранится адресс нужных данных, при колизии если елемент не тот мы ищем его уже в цепочном массиве который лежит за первоначальным адрессом.

[Дмитрий Еремин]

Pantene742, да, один из способов рабоы с коллизией - связанный список

Answer 2

[Mercury13]

Производительность хэш-таблиц — O(1) в среднем. Усреднённое по всем возможным наборам данных, если хэш-функция хорошо перемешивает.

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

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

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

Comments

[Pantene742]

хеш таблица содержит адреса наших данных в памяти ? скорее всего эта таблица просто массив адресов в памяти основных данных. чтоб найти адресс в памяти по индексу надо прибавить в адрессу начала хеш таблицы умножения размера одной ячейки хеш таблицы на 34 или к примеру на 234 если размер таблицы 400... после умножения мы получаем адресс памяти где хранится адресс памяти на наши основные данные..
Я так понимаю что хеш таблица всегда в памяти неразрывно должна находится. если ей нет места при разростании она тупо вся переезжает в другой свободный участок, зато основные данные никуда не двигаются...

[Mercury13]

Pantene742,
Не важно. Могут быть просто данные (если они достаточно маленькие и тривиальные), указатели на что-то другое, голова связанного списка…
Хэш-таблица представляет собой индексный массив любого типа. Может быть как непрерывный, так и из массивчиков поменьше.