Унифицированные хеш-функции

Основы хеш-таблицы: — ОСНОВНЫЕ ИСПЫТАНИЯ. ВСЯ ПОМОЩЬ БУДЕТ ЦЕНА.

Я в основном немного запутался в равномерном хешировании ключей.

----------------------
| X X X                    <=== Chains; X represents an item in there
----------------------
| X X X                    <=== Multiple X represents collisions
----------------------
|
----------------------
| X X X
----------------------
| X
----------------------
  1. Рассмотрим случай вышеупомянутой хеш-таблицы, где M = 5 (количество строк), а общая длина равна 10. Как узнать, является ли эта хеш-таблица равномерно хешированной или нет?

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

  3. Если кто-то делает равномерное хеширование ключей, означает ли это, что функции поиска и удаления этой хеш-таблицы равны O (1) (амортизируется) и представляют собой сложную сложность O (n / M), где M — общее количество цепочек?

  4. Коэффициент загрузки или (N / # ofChains) идентифицирует однородность хеширования?

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

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

Кроме того, что это означает, когда они говорят, что «количество ключей, которые отображаются на каждый слот, равно». Означает ли это, что моя хеш-таблица, показанная выше, НЕ одинаково хешируется?

введите описание изображения здесь

Спасибо

0

Решение

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

1) Рассмотрим случай вышеупомянутой хеш-таблицы, где M = 5 (количество строк) и общая длина равна 10. Как узнать, является ли эта хеш-таблица равномерно хешированной или нет?

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

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

Это значит в среднем.

3) Если выполняется равномерное хеширование ключей, означает ли это, что функции поиска и удаления этой хеш-таблицы равны O (1) (амортизировано) и имеют сложную сложность O (n / M), где M — общее количество цепочек ,

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

2

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector