Page 195 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes and place y in the ith location of the table. There are various methods available to obtain an
alternative location to handle the collision. They differ from each other in the way search is made
for an alternative location. The following are the commonly used collision handling techniques:

9.1.1 Linear Probing or Linear Open Addressing

In this method, if for an identifier x, h(x) = i, and if the ith location is already occupied then you

search for a location close to the ith location by doing a linear search starting from the (i+1)th
location to accommodate x. This means you start from the (i+1)th location and do the linear search
till you get an empty location, and once you get an empty location I accommodate x there.

9.1.2 Overfl ow Chaining

This is a method of implementing a hash table, in which collisions gets handled automatically. In

this method you use two tables, a symbol table to accommodate identifiers and their attributes,
and a hash table which is an array of pointers pointing to symbol table entries. Each symbol table

entry is made of three fi elds, first for holding the identifier, second for holing the attributes, and
the third for holding the link or pointer which can be made pointing to any symbol table entry.
The insertions into the symbol table are done as follows:
If x is symbol to be inserted, then it will be added to the next available -entry of the symbol table.
The hash value of x is then computed, if h(x) = i, then the ith hash table pointer is made pointing
to the symbol table entry in which x is stored if the ith hash table pointer is not pointing to any
symbol table entry. If the ith hash table pointer is already pointing to some symbol table entry,
then the link field of symbol table entry containing x is made pointing to that symbol table entry

to which ith hash table pointer is pointing to, and make the ith hash table pointer pointing the
symbol entry containing x. This is equivalent to building a linked list on the ith index of the hash
table. The retrieval of attributes is done as follows:

If x is a symbol, then you obtain h(x), and use this value as the index of the hash table, and traverse
the list built on this index to get that entry which contains x. A typical hash table implemented
using this technique is shown below:
Let the symbols to be stored are x , y , z , x , y , z . The hash function that you use:
1 1 1 2 2 2

h(symbol) = (value of first letter of the symbol) mod n,
Where n is the size of table.
if h(x ) = i
1
h(y ) = j
1
h(z ) = k
1
then
h(x ) = i
2
h(y ) = j
2
h(z ) = k
2
Therefore, the contents of the symbol table will be the one shown in Figure 9.1.

190 LOVELY PROFESSIONAL UNIVERSITY