Page 199 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 2. B the set of hash values (also called the buckets or bins). Let B = {0, 1,..., m - 1}where m > 0
is a positive integer.
A hash function h: U → B associates buckets (hash values) to keys.
Two main issues:

Collisions

If x and x are two different keys, it is possible that h(x ) = h(x ). This is called a collision. Collision
1
1
2
2
resolution is the most important issue in hash table implementations.
Hash Functions
Choosing a hash function that minimizes the number of collisions and also hashes uniformly is
another critical issue.

9.4 Closed Hashing

1. All elements are stored in the hash table itself
2. Avoids pointers; only computes the sequence of slots to be examined.
3. Collisions are handled by generating a sequence of rehash values.

h: U × U → {0, 1, 2,..., m - 1}
universe of primary keys probe number
4. Given a key x, it has a hash value h(x,0) and a set of rehash values
h(x, 1), h(x,2), . . . , h(x, m-1)
5. I require that for every key x, the probe sequence
< h(x,0), h(x, 1), h(x,2), . . . , h(x, m-1)>
be a permutation of <0, 1, ..., m-1>.
This ensures that every hash table position is eventually considered as a slot for storing a
record with a key value x.

Search (x, T)

Search will continue until you find the element x (successful search) or an empty slot (unsuccessful
search).
Delete (x, T)

1. No delete if the search is unsuccessful.

2. If the search is successful, then put the label DELETED (different from an empty slot).
Insert (x, T)

1. No need to insert if the search is successful.
2. If the search is unsuccessful, insert at the first position with a DELETED tag.

194 LOVELY PROFESSIONAL UNIVERSITY