Hashing

Overview

Hashing is designed to solve the problem of needing to efficiently find or store an item in a collection
if we have a list of 1,00 ,ooo words of English and we want to search a given word in the list , it would be
inefficient to successively compare the word with all 100,000 words until we find a match.

It is a technique of mapping keys , and values into the hash table by using function.
If implemented correctly then one can achieve O(1) time complexity in searching an item in the collection of elements
Efficiency of mapping depends on the efficiency of the hash function used.

Hash Table	It is the data structure used to store elements
Hash function	It is a function to map /Hash) Key -values to the memory address
Hashing	It is a method for storing and retrieving records from a database

Suppose too student records need to be stored in an array of 100 memory slots .Use hashing to perform efficient access of student data

Roll no->1 to 100
key i=Hf(key)
int Hf(int key)
{
return key-1;
}

Hashing is amethod of stormy and retrieving records from data structure
It lets you insert ,delete and search records based on search key value
When properly implemented these
operations can be performed in constant
time .
this is far better than Ocdogzn) average cost required to do a binary search on a sorted array
Hashing generally takes records whose key values come from a large range and
stores those records ina table with a relatively small number of slots

Roll no->5 digit nuber 10000 to 99999
10025->25
25287->87
51128->28
48225->25
int HF(int key)
{
return key % 100;
}

collision occur when two records hash
to the same slot in the table
Unfortunately ,
even under the best of
circumstances ,
collisions are nearly
unavoidable

The hash function creates a mapping between key and value , this is done through the use of mathematical formula

Various hash functions

Two types of resolution