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.
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
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
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)
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];
}
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]);
}
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)]);
}
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)
