RE: stringtable and Table Hashing

[Yann Com-Nougue <ycomnougue@...>]

>> ... 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.)


	Ok thanks, I see that now.  It does indead chain it.  Originally I
thought that the 'next' of the node was the next index in the array.  I've
got a much clearer picture of what's going on now :)

	Also I profiled the hash lookup collision count on my applic and the
number of nodes traversed in the chains to resolve the collision and I have
an average of 1.4 nodes traversed/collision.  So no worries there.

	Thanks again for the help, It's the first time I really look at
hashing algorithms and I didn't understand it right the first time.

	Yann