[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: stringtable and Table Hashing
- From: "Wim Couwenberg" <wcou@...>
- Date: Wed, 2 Jun 2004 10:19:27 +0200
> ... 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.)