Re: thought on Lua's hash-table invariants

[Robert Burke <sharpobject@...>]

On Wed, Apr 22, 2020 at 3:30 AM Roberto Ierusalimschy
<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')?

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?

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