Hashing

Hashing is the method which involvesconversion of a key into a index via use of Hash Function. Consider the problem of searching an array for a given value. If the array is not sorted, the search might require examining each and all elements of the array (performing a sequential search). If the array is sorted, we can use the binary search, therefore reducing the worse-case runtime complexity to O(log n). We could search even faster if we know in advance the index at which that value is located in the array. Suppose we do somehow know thefunction that would tell us the index for a given value. With this magic function our search is reduced to just one probe, giving us a constant runtime O(1). Such a function is called a hash function and the process Hashing.

Let us say we have a table with an entry the keys:

We can simply have an array represent each key. But what about the case like below?

The Key to Index Method Fails to work here. So simply we can represent each data index with easier index say from 000 to 999 instead of 10 million space allocation.

A simple hash function for the purpose can be:
Int getindex(int key)
{
return key00;
}

Now, the scene looks like:

But there can be numbers with last same digits. For this Hash Clashes must be avoided. To do these, several hash functions are used, which are discussed in the upcoming sections of this chapter.

References

1.https://en.wikipedia.org/wiki/Hash_function

2. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structuresusing C and C++”

3. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”