lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On Fri, Dec 30, 2011 at 2:31 PM, Leo Razoumov <> wrote:
> On Thu, Dec 29, 2011 at 13:58, Peter Cawley <> 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.