Расширяемое хеширование с подобными ключами

Question

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

Рассмотрим пример с использованием MSB ключей:

| 0 | -> 00111

| 1 | -> 11110

вставить (11111)

Каков будет результат? Нужно ли мне удваивать каталог несколько раз?

Answer 1

Это будет зависеть от вашего максимального размера страницы. Если ваши страницы могут содержать только несколько ключей, вы можете просто добавить ключ в конец записи от 1, как показано ниже:

| 0 | -> 00111 | 1 | -> 11110, 11111

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

Если вам требуется обратное, я уверен, что вы можете вместо этого реализовать решение с помощью LSB.