Basics of Hashing and Why hashing is used ?

The article explains why hashing have o(1) complexity. This article will clear your doubt that whay hashing has 0(1) time complexity but will not take you deeper . There are certain factors which can affect the time complexity like collision and performance of hashing depends on hashing algorithm.

student: forget about working of hashing just tell me for what reason hashing exists at all?
teacher: There are several answers to this but the perfect one is this "it makes the search faster".
student: how? i have binary search with o(log n).can hashing do better then this?
teacher: yes.hashing works with o(1).
student: how?
teacher: if you have the index of the data which you have to find then simply put that index in array and get your data.

Code:

 int search_data(int index,int a[]){
 return a[index];
 }
 

teacher: so folks what's the time complexity of this function search_data()?
student: o(1).constant.does not depends on input.
student: how will i know this index?
teacher: hashing function will give to you that index.
teacher: let me explain you in this way.
teacher: say you have to find a roll no of a student name "dumb_***"
teacher: assume that each name will be of string type with max length 25 characters (25 bytes)
teacher: lets say you have two arrays one for students and one for their roll numbers

Code:

int main()
{

  int no_of_students=10000;
  int n=no_of_students;
  char  *students[n]={"shawn","sha",....,"dumb_***"};
  char  *rollno[n]={"805021","805026",....,"805029"};
  int index_to_find=-1;
  for(int i=0;i<n;++i)
  {
    if(strcmp("students[i]","dumb_***")==0)
    {
      index_to_find=i;
      exit;
    }
  }
  printf("%s",rollno[index_to_find]);
}
 

teacher: so what's the time complexity.
student: o(n).
teacher if you use binary search instead of linear search then?
student: o(log n)
teacher: now lets see hashing

Code:

// just assume that it produce some ouput h based on key
//if keys are same then output must be same
//famous hashing function xor_hash
// dont bother about its internal working
unsigned int suit_hash ( char *key, int len )
{
  unsigned char *p = key;
  unsigned int h = 0;
  int i;

  for ( i = 0; i < len; i++ )
    h ^= p[i];

  return (h%no_of_students);
}
int main()
{
  char  *rollno[n];
  /* first store using same key "dumb_***" */
  roll[suit_hash("dumb_***",25)]="805026";
  /*  retrieve roll no  using same key "dumb_***" */
  printf("%s",roll[suit_hash("dumb_***",25)]);
}
 

teacher: can you tell me the time complexity now?
student: 2 * complexity of suit_hash() + constant1
teacher: yes go on tell me the complexity of suit_hash()
student: it is o(len).since len is constant (always 25).
teacher: yes you are in the right path
student: i think time complexity of this approach (or hashing ) is o(constant) or better represented by o(1).
teacher: i think you are now out of doubt.
student: what if somebody ask me the defination of hashing
teacher: hashing = hash +ing
teacher: just told him that hash is a pure form of GANJA (english:weed)

 

THE BASIC IS THAT KEY ITSELF IS USED AS ADDRESS.IN OUR CASE THE KEY IS dumb_***

 

The basics of hashing is to apply a function to the search key so we can determine area the account is after searching at the added items. To accomplish the table of reasonable size, we have to acquiesce for collisions, two audible keys mapped to the aforementioned location.