UNIT-6

Hashing and File Organization

Q1) Explain Hashing

A1) Hashing is a technique to convert a range of key values into a range of indexes of an array. We're going to use modulo operator to get a range of key values. Consider an example of hash table of size 20, and the following items are to be stored. Item are in the (key,value) format.

Q2) What is Linear Probing?

A2) As we can see, it may happen that the hashing technique is used to create an already used index of the array. In such a case, we can search the next empty location in the array by looking into the next cell until we find an empty cell. This technique is called linear probing.

Q3) Explain Search Operation of hash table

A3) Whenever an element is to be searched, compute the hash code of the key passed and locate the element using that hash code as index in the array. Use linear probing to get the element ahead if the element is not found at the computed hash code.

Example

struct DataItem *search(int key) {

   //get the hash

   int hashIndex = hashCode(key);

   //move in array until an empty

   while(hashArray[hashIndex] != NULL) {

      if(hashArray[hashIndex]->key == key)

         return hashArray[hashIndex];

      //go to next cell

      ++hashIndex;

      //wrap around the table

      hashIndex %= SIZE;

   }

   return NULL;       

}

Q4) Explain Insert Operation of hash table

A4) Whenever an element is to be inserted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing for empty location, if an element is found at the computed hash code.

Example

void insert(int key,int data) {

   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));

   item->data = data; 

   item->key = key;    

   //get the hash

   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell

   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {

      //go to next cell

      ++hashIndex;

      //wrap around the table

      hashIndex %= SIZE;

   }

   hashArray[hashIndex] = item;       

}

Q5) Explain Delete Operation of hash table

A5) Whenever an element is to be deleted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing to get the element ahead if an element is not found at the computed hash code. When found, store a dummy item there to keep the performance of the hash table intact.

Example

struct DataItem* delete(struct DataItem* item) {

   int key = item->key;

   //get the hash

   int hashIndex = hashCode(key);

   //move in array until an empty

   while(hashArray[hashIndex] !=NULL) {

      if(hashArray[hashIndex]->key == key) {

         struct DataItem* temp = hashArray[hashIndex];

         //assign a dummy item at deleted position

         hashArray[hashIndex] = dummyItem;

         return temp;

      }

      //go to next cell

      ++hashIndex;

      //wrap around the table

      hashIndex %= SIZE;

   } 

   return NULL;       

}

Hash Table is a data structure which stores data in an associative manner. In hash table, the data is stored in an array format where each data value has its own unique index value. Access of data becomes very fast, if we know the index of the desired data.

Q6) Explain Searching Techniques of hash table

 A6) In data structures,

 Example-

 Drawback-

 The main drawback of these techniques is-

 Hashing in Data Structure-

 In data structures,

 Advantage-

 Unlike other searching techniques,

Q7) What are the Types of Hash Functions?

A7) There are various types of hash functions available such as-

 It depends on the user which hash function he wants to use.

 Properties of Hash Function-

 The properties of a good hash function are-

Q8) What are the Characteristics of Good Hash Function?

A8)

Some Popular Hash Function is:

1. Division Method:

Choose a number m smaller than the number of n of keys in k (The number m is usually chosen to be a prime number or a number without small divisors, since this frequently a minimum number of collisions).

The hash function is:

For Example: if the hash table has size m = 12 and the key is k = 100, then h (k) = 4. Since it requires only a single division operation, hashing by division is quite fast.

2. Multiplication Method:

The multiplication method for creating hash functions operates in two steps. First, we multiply the key k by a constant A in the range 0 < A < 1 and extract the fractional part of kA. Then, we increase this value by m and take the floor of the result.

The hash function is:

Where "k A mod 1" means the fractional part of k A, that is, k A -⌊k A⌋.

3. Mid Square Method:

The key k is squared. Then function H is defined by

Where L is obtained by deleting digits from both ends of k2. We emphasize that the same position of k2 must be used for all of the keys.

4. Folding Method:

The key k is partitioned into a number of parts k1, k2.... kn where each part except possibly the last, has the same number of digits as the required address.

Then the parts are added together, ignoring the last carry.

H (k) = k1+ k2+.....+kn

Example: Company has 68 employees, and each is assigned a unique four- digit employee number. Suppose L consist of 2- digit addresses: 00, 01, and 02....99. We apply the above hash functions to each of the following employee numbers:

(a) Division Method: Choose a Prime number m close to 99, such as m =97, Then

That is dividing 3205 by 17 gives a remainder of 4, dividing 7148 by 97 gives a remainder of 67, dividing 2345 by 97 gives a remainder of 17.

(b) Mid-Square Method:

k = 3205       7148       2345

k2= 10272025   51093904   5499025

h (k) = 72     93         99

Observe that fourth & fifth digits, counting from right are chosen for hash address.

(c) Folding Method: Divide the key k into 2 parts and adding yields the following hash address:

Q9) Why we need Hashing?

A9)

Suppose we have 50 employees, and we have to give 4 digit key to each employee (as for security), and we want after entering a key, direct user map to a particular position where data is stored.

If we give the location number according to 4 digits, we will have to reserve 0000 to 9999 addresses because anybody can use anyone as a key. There is a lot of wastage.

In order to solve this problem, we use hashing which will produce a smaller value of the index of the hash table corresponding to the key of the user.

Universal Hashing

Let H be a finite collection of hash functions that map a given universe U of keys into the range {0, 1..... m-1}. Such a collection is said to be universal if for each pair of distinct keys k,l∈U, the number of hash functions h∈ H for which h(k)= h(l) is at most |H|/m. In other words, with a hash function randomly chosen from H, the chance of a collision between distinct keys k and l is no more than the chance 1/m of a collision if h(k) and h(l)were randomly and independently chosen from the set {0,1,...m-1}.

Rehashing

If any stage the hash table becomes nearly full, the running time for the operations of will start taking too much time, insert operation may fail in such situation, the best possible solution is as follows:

Q10) PRACTICE PROBLEM BASED ON SEPARATE CHAINING-

 Problem-

 Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-

50, 700, 76, 85, 92, 73 and 101

 Use separate chaining technique for collision resolution.

S10)

The given sequence of keys will be inserted in the hash table as-

Step-01:

Step-02:

Step-03 

Step-04:

 Step-05:

Step-06:

 Step-07:

Step-08: