1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Basics of Hashing and Why hashing is used ?

Discussion in 'C' started by teacher, Mar 28, 2011.

  1. teacher

    teacher New Member

    Joined:
    Mar 27, 2011
    Messages:
    66
    Likes Received:
    8
    Trophy Points:
    0
    Occupation:
    i hate jobs
    Location:
    india,agra
    Home Page:
    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)
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,285
    Likes Received:
    364
    Trophy Points:
    83
    Nice way to convey a message in an Article.
     
  3. teacher

    teacher New Member

    Joined:
    Mar 27, 2011
    Messages:
    66
    Likes Received:
    8
    Trophy Points:
    0
    Occupation:
    i hate jobs
    Location:
    india,agra
    Home Page:
    THE BASIC IS THAT KEY ITSELF IS USED AS ADDRESS.IN OUR CASE THE KEY IS dumb_***
     
  4. alvisnally

    alvisnally New Member

    Joined:
    May 18, 2011
    Messages:
    4
    Likes Received:
    0
    Trophy Points:
    0
    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.
     

Share This Page