Hashtables и борьбы с столкновениями

Question

Предположим, хеш-таблица представлена ​​в виде массива размера 7. Мы хотим хранить строки, состоящие из трех цифр.Первичный хэш-ключ - это числовое значение второй цифры по модулю 7. Вторичный хэш-ключ - это числовое значение третьей цифры по модулю 4, увеличенное на единицу.Вставьте следующие строки в изначально пустую хеш-таблицу: «111», «222», «737», «323» и «234».

Мой ответ:

• 0 -234
• 1 - 111
• 2 - 222
• 3 - 737
• 4 - 323
• 5 -

• 6 -

• 111;1 мод 7 = 1

• 222;2 мод 7 = 2
• 737;3 мод 7 = 3
• 323;3 мод 4 + 1 = 4
• 234;4 мод 4 + 1 = 4 (0)

это правильно?

Answer 1

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

0:
1: 111
2: 222
3: 737
4: 323
5:
6:

Попытка вставить 234 с помощью h1 дает ключ 3 mod 7 = 3, но 3 уже содержит 373. Переходя к h2, мы получаем 4 mod 4 + 1 = 1, но1 уже содержит 111. На данный момент больше нет хеш-функций, поэтому мы вставляем 234 в 1 и перефразируем 111.

0:
1: 234
2: 222
3: 737
4: 323
5:
6:

Хеширование 111 с помощью h1 снова дает 1, h2 дает 1 mod 4 + 1 = 2, но 2 уже содержит 222, поэтому мы сохраняем 111 в 2 и перефразируем 222 и т. д. В этом случае, в конце концов, вы найдете все ключи подходящими.В случае, если их записи не подходят всем (т. Е. Повторная вставка входит в бесконечный цикл), размер таблицы должен быть изменен и дополнен новыми хэш-функциями.

Answer 2

Я не уверен, что эта проблема хочет, чтобы вы делали, если после проверки вторичного ключа хеш-функции все еще существует коллизия, но я думаю, что она выглядит так:

• 111: 1 мод7 = 1
• 222: 2 мода 7 = 2
• 737: 3 мода 7 = 3
• 323: 2 мода 7 = 2 => Столкновение: 3 мода 4 +1 = 3 + 1 = 4
• 234: 3 мода 7 = 3 => Столкновение: 4 мода 4 + 1 = 0 + 1 = 1 => Столкновение

Если вы продвинетесьна единицу после второго столкновения, результат будет

• 0 -
• 1 - 111
• 2 - 222
• 3 - 737
• 4 - 323
• 5 - 234
• 6 -
• 7 -