[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: RE: stringtable and Table Hashing
- From: Yann Com-Nougue <ycomnougue@...>
- Date: Wed, 2 Jun 2004 10:20:59 -0400
>> ... 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.