Re: Lua hash algorithm

[RLake@...]

A couple of things I forgot about yesterday:

1) The comment about constant-limited hashing only applies if the length of
the string is known. Null-delimited c strings (which are high on the list
of "what's wrong with c") impose an O(n) time on almost any string
algorithm.

2) Hashing of numbers in Lua is problematic. It really only works for
integers which could fit in an "int" (or "unsigned int"). There has been
some discussion about the issue of Lua crashing on a floating point
exception for hash keys outside of this range (for what it's worth, I
experienced this problem on FreeBSD in various versions, although v. 4.6
seems to be less fascist about floating point conversions.)

The hash algorithm converts any number to an integer. So 1.25, 1.5 and 1.75
all hash to the same value. (This does not trigger an FPE, at least.) In
the following code, the table lookup is essentially linear (untested, by
the way):

local epsilon = 2 ^ -20
for x = epsilon, 1, epsilon do
   a[x] = some_function(1 + x)
end

I suppose that people don't think of such code because of fears about the
imprecision of floating-point numbers. But the above numbers are perfectly
precise.