Next: Hash Indices
Up: Hash File Organization
Previous: Hash Functions
Open hashing occurs where records are stored in different buckets.
Compute the hash function and search the corresponding bucket to find a
Closed hashing occurs where all records are stored in one
bucket. Hash function computes addresses within that bucket.
(Deletions are difficult.)
Not used much in database applications.
Drawback to our approach: Hash function must be chosen at
- Number of buckets is fixed, but the database may grow.
- If number is too large, we waste space.
- If number is too small, we get too many ``collisions'', resulting in
records of many search key values being in the same bucket.
- Choosing the number to be twice the number of search key values in
the file gives a good space/performance tradeoff.
Mon Jul 13 13:28:03 PDT 1998