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

[Leo Razoumov <slonik.az@...>]

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.

--Leo--