Почему (без столкновений) хеш-таблица поиска действительно O (1)?

Отказ от ответственности: я знаю, что есть похожие вопросы уже здесь и на Stackoverflow. Но они все о столкновениях, о которых я не прошу.

Мой вопрос: почему столкновительный меньше LookUp O(1)в первую очередь?

Давайте предположим, что у меня есть эта хеш-таблица:

Hash  Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6

Теперь я ищу ключ, kкоторый h(k)дает хэш-функция h(k) = mkwer. Но как поиск "узнает", что хеш mkwerнаходится в позиции 5? Почему не нужно пролистывать все клавиши, O(n)чтобы найти его? Хеши не могут быть какими-то реальными аппаратными адресами, потому что я потерял бы способность перемещать данные. И, насколько я знаю, хеш-таблица не сортируется по хешам (даже если бы это было, поиск также занял бы O(log n))?

Как знание хеша помогает найти правильное место в таблице?

complexity-theory hash hash-tables performance Фу Бар
источник

Ответы:

Хеш-функция не возвращает какую-либо строку, такую как mkwer. Он напрямую возвращает позицию элемента в массиве. Если, например, ваша хеш-таблица содержит десять записей, хеш-функция вернет целое число в диапазоне 0–9.

Дэвид Ричерби
источник

Спасибо. :) Моя ошибка была в том, что я думал о хэш-функции, такой как MD5 или SHA. Но хеш, конечно, может быть целочисленной позицией, о которой я не думал. Теперь, когда я знаю, что искать, я даже быстро нашел хороший пример: хеш-функция PHP: github.com/php/php-src/blob/PHP-5.6.10/Zend/zend_hash.h#L237

Foo Бар

@FooBar: MD5 и SHA также вычисляют отдельные числа из входных данных, просто так часто говорят о хешах в шестнадцатеричной форме. Так же, как адреса памяти редко считаются десятичными.

nperson325681

Кроме того, MD5 и т. Д. Слишком длинные, чтобы их можно было использовать в качестве индекса массива напрямую. Можно было бы использовать некоторую часть хеша, например младшие n битов.

Чирлу

Хеш-функция вычисляет позицию массива по заданной строке . Если это идеальный хеш, это означает, что коллизий точно не будет, наиболее вероятный массив, по крайней мере, в два раза больше, чем количество элементов.

Например, я дам очень плохой хэш для букв, просто чтобы проиллюстрировать механизм:
0) 1) для каждого символа в строке принять значение ascii, вычесть 'a', если это строчные буквы, вычесть 'A', если прописные, добавить значение к x. 2) результирующее число, например 15 - индекс массива. $x = 0;$
$x = x mod 52$

Этот очень простой хеш (ограниченный и склонный к коллизиям) отличается от других хешей механизмом хеширования, не учитывает данный ввод. В более продвинутой схеме хэш - это большее число, настроенное на количество элементов. Идеальный хеш генерируется для всех входных данных, чтобы гарантировать отсутствие коллизий.

Это потому что вычисление хеша из строки зависит от того, насколько сложна вычисляемая функция, но не зависит от количества элементов. $O(1)$

В случае идеального хэша, когда добавляются элементы, пересчитывается, более простой случай с коллизиями, когда нагрузка на массив велика, размер массива увеличивается, функция принимает больший модуль вывода, а элементы перемещаются на новые места. $h(k)$

Массив - это непрерывный фрагмент памяти, чтобы получить элемент, вы берете адрес первого элемента (начало массива), а затем добавляете к этому адресу чтобы у вас была явная ячейка памяти. $n-th$ $n * (size of element)$

Злой
источник

И как поиск узнает, где в таблице находится хеш? Это ни заказанные, ни аппаратные адреса.

Foo Bar

