hello,
I have a question about hashtable.
what is the complexity of searching an item in hashtable in average case performance (when using a rehash function)?
thank you!
hello,
I have a question about hashtable.
what is the complexity of searching an item in hashtable in average case performance (when using a rehash function)?
thank you!
>what is the complexity of searching an item in hashtable in average case performance
Amortized O(1). While an individual search might be more expensive, in toto the performance is constant. This is all assuming the hash table is properly implemented, of course.
Yes, a hash table is just like a complicated array.
>what is the complexity of searching an item in hashtable in average case performance
Amortized O(1). While an individual search might be more expensive, in toto the performance is constant. This is all assuming the hash table is properly implemented, of course.
I would say that the last 2 sentences were the answer to "what is the complexity in the average case...".
Note, though, that it is not amortized O(1). That would mean that any sequence of n legal operations during the lifetime of the hash table takes O(n), i.e. amortized complexity is like the normal complexity, except it gives you solid upper bound on a sequence of operations and it is a kind of misleading convention that when saying "amortized O" you give as the argument (upper bound on sequence/# of ops. in sequence).
So, assuming you can create a pathological input sequence for any arbitrary hashtable, even amortized complexity is O(n).