[prev] 33 [next]

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)