Extensible Hashing

• use i of b bits output by hash function

  • i grows over time

• use directory (bucket address table)

• many consecutive directory entries may point to the same bucket

• associate with this bucket the length of the common prefix

00110101

b

i

h(key)[i]

Directory

to

bucket

00

01

10

11

2

1

2

2

Directory

Buckets

Previous slide

Next slide

Back to first slide

View graphic version