Page 235 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes It is possible that when a hash function is mapping the keys into a hash table, two elements
might hash to the same location in the hash table. This is known as collision. But this is for sure
that the first element that is already present in the hash table cannot be modified. So the new
element has to be brought up with a solution. In order to avoid this collision we can prefer one
of these solutions:
Search from that position for an empty location.
Use a second hash function.

Use that array location as the header of a linked list of values that hash to this location.
13.5.3 Working of Hashing

Suppose we need to store all the information of 5 employees in a hash table and unique security
number of the employees is used as a key. Let’s assume that the size of the hash table is 6. Hence
the hash function should be:-

Value modulo 6
The value is the ssn number of the employee and modulo (%) is the arithmetic modulo operation.
6 is the size of the hash table. The hash function is usually modulated like this in case of integers.
Hence we can write it in simpler words as:
Hash function= (sum of all the digits in ssn) % 6
For employee1 ssn = 2342158231IN
2+3+4+2+1+5+8+2+3+1=31

Hash code= 31 % 6 =1.
So the hash function maps the ssn of employee 1 to index 1 in the hash table.
Similarly all the employees are mapped onto the hash table by the hash function and there is a
chance of collision. If there is a collision then the above solutions can be followed to solve the
collision problem.

13.5.4 Types of Hashing

The different types of hashing are:

Static Hashing
Dynamic Hashing
Static Hashing

In static hashing the process is carried out without the usage of an index structure. Data is
normally accessed on a disk by computing a function on key instead. A bucket in a hash file is a
storage unit that can hole records. This bucket can be a block in the disk. For inserting a data we
need to find the hash code subsequently and place the record in the bucket. For searching the
data compute the hash value and match with each record in the bucket. The hash function can
assign equal or random number of records to all the buckets. Bucket overflow can occur if:
There are not enough buckets to store data.
A few buckets have more records then others. (Multiple records have same hash value)
In order to provide a solution for bucket overflow issue, we need to provide more buckets than
are needed. If a bucket is full, then link another bucket to it and repeat this process.

228 LOVELY PROFESSIONAL UNIVERSITY