Re: ltable.c table deletion

[Doug Currie <doug.currie@...>]

On Jan 31, 2012, at 3:01 PM, Josh Haberman wrote:

> 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.  

From the Lua programmer's perspective, these operations are indistinguishable.

> […]  it occurred to me that Brent's
> variation (evicting a colliding element that is not in its main
> position) prevents chain coalescing

No, it doesn't. Imagine a full hash table with all keys in their main position (perfectly hashed). All chains are coalesced.

> […] I was surprised that Lua didn't
> implement it.

Note that Lua uses explicit chaining (with next fields in the TKey), so chains never coalesce at the expense of one link pointer per hash bucket. 

Something like your idea of deferring the movement of elements to new buckets during deletion can be achieved with "tombstones," see: http://research.cs.vt.edu/AVresearch/hashing/deletion.php

e