Поиск элементов в универсальной хэш-таблице?

Ответ 1

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

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

Позже, когда вы захотите найти (связанную с информацией информацию) конкретный ключ (в данном случае, человек), который вы вводите, и хеш-ключ, чтобы найти нужное место в хеш-таблице, чтобы искать эту информацию.

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

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

Это указывает на другой недостаток хеш-таблиц - вам обычно требуется точное совпадение с одной оригинальной записью, чтобы они хорошо работали. Например, рассмотрим некоторые запросы, основанные на моей фамилии. Предполагая, что вы проиндексированы по всей фамилии, было бы тривиально найти "Coffin" - но, по крайней мере, с большинством нормальных хеш-функций, поиск "чего-то, начиная с" Cof ", будет значительно медленнее, так как" найдет все имена между "Гроб" и "Демминг".

Как таковой, вы наполовину правильны - в то время как хеш-таблицы, как правило, очень быстрые для нескольких конкретных случаев (в первую очередь для поиска точного соответствия), общая идея, которую вы наметили (сканирование всей таблицы до найти данные) является почти единственным выбором, доступным для некоторых других целей, поэтому, если вы хотите поддерживать что-либо, кроме точных совпадений, может быть предпочтительной другая структура данных.

Это касается прежде всего наиболее типичных применений/типов хеш-таблиц. Возможно создание хеш-функций, которые по меньшей мере сгибают (если не нарушают) эти правила в разной степени. В большинстве случаев это связано с некоторыми компромиссами. Например, учитывая географическую информацию в качестве входных данных, вы можете создать хэш (из рода), просто усекая координаты (или, по крайней мере, один из них), чтобы получить ту же информацию с меньшей точностью. Это упорядочивает информацию по крайней мере до степени, поэтому близкие друг к другу объекты имеют сходные хеш-значения, что упрощает поиск соседних данных. Это, однако, часто приводит к большему количеству столкновений (например, вы получите много элементов хэширования для одного и того же значения для центра города большого города).

Глядя конкретно на универсальное хэширование, это добавляет еще один элемент в головоломку: вместо одной хэш-функции у вас есть семейство хеш-функций, из которых вы выбираете "случайно". Когда универсальное хеширование используется для реализации хеш-таблицы (что не всегда - оно также часто используется для таких вещей, как коды аутентификации сообщений), вы обычно не выбираете хэш-функцию случайным образом каждый раз, когда вы вставляете элемент. Скорее, вы обычно выбираете хэш и продолжаете использовать его, пока не столкнетесь с каким-то фиксированным числом столкновений. Затем вы произвольно выбираете другую хэш-функцию.

Например, в хэшировании Cuckoo (возможно, наиболее часто используемом универсальном хэше) вы используете хеш-ключ для поиска местоположения. Если он уже занят, вы "выкиньте" существующий элемент и повторите его, чтобы найти альтернативное местоположение для него. Там он вставлен. Если этот слот уже занят, он "выкидывает" элемент уже в этом слоте, и образец повторяется.

Когда вы ищете элемент, вы его используете и смотрите на это место. Если это пустое, вы сразу же знаете, что ваш товар отсутствует. Если этот слот занят, но не содержит ваш элемент, вы повторно используете хэш для поиска альтернативного местоположения. Продолжайте этот шаблон для множества хеш-функций, которые вы используете (как правило, только два в случае хэширования кукушки, но вы, очевидно, могли бы использовать аналогичный алгоритм с большим количеством функций).

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

При использовании открытого хэширования (универсальное хеширование - одна форма) удаление имеет тенденцию быть нетривиальным. В частности, мы должны убедиться, что когда мы удаляем элемент в одном месте, это не начало цепочки элементов, которые столкнулись в этом месте. Во многих случаях наиболее эффективно просто добавить третье состояние для слота: если он никогда не был занят, он просто пуст. Если он в настоящее время занят, он используется. Если элемент удален, он удаляется. Таким образом, когда вы ищете элемент, если вы сталкиваетесь с "удаленным" слотом, вы продолжаете поиск своего предмета (тогда как если вы попадаете в слот, который никогда не использовался, вы можете немедленно остановить поиск - ваш элемент четко никогда не вставлен).

Ответ 2

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

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

Ответ 3

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