Re: thought on Lua's hash-table invariants

[Roberto Ierusalimschy <roberto@...>]

>  > I spent a bit of time worrying that in use cases where many keys are
>  > inserted and removed from a table while the size of the table remains
>  > more or less the same, like the hash table attached to a heap that
>  > supports update-key in A* or Dijkstra or an LRU cache, the performance
>  > may degrade. My mind was put at ease when Roberto shared that all this
>  > won't matter anyway, because for use cases like these the table will
>  > be regularly rehashed even if it does not change size.
> 
> What triggers the rehash?  Is it the movement of the `lastfree` pointer?

Yes. 'lastfree' only moves in one direction (from the end of the table
to its beginning). Although it may have to skip several slots to find
a free one, the amortized cost is O(1), as it will pass N slots to
insert N keys. When 'lastfree' hits the beginning of the table, and
therefore it cannot find a free slot, there is a rehash.

When doing a rehash, Lua counts the number of slots actually in use,
that is, with non-nil values, and computes the new size for the table.
(That computation includes the size of the array part, too.) This
new size can be larger (the typical case), smaller, or equal to the
previous size. After the rehash, 'lastfree' is reset to the end of
the table abain.

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