Trying to figure out how hashing and universal hashing works!
If I understand correctly, the main concept of hashing is using a function (the hash function) to "produce" a number out of a string.
This number is the index number for the array which will store the string. If you ever want to lookup for that string the hash function will get you to the correct place in no time (or to be precise in constant time :p).
You can also save memory that way.
If the above is correct I cannot figure out how universal hashing works!
From what I understand, you pick a random hashing function from a set of functions and hash the key with that function.
So when you lookup for that key afterwards how can you know that it will be pick the hashing function that was used on "creation"?
It probably doesn't work that way but that's what I understood:P
Question
gian
Hello people,
Trying to figure out how hashing and universal hashing works!
If I understand correctly, the main concept of hashing is using a function (the hash function) to "produce" a number out of a string.
This number is the index number for the array which will store the string. If you ever want to lookup for that string the hash function will get you to the correct place in no time (or to be precise in constant time :p).
You can also save memory that way.
If the above is correct I cannot figure out how universal hashing works!
From what I understand, you pick a random hashing function from a set of functions and hash the key with that function.
So when you lookup for that key afterwards how can you know that it will be pick the hashing function that was used on "creation"?
It probably doesn't work that way but that's what I understood:P
Thanks for the help
Link to comment
Share on other sites
0 answers to this question
Recommended Posts