Symbol Table (Part 2)

More Collision Handling Techniques

2) Pseudo random probing (from Data Structure Techniques by Standish)

This method chooses p(K)=C for all K where C is an integer that is relatively prime to the table size M. The effect of this is to generate a pseudo random probe sequence.

Note: relatively prime refers to the fact that C and M have no common integral factors except 1 or -1.

3) Radke's Quadratic Residue Search (from Data Structure Techniques by Standish)

For this collision handling technique, we will use a probe sequence of the form: h(K), h(K)+i^2, h(K)-i^2, ... all reduced modulo the tablesize M. The values of i increase in the interval 1<=i<=(M-1)/2. Further, with M chosen as a prime number of the form 4j+3, it is guarenteed that the probe sequence is a permutation of the table space.

4) Chaining

Chaining still involves using the hash technique described above, but collisions are handled using chains (linked lists) when a collision happens at a particular address. That is, we maintain M linked lists, one for each possible address in the hash table. Some key K hashes such as b=h(K). At address b we find the head of a linked list and put the key K at the head of the list. Now if another key K' hashes to the same address, then we put the key K' into the linked list.

Problem #1: Hash the keys M13, G7, Q17, Y25, R18, Z26, and F6 using the formula h(Kn)=n mod 9 with: (a) linear probing (b) chaining. Further, compute the average number of probes for this set of keys for both methods (linear probing and chaining).

Problem #2: Assume that you have a hash table that needs to print out the symbols in lexicographic order. If you have a hash algorithm of the form f(x) = ASCII value of the 1st character of the symbol and linear probing is used, what algorithm would you use to print the symbols in lexicographic order and what is the complexity of this algorithm? (Horowitz and Sahni)

Problem #3: An assembler's symbol table needs to be able to insert, search, and modify efficiently. Typically, the assembler needs to produce a sorted symbol table as part of the listing file. Describe a data structure that can handle all of these things efficiently.