Вы задаете некоторую строку, например, "xcnvb", так что вычисленный хеш дает индекс массива, "xcnvb" - ваш элемент для поиска, 8 - индекс в таблице. Он упорядочен, хэш возвращает место для получения элемента. Этот элемент был помещен туда той же самой функцией. Аппаратные средства тут не при чем. Вы предоставляете массив, хэш-функцию и вычисляете хеш, чтобы получить индекс в массиве, то же самое при получении. Массив не отсортирован, и он никогда не бывает полным.

h (" x c n v b ") = 8

$h("xcnvb") = 8$

Зло

Но не каждый индекс будет заполнен. Если у меня есть хэши 1, 4, 8, 90 и 223, заполненные данными, как поиск найдет правильное место? В этом случае индекс «90» находится на позиции 4, потому что большинство других индексов не существует. И пустой хеш-таблица не имеет бесконечного размера и имеет все возможные позиции !?

Foo Bar

Да, массив позволяет нам предполагать 512 элементов длиной, 9 битов, используемых для хэш-функции, и у вас есть только 4 элемента. Индекс 90 имеет позицию 90 в массиве, как в примере - почти все ячейки пусты. Если ваш массив вы индексируете его = ваши данные для "xcnvb"

H a

$Ha$

H a (h (" x c n v b ")) = H a [90]

$Ha(h("xcnvb")) = Ha[90]$

Evil

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

Кристофер Шульц

Чтобы расширить ответ Дэвида Ричерби, термин « хэш-функция » немного перегружен. Часто, когда мы говорим о хэш-функции, мы думаем о MD5, SHA-1 или о чем-то вроде .hashCode()метода Java , который превращает некоторый ввод в одно число. Однако домен этого числа (т. Е. Является максимальным значением) вряд ли будет иметь тот же размер, что и хеш-таблица, в которой вы пытаетесь сохранить данные. (MD5 составляет 16 байт, SHA-1 составляет 20 байт и .hashCode()представляет собой int- 4 байт).

Итак, ваш вопрос касается следующего шага - когда у нас есть хеш-функция, которая может отображать произвольные входные данные в числа, как мы можем поместить их в структуру данных определенного размера? С другой функцией, также называемой «хэш-функцией»!

Тривиальный пример такой функции - по модулю ; Вы можете легко сопоставить число произвольного размера с определенным индексом в массиве по модулю. Это вводится в CLRS как «метод деления»:

В методе деления для создания хеш-функций мы отображаем ключ в один из слотов, беря остаток от деленный на . То есть хеш-функция $k$ $m$ $k$ $m$

$h(k) = k$ mod . $m$

...

При использовании метода деления мы обычно избегаем определенных значений . Например, не должно быть степенью 2, так как если то - это просто младших битов . $m$ $m$ $m = 2^p$ $h(k)$ $p$ $k$

~ Введение в алгоритмы, §11.3.1 - CLRS

Таким образом, модуль не является отличной хеш-функцией, поскольку ограничивает размеры, которые мы можем безопасно использовать для нашей базовой структуры данных. В следующем разделе представлен чуть более сложный «метод умножения», который также использует модуль по модулю, но имеет преимущество, поскольку «значение не является критическим». Однако он лучше всего работает с некоторыми предварительными знаниями о «характеристиках хешируемых данных» - то, чего мы часто не знаем. $m$

Java HashMapиспользует модифицированную версию метода деления, которая выполняет этап предварительной обработки для учета слабых .hashCode()реализаций, чтобы он мог использовать массивы степени двойки. Вы можете точно увидеть, что происходит в .getEntry()методе (мои комментарии):

 // hash() transforms key.hashCode() to protect against bad hash functions
 int hash = (key == null) ? 0 : hash(key.hashCode());
 // indexOf() converts the resulting hash to a value between 0 and table.length-1
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
     ...

_{Java 8 принесла переписывание, HashMapкоторое еще быстрее, но немного сложнее для чтения. Однако он использует тот же общий принцип для поиска по индексу.}

dimo414
источник