Theory Of Hashing And Hash Tables

1. Chaining
2. Linear Probing - Open addressing technique
3. Double Hashing - Open addressing technique

Chaining

Chaining technique replaces an array index slot with the linked list, if more than one value points to the same index. Here, is a graphical illustration.



Here, hash function(hf) is generating same index (index 3) for the two values. Therefore, both these keys will point to index 3, which will be replaced by linked list and index three will point to the head of linked list. The same algorithm is applied, when we retrieve the values from Hash Tables. This technique is used in managed languages like Hash Tables and hashmap in Java.

Open addressing schemes: This technique is used when there are more buckets (index slots), available than the actual values. Two techniques used in this scheme are as follows:

Linear Probe

Here, if the hash function is generating the same hash index value, then, it will look for another empty slot available to store the data.

Example:

if hf (kiran) = 4 is occupied then it will look for hf (komal) + 1 = 5

It will keep repeating this, until it can found in the next available empty index.



Double Hashing

In this, two different hashing functions are used. If the first hash function hf (key) is occupied, then the second hash function hf1 (key) is used to increment the result of first hash function. E.g.

hf (key) = 4 occupied then
hf (key) + hf1 (key) = 8 will be used.



Open addressing scheme is relatively slow, because it would have to iterate through lot of buckets until it finds the empty one.

Where do we use Hash Tables?

• We use Hash Tables to store arrays; having key value pairs in programming languages such as Dictionaries, Hash Tables in C# and Hash Tables and Hashmap in Java. Using this, you can quickly search an item with a given key, without scanning whole collection of Hash Tables array.
  
  
• One can use Hash Tables in the temporary tables in a relational database system like SQL Server.

What is the difference between Hash Tables and binary search tree and how do we choose between the two?

Hash Table is a linear and unordered data structure whereas binary search tree is nonlinear and sorted. Lookups and insertion in the binary tree is relatively slow, compared to Hash Tables. Use Hash Tables if you are using large unordered collections of data. Use binary search tree, if you have small collection of ordered data, which will be faster.

In other cases, if you have small collection which is already sorted, there will not be extra memory consumption to sort and store sorted data in the memory, in case we use binary search.