Re: stringtable and Table Hashing

[Wim Couwenberg <debosberg@...>]

> When geting an item in the Table(Hash) we look at
> the index where it
> "should" be based on the hash number, and if it's
> not there we traverse the
> complete array starting from our "main position". 

Not the complete array is traversed, only the (tail
of) the hash bucket chain starting at the main
position. Note that this chain might actually belong
to a different hash value! 

As stated in the comment at the top of ltable.c the
Lua hash table is based on an idea of Brent that has
very good hash table access characteristics compared
to some other scatter table algorithms:

http://web.comlab.ox.ac.uk/oucl/work/richard.brent/pd/rpb013.pdf

--
Wim



	
		
__________________________________
Do you Yahoo!?
Friends.  Fun.  Try the all-new Yahoo! Messenger.
http://messenger.yahoo.com/