Re: thought on Lua's hash-table invariants

[Roberto Ierusalimschy <roberto@...>]

> <roberto@inf.puc-rio.br> wrote:
> > >   - When a key-value pair (k, v) is added, if its main spot is
> > >     occupied by key-value pair (k', v'), and if k and k' hash to
> > >     different spots, then the main spot is overwritten with (k, v),
> > >     and (k', v') is added.
> >
> > Right.
> 
> Is the chain that the node was previously a part of modified by the
> removal of (k', v')?

No. As I said in that other message, a removal does not change anything
in a table. It only sets the node's value to nil, so that it can be
reused by another key that hashes to that node (or by the same key,
if it is reinserted). Only rehashes actually clear previous removals.
(But removals also do not trigger rehashes.)


> One desirable property for a scatter table that's used in a "hot use"
> way (so first some keys are added, then after that keys are queried or
> modified but not removed) is that total number of non-null next
> pointers is equal to the number of colliding elements. So if a user
> inserts 4 elements that hash to slot 1 and 1 element that hashes to
> slot 2, the number of colliding elements is 3. Is the number of
> non-null next pointers guaranteed to be 3 there?

Yes. Without removals, chains do not merge. Each chain contains exactly
the keys colliding to its first node.

-- Roberto
_______________________________________________
lua-l mailing list -- lua-l@lists.lua.org
To unsubscribe send an email to lua-l-leave@lists.lua.org