Extendible Hashing is a #collision resolution strategy for 202112122035 that is similar to #202112121935.
Extendible Hashing could be used in:
- large databases
Analysis
- Find in 2 disk accesses
- Insertions in few disk accesses
- Average leaf is 69% full
- Expected size of directory is \(O(\frac{N^{1+\frac{1}{M}}}M)\)
Attention
- Hash key into reasonably long integers to avoid duplicate case
- Use leaves to contain pointers to the records to avoid small M