Re: thought on Lua's hash-table invariants

[Roberto Ierusalimschy <roberto@...>]

> Got it!  But if I understand correctly, this happens only if a removal
> is followed by an insertion.   It would be interesting to think about
> the probability of such an event.  A new node has to hash to the
> position previously occupied by a removed node.  If there is a long
> sequence of remove/insert operations with different keys, I wonder if
> short chains could eventually merge to become long ones (as the
> overall size doesn't change)?

Note that the 'lastfree' field only moves forward. So, to have this
worst case cenario, *all* insertions must match a previouly freed
slot. Each insertion that collides needs to find a free slot, and
therefore moves 'lastfree' forward. Eventually 'lastfree' reaches the
end of the table (actually its beginning) and there is a rehash,
clearing everything.

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