Go4Expert - 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: c++

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: c++

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: c++

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