Re: stringtable and Table Hashing

["Wim Couwenberg" <wcou@...>]

> ... the hashing of
> tables (in ltable.c) uses probing to resolve collisions.

I think you mean the search for a free node (when relocating / adding a
node)?  However the `firstfree' member of a hash table descends the node
array *only once*  (it is only decremented.)  Therefore it takes amortised
constant time to find a free position.  If no free nodes remain (and only
then) the table is rehashed and the `firstfree' member is reset to the top
of the node array.  Note that a key with a nil value is kept in the hash
table until the next rehash (i.e. it is not a free node).

(NB: Nodes with equal hash values for their keys are chained (by the `next'
member of a node), so Lua hash tables do use chaining.)

--
Wim