stringtable and Table Hashing

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

	Hiyas, I`m trying to figure out how hashing was implemented for Lua.
Unfortunately I'm stuck with using Lua4.1alpha until my project is over so
things might have changed in more recent versions.  But from a quick look at
Lua 5.0.2 it seems to still be working the same way.

	As far as I can figure out, the hashing method for the string table
is an array that contains lists of TString*.  So if 2 hash numbers map out
to the same array index they will be chained in that index.  This seems to
me to be a standard and "good" way to do it.

	For the Tables ( Hash in lua 4.x ), the hash number maps out to an
index in the node aray, we 1. Move the colliding node to the "firstfree" pos
that starts at the end of the array and will go downwards, then place our
node at the proper index.  OR 2. We place our node at the "firstfree" which
is at the end of the array.

	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".  This does not seem to be
as efficient as the method used for the string table.  I don't see the
advantage of doing it this way instead of using lists to resolve
collisions... Also I`m wondering why there are 2 different hashing
behaviors?
	
	I guess I must be missing some info or not understanding something
corectly... can someone try to explain this to me, or point me to a link
where it's explained.

	Thanks,
	Yann Com-Nougué