Page 202 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 9: Hashing

(b) Determine the hash addresses and find how many collisions occur when these keys Notes

are first folded by adding their digits together (in ordinary decimal representation)

and then applying % hash_size.
(c) Find a hash function that will produce no collisions for these keys. (A hash function
that has no collisions for a fixed set of keys is called perfect.)

(d) Repeat the previous parts of this exercise for hash_size = 11. (A hash function that

produces no collision for a fixed set of keys that completely fill the hash table is called
minimal perfect.)
6. Another method for resolving collisions with open addressing is to keep a separate array
called the overflow table, into which are put all entries that collide with an occupied

location. They can either be inserted with another hash function or simply inserted in
order, with sequential search used for retrieval. Discuss the advantages and disadvantages
of this method.
7. With linear probing, it is possible to delete an entry without using a second special key, as
follows. Mark the deleted entry empty. Search until another empty position is found. If the

search finds a key whose hash address is at or before the just-emptied position, then move
it back there, make its previous position empty, and continue from the new empty position.
Write an algorithm to implement this method. Do the retrieval and insertion algorithms
need modifi cation?
8. In a chained hash table, suppose that it makes sense to speak of an order for the keys,
and suppose that the nodes in each chain are kept in order by key. Then a search can
be terminated as soon as it passes the place where the key should be, if present. How
many fewer probes will be done, on average, in an unsuccessful search? In a successful
search? How many probes are needed, on average, to insert a new node in the right place?
Compare your answers with the corresponding numbers derived in the text for the case of
unordered chains.
9. The hash table itself contained only lists, one for each of the chains. One variant method

is to place the first actual entry of each chain in the hash table itself. (An empty position
is indicated by an impossible key, as with open addressing.) With a given load factor,
calculate the effect on space of this method, as a function of the number of words (except
links) in each entry. (A link takes one word.)
10. Distinguish between linear and quadratic probing.
11. Consider using division method of hashing store the following values in the hash table of
size 13:
29, 45, 106, 136, 162, 172, 297, 301

Answers: Self Assessment

1. linked list 2. Open hashing 3. Collision
4. deterministic 5. symbol table 6. hash function
7. symbols 8. Truncation

LOVELY PROFESSIONAL UNIVERSITY 197