# Basics of Hashing and Why hashing is used ?

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

1. ### teacherNew Member

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

Joined:
Jul 12, 2004
Messages:
15,334
377
Trophy Points:
83
Nice way to convey a message in an Article.

3. ### teacherNew Member

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

Joined:
May 18, 2011
Messages:
4