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!
attias 0 Newbie Poster
Narue 5,707 Bad Cop Team Colleague
>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.
boattraveller78 0 Junior Poster in Training
Yes, a hash table is just like a complicated array.
jk451 0 Newbie Poster
>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).
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.