[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: thought on Lua's hash-table invariants
- From: Robert Burke <sharpobject@...>
- Date: Wed, 22 Apr 2020 17:23:29 +0900
On Wed, Apr 22, 2020 at 3:30 AM Roberto Ierusalimschy
> > - 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.
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?
lua-l mailing list -- firstname.lastname@example.org
To unsubscribe send an email to email@example.com