Basic Concept of Hashing

Basic Concept

Hashing is an effective way to reduce the number of comparisons. Actually hashing deals with the idea of proving the direct address of the record where the record is likely to store. To understand the idea clearly let us take an example -

Suppose the manufacturing company has an inventory file that consists of less than 1000 parts. Each part is having unique 7 digit number. The number is called 'key' and the particular keyed record consists of that part name. If there are less than 1000 parts then a 1000 element array can be used to store the complete file. Such an array will be indexed from 0 to 999. Since the key number is 7 digit it is converted to 3 digits by taking only last three digits of a key. This is shown in the Fig. 6.1.1.

Observe in Fig. 6.1.1 that the first key 496700 and it is stored at oth position. The second key is 8421002. The last three digits indicate the position 2nd in the array. Let us search the element 4957397. Naturally it will be obtained at position 397. This method of searching is called hashing. The function that converts the key (7 digit) into array position is called hash function. Here hash function is

h(Key) = key  1000

Where key % 1000 will be the hash function and the key obtained by hash function is called hash key.

1. Basic Concepts in Hashing

1) Hash Table : Hash table is a data structure used for storing and retrieving data quickly. Every entry in the hash table is made using Hash function.

2) Hash Function:

• Hash function is a function used to place data in hash table.

• Similarly hash function is used to retrieve data from hash table.

• Thus the use of hash function is to implement hash table.

For example : Consider hash function as key mod 5. The hash table of size 5.

3) Bucket: The hash function H(key) is used to map several dictionary entries in the hash table. Each position of the hash table is called bucket.

4) Collision: Collision is situation in which hash function returns the same address for more than one record.

For example

5) Probe: Each calculation of an address and test for success is known as a probe.

6) Synonym: The set of keys that has to the same location are called synonyms. For example - In above given hash table computation 25 and 55 are synonyms.

7) Overflow : When hash table becomes full and new record needs to be inserted then it is called overflow.

For example -

Ex. 6.1.1: Indicate whether you use an Array, Linked List or Hash Table to store data in each of the following cases. Justify your answer.

1) A list of employee records needs to be stored in a manner that it is easy to find max or min in the list.

2) A library needs to maintain books by their ISBN number. Only thing important is finding them as soon as possible.

3) A data set needs to be maintained in order to find the median of the set quickly.

AU: May-19, Marks 6

Sol. : 1) The list of employees can be stored in an array. The min or max value can be searched easily from the array.

2) As the book is searched using ISBN, hash table can be used to store the book records.

3) The data set can be stored in an array, so that the median of array can be easily obtained.