lua-users home
lua-l archive

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

>From my reading of ltable.c and lvm.c it appears that Lua does not
remove table entries when a program does t[x] = nil, but just sets the
entry's value to nil.  Please correct me if I'm wrong.

Is there a reason for this?  I ask because I'm implementing my own
hash table that uses Lua's design (chained scatter with Brent's
variation) and discovered something that I haven't seen published
anywhere.  All chained scatter removal algorithms I've seen published
are very complicated because they cover the case where chains have
coalesced.  For example:

However, as I was studying this it occurred to me that Brent's
variation (evicting a colliding element that is not in its main
position) prevents chain coalescing, which seems that it would
dramatically simplify the removal algorithm: you can just remove
the target element from its own chain.  This algorithm is so much
simpler and more efficient that I was surprised that I couldn't
find any reference to it, and I was surprised that Lua didn't
implement it.

Am I missing something?