Problem with Hashing...
So far, discussion of hashing has assumed a fixed file size
(fixed b).
What size file to use?
- the size we need right now
(performance degrades as file overflows)
- the maximum size we might ever need
(signifcant waste of space)
Change file size ⇒ change hash function ⇒ rebuild file
Methods for hashing with dynamic files:
- extendible hashing, dynamic hashing (need a directory, no overflows)
- linear hashing (expands file "sytematically", no directory, has overflows)
|