Flat Preloader Icon



  1. Why Hashing?
  2. Hashing
  3. Key terms
  4. collision
  5. Hash function
  6. Collision Resolution

Why - Hashing

  • 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.

Key Terms

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
                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

Hash Function

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

Various hash functions

  1. Simple mod function
  2.  Division method
  3. Binning
  4.  Mid square method

Collision Resolution

Two types of resolution

  • open Hashing (chairing)
  • closed Hashing (open addressing

Open Hashing

Closed Hashing