Унифицированные хеш-функции
Основы хеш-таблицы: — ОСНОВНЫЕ ИСПЫТАНИЯ. ВСЯ ПОМОЩЬ БУДЕТ ЦЕНА.
Я в основном немного запутался в равномерном хешировании ключей.
----------------------
| X X X <=== Chains; X represents an item in there
----------------------
| X X X <=== Multiple X represents collisions
----------------------
|
----------------------
| X X X
----------------------
| X
----------------------
-
Рассмотрим случай вышеупомянутой хеш-таблицы, где M = 5 (количество строк), а общая длина равна 10. Как узнать, является ли эта хеш-таблица равномерно хешированной или нет?
-
Если кто-то делает равномерное хеширование набора ключей, означает ли это, что списки внутри цепочек в хеш-таблице, или связанные списки из-за коллизий, имеют одинаковую длину? Или это означает среднее?
-
Если кто-то делает равномерное хеширование ключей, означает ли это, что функции поиска и удаления этой хеш-таблицы равны O (1) (амортизируется) и представляют собой сложную сложность O (n / M), где M — общее количество цепочек?
-
Коэффициент загрузки или (N / # ofChains) идентифицирует однородность хеширования?
Я надеюсь, что вы можете помочь мне с этими вопросами. Мой профессор представил много концепций в классе, и я просто сводил их здесь вместе, и я запутался, когда соединил эти концепции.
Я искал в Интернете больше, чтобы изучить эту концепцию, и я увидел набор слайдов, как показано ниже. Я был бы обязан, если вы можете объяснить мне, что означает уравнение на втором слайде по отношению к равномерному хешированию ключей.
Кроме того, что это означает, когда они говорят, что «количество ключей, которые отображаются на каждый слот, равно». Означает ли это, что моя хеш-таблица, показанная выше, НЕ одинаково хешируется?
Спасибо
Решение
Слайд говорит о всех возможных значениях ключей. Важно понимать, что в вашей хэш-карте у вас есть только подмножество ключей в любой момент времени. Независимо от того, насколько хороша ваша хэш-функция, вам может повезти в том, как эти ключи отображаются в сегменты, или нет.
1) Рассмотрим случай вышеупомянутой хеш-таблицы, где M = 5 (количество строк) и общая длина равна 10. Как узнать, является ли эта хеш-таблица равномерно хешированной или нет?
Равномерное хеширование является свойством хеш-функции, а не хеш-таблицы. Поэтому, просто взглянув на содержимое хеш-таблицы, вы не сможете. Вы должны посмотреть на саму хэш-функцию, чтобы определить, является ли она равномерной.
2) Если кто-то делает равномерное хеширование набора ключей, означает ли это, что списки внутри цепочек в хеш-таблице, или связанные списки из-за коллизий, имеют одинаковую длину? Или это означает среднее.
Это значит в среднем.
3) Если выполняется равномерное хеширование ключей, означает ли это, что функции поиска и удаления этой хеш-таблицы равны O (1) (амортизировано) и имеют сложную сложность O (n / M), где M — общее количество цепочек ,
Помимо свойств хеш-функции, сложность также зависит от коэффициента загрузки. Если количество сегментов растет линейно по количеству элементов, вы получаете O(1) найти и удалить в среднем (до тех пор, пока вы не амортизируете повторное ведение соответствующим образом).
Другие решения
Других решений пока нет …