Как с этим справляется линейное зондирование?
• хеш-функция: h(x) = | 2x + 5 | мод М
• массив блоков емкостью N
• набор объектов с ключами: 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, 5 (для ввода слева направо)
4.a [5 баллов ] Напишите хеш-таблицу, где M=N=11, а столкновения обрабатываются с помощью линейного зондирования.
Итак, я встал здесь
ххххх 44 88 12 23 13 94
но следующая переменная должна идти после 94 сейчас (11), но начинается ли она с начала или как? Спасибо
Кроме того, если M=11, можете ли вы найти значение N, которое не генерирует коллизии, хэширующие эти ключи?
как это может быть возможно? Я имею в виду, даже если бы массив был действительно большим, колизии все равно бывали?
1 ответ
Да, это начнется с самого начала, т.е.
Столкновения зависят от вашей хэш-функции. Так что, да, даже если ваша хеш-таблица достаточно велика, все равно могут возникнуть коллизии.