Re: Hash Table Collisions (n.runs-SA-2011.004)

[Peter Cawley <lua@...>]

On Fri, Dec 30, 2011 at 2:31 PM, Leo Razoumov <slonik.az@gmail.com> wrote:
> On Thu, Dec 29, 2011 at 13:58, Peter Cawley <lua@corsix.org> wrote:
>>
>> The fundamental messages here are:
>> 1) Inserting N elements into a hash table insertion is O(N^2) worst
>> case (regardless of what particular hash table implementation is being
>> used).
>
> Actually, it is not true. You can use self-balancing trees like
> RB-tree to store elements that hash to the same value. In this case
> insert/search will be O(log(N)) per element and O(Nlog(N)) per
> N-elements. Of course, RB-tree has its own overhead. Therefore, one
> can try an adaptive approach. Whenever a certain bucket becomes too
> large k>Kmax convert it to RB tree, else keep it a list. No
> randomization required.

Once you start merging trees and hash tables, you leave the realms of
what I'd traditionally call a hash table, but I concede your point;
adaptive choice of hybrid algorithms certainly seems like a nicer
solution than randomisation.