lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

> 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 --
To unsubscribe send an email to