Page 201 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 9.7 Keywords

Folding: In folding the identifier is partitioned into several parts all but the last part being of the

same length.
Hash Function: A Hash Function is a Unary Function that is used by Hashed Associative
Containers.
Hashing: Hashing is the transformation of a string of characters into a usually shorter

fixed-length value or key that represents the original string.

Rehashing: In rehashing find an alternative empty location by modifying the hash function, and
applying the modified hash function to the colliding symbol.

9.8 Self Assessment

Fill in the blanks:

1. The simplest form of open hashing defi nes each slot in the hash table to be the head of a
.............................. .
2. .............................. is most appropriate when the hash table is kept in main memory, with
the lists implemented by a standard in-memory linked list.
3. .............................. resolution is the most important issue in hash table implementations.
4. A Hash Function must be .............................. and stateless.
5. A .............................. is referred to or accessed frequently either for adding the name, or for
storing the attributes of the name, or for retrieving the attributes of the name.
6. Hashing is a method of directly computing the index of the table by using some suitable
mathematical function called .............................. .

7. Collision handling involve finding out an alternative location for one of the two colliding

.............................. .
8. .............................. method ignores part of key, and use the remainder part directly as hash
value.

9.9 Review Questions

1. Describe overfl ow chaining.
2. Describe various hash functions in detail.
3. Describe rehashing.

4. Devise a simple, easy to calculate hash function for mapping three-letter words to integers
between 0 and n−1, inclusive. Find the values of your function on the words
PAL LAP PAM MAP PAT PET SET SAT TAT BAT
for n = 11, 13, 17, 19. Try for as few collisions as possible.

5. Suppose that a hash table contains hash_size = 13 entries indexed from 0 through 12 and
that the following keys are to be mapped into the table:
10 100 32 45 58 126 3 29 200 400 0

(a) Determine the hash addresses and find how many collisions occur when these keys
are reduced by applying the operation % hash_size.

196 LOVELY PROFESSIONAL UNIVERSITY