Как рассчитать максимальное / минимальное количество зондов, необходимых для построения хеш-таблицы

Question

В настоящее время я работаю с Алгоритмами четвертого издания Роберта Седжвика и Кевина Уэйна, и я застрял в одном из упражнений. Я знаю, что есть кто-то, кто разместил решения для многих упражнений из этой книги на GitHub, но я хочу сделать их самостоятельно, чтобы я мог понять и извлечь уроки из них.

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

Упражнение:

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

key = "ABCDEFG"

hash= "2 0 0 4 4 4 2"

Что из нижеперечисленного не могло быть результатом вставки этих ключей?

a) EFGACBD

b) CEBGFDA

c) BDFACEG

d) CGBADEF

e) FGBDACE

f) GECADBF

Я нашел этот сайт http://orion.lcg.ufrj.br/Dr.Dobbs/books/book2/algo02e5.htm, но я не мог понять этого. Я был озадачен тем, что делать, когда пытался решить эту проблему, сначала я подумал, что неправильно понял вопрос, или что просто не могу найти формулу для решения упражнения.

Как рассчитатьмаксимальное и минимальное количество зондов, которое может потребоваться для построения таблицы размером m?

Answer 1

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

Давайте посмотрим на (a) вместе: E F G A C B D.

Если мы заменим ключи на их хэшзначения, мы получим 4 4 2 2 0 0 4. Теперь важная часть - обратите внимание, что only G находится в «правом» сегменте, все остальные значения были смещены из-за линейного зондирования. Это возможно?

Скажем, мы сначала вставили G, и она была записана в индекс 2. Что теперь? Если мы вставим ключ с хешем 0 или 4, он будет помещен в ячейку 0 или 4 без проверки, а это не то, что нам нужно. Единственный вариант - вставить A сейчас, который также имеет хеш-значение 2. Куда это пойдет? Индекс 3 конечно из-за линейного зондирования. Пока все хорошо, наш массив выглядит так: X X G A X X X

Что теперь? У нас остались только ключи с хешем 0 или 4, и как только мы вставим один такой ключ, он будет помещен в ячейку 0 или 4. Но в шаблоне, к которому мы обращаемся, все значения с хэшами 0 и 4 не находятся в «правильной» ячейке. Следовательно, этот шаблон невозможен.

Теперь давайте посмотрим на (b). Заказ составляет C E B G F D A, что означает 0 4 0 2 4 4 2. Как мы можем создать этот шаблон?

Давайте вставим C: C X X X X X X Что теперь? Давайте вставим F: C X X X F X X. Теперь давайте вставим D. Из-за линейного зондирования мы получим C X X X F D X. Что теперь? Застряли. Неважно, что мы вставим сейчас, мы не сможем достичь C E B G F D A. Что мы можем изменить в наших предыдущих вставках, чтобы добиться другого результата? Нет. Следовательно, (б) также невозможно.

Answer 2

Кажется, что ни один из вариантов не возможен.

a) EFGACBD (4 4 2 2 0 0 4).
возможный порядок ввода: G, A (остальное невозможно)

b)CEBGFDA ( 0 4 0 2 4 4 2).
возможный порядок ввода: C, F, D (остальное невозможно)

c)BDFACEG ( 0 4 4 2 0 4 2).
возможный порядок вставки: B (остальное невозможно)

d) CGBADEF ( 0 20 2 4 4 4 ).
возможный порядок вставки: C, D, E, F (остальное невозможно)

e) FGBDACE (4 2 0 4 2 04).
возможный порядок вставки: нет возможной последовательности вставки

f) GECADBF (2 4 0 2 4 0 4).
возможный порядок вставки: D (остальныене возможно)