lua-users home
lua-l archive

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

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.