0

Is it possible for a single insert into an extendible hash to result in multiple directory doubles? All the online resources I could find only demonstrate cases where only a single double is necessary.

Consider the example using the MSB of keys:

| 0 | -> 00111

| 1 | -> 11110

insert(11111)

What would the result be? Would I need to double the directory multiple times?

user3694523
  • 1
  • 1

1 Answers1

0

This would depend on your maximum page size. If your pages can only contain more than one key, then you can simply add the key to the end of the entry from 1, as below:

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

Otherwise, you would have to extend the MSB Directory multiple times , in which case you would get.

If you require the opposite, I am sure you can implement the solution with LSB instead.

Kam
  • 1