Hashing is the process of converting an input of any length into a fixed size string or a number using an algorithm. In hashing, the idea is to use a hash function that converts a given key to a smaller number and uses the small number as an index in a table called a hash table.
Hashing in Data Structures
We generate a hash for the input using the hash function and then store the element using the generated hash as the key in the hash table.
Operation in hash function:
- Insert - T[ h(key) ] = value;
It calculates the hash, uses it as the key and stores the value in hash table.
2)Delete - T[ h(key) ] = NULL;
It calculates the hash, resets the value stored in the hash table for that key.
3)Search - return T[ h(key) ];
It calculates the hash, finds and returns the value stored in the hash table for that key
Hash Collision: When two or more inputs are mapped to the same keys as used in the hash table. Example: h(“John”) == h( “joe”)
A collision cannot be completely avoided but can be minimized using a ‘good’ hash function and a bigger table size.
The chances of hash collision are less if the table size is a prime number.
