lua-users home
lua-l archive

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

"In handling resources, strive to avoid disaster rather than to attain an optimum." (Butler Lampson)

Alternatively, as I suggested in an earlier post to this thread, you
can use self-balancing trees like RB-tree to resolve collisions
instead of lists when lists get larger.

I like this approach, and I've used it before for symbol tables, using a fixed number of hash buckets. You get good performance for normal cases, and it only deteriorates to O(log(N)) for degenerate cases. I used treaps, not read-black trees, but the principle is the same.