Hash Algorithm

Hashing

So many of us are using JSON to transfer data from system to system. To understand hashing the best example I can take is an associative array. An associative array, we store the value with respect to a key. In hashing, we do the same thing. There is a function known as Hash Function that will generate a key to a particular value. and store the data with respect to a key. This is the whole overview of Hash Data Structure. The efficiency of hashing depends on the efficiency of the hash function. Let us take on example to get the hash function of words in a dictionary. Our function will be structured as follows

f(n) = first letter of n

The mapping will be done like:-

"A" -> "Apple" -> "Ant" -> "Ape",
"B" -> "Ball" -> "Bell" -> "Bat",
"C" -> "Cat" -> "Comb" -> "Cascade",
...And So on

The basic of a hash function is like this.

Benefits

Suppose we take an array or linked list data structure to store our data. For searching, deleting and inserting data will take a lot of time O(n) or O(logn). In the binary search tree, we reduce the time complexity to moderate label i.e O(logn). But in case of direct access table we make a big array and use a unique key for each row(primary key, email, phone number). These keys point to each individual records, as a result, we can do all the operations in O(1) time. Which is a constant time complexity? But there is a limitation in the direct access table that it takes a huge amount of space to store the data. To overcome this situation Hashing is being introduced. In hashing, we can overcome all these situations and perform a task in minimal time. In Hashing we get an average case of O(1) and the worst case of O(n). Benefits

• Fast searching
• Fast Insertion
• Fast Deletion
• Fast Processing

Hash function

The function which converts a big number or large unique number to a smaller practical integer value. The mapped integer value is used as an index in the hash table. Properties

• Efficiently computable
• Should uniformly distribute the key

Hash table

An array that stores pointer to records corresponding to a given hash index produced by the hash function.

Collision handling

The behavior of a hash function is to provide a small value for a big integer. That brings a conflict that two big keys may have same hash index values. The situation when a newly inserted key is mapped to already occupied slot in a hash table is known as collision. Where there is a conflict we should handle the conflict using some technique. There are some basic technique through which we can handle this type of conflicts.

• Chaining (Which I have shown in the example. To store a number of value to a particular index using linked list)
• Open Addressing(All element stored in the hashtable itself, Each table entry contains either a record or a nill)