Interview Question
Country: India
Interview Type: Phone Interview
hash table relies on the hash function so that hash function should ensure the uniformity of all the keys into all the hash positions...
hey eugene,
if the hash function is not good, then there will be a lot of collisions and would increase the complexity to O(n) if you use linked list as chaining. However, if you use something like B+/AVL/RB Tree instead of a linked list, then hashtable might work, however this is assuming that your hash function is uniform, otherwise, you wont get any improvement.
That doesn't mean we can't use a hash table -- just means we have to make a good hash function.
"However, if you use something like B+/AVL/RB Tree instead of a linked list, then hashtable might work, however this is assuming that your hash function is uniform, otherwise, you wont get any improvement."
Really not sure I'm following you there. Are you saying that we should use B+ trees as a *collision resolution mechanism*?
AVL Trees
- Anonymous November 10, 2012