https://stackoverflow.com/questions/22899172
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianwhat would the best case and worst case be for a hashtable with chaining?
Find, insert, delete operation best time is O(1) or constant time. For worst time,
- insert: O(1), assuming chaining is done by just adding to the end of chain
- delete: O(k), with k = number of elements on the longest chain. k == n when the hashing function is very poor and all n values map to same entry and gets chained. So, the absolute worst case is O(n).
- find: O(n), using the same reasoning as delete
How would I differentiate the two if given two mystery data structures?
Just an idea:
- Insert data in both structures and plot the insertion time for the insertion operation vs n. Choose the data to make the mimic the worst case for AVL tree (i.e. if integers, insert in the order 1000000, 99999, 999998...) but not for the hashtable.
- Notice the plot being generate. The AVL tree one will have insertion time log(n) from the beginning while this should be fairly constant for hashtable. Around the 1000th insertion ALV tree will take 10 times longer for insertion (assuming worst case insertion happening). But insertion time should be almost same as before for hashtable. Assuming the hashtable has enough capacity and hashing function is not silly enough to get conflicts with sequential data like '1000000, 99999, 999998...'
- If still not sure, then bombard both structure with insertion, hoping to fill up hashtable and force it to start chaining. After many insertions, notice the plots. AVL will still maintain log(n) curve, but hashtable will show different curve, like: constant time with higher constant value.
