Next: Hash Functions
Up: Static Hashing
Previous: Static Hashing
Hashing involves computing the address of a data item by computing
a function on the search key value.
A hash function h is a function from the set of all search key
values K to the set of all bucket addresses B.
- We choose a number of buckets to correspond to the number of search
key values we will have stored in the database.
- To perform a lookup on a search key value , we compute
, and search the bucket with that address.
- If two search keys i and j map to the same address, because
, then the bucket at the address obtained will contain
records with both search key values.
- In this case we will have to check the search key value of every record
in the bucket to get the ones we want.
Insertion and deletion are simple.
Mon Jul 13 13:28:03 PDT 1998