New hash function for integer keys

When integer keys do not form a sequence, it is better to use all their
bits to compute their hashes. (The previous implementation was quite bad
for integer keys with common lower bits, and disastrous for integer keys
changing only in their upper 32 bits.)

1 files changed, 14 insertions, 2 deletions

diff --git a/ltable.c b/ltable.c
index 33c1ab30..af878368 100644
--- a/ltable.c
+++ b/ltable.c
@@ -84,8 +84,6 @@
 #define hashstr(t,str)          hashpow2(t, (str)->hash)
 #define hashboolean(t,p)        hashpow2(t, p)
 
-#define hashint(t,i)            hashpow2(t, i)
-
 
 #define hashpointer(t,p)        hashmod(t, point2uint(p))
 
@@ -101,6 +99,20 @@ static const Node dummynode_ = {
 static const TValue absentkey = {ABSTKEYCONSTANT};
 
 
+/*
+** Hash for integers. To allow a good hash, use the remainder operator
+** ('%'). If integer fits as a non-negative int, compute an int
+** remainder, which is faster. Otherwise, use an unsigned-integer
+** remainder, which uses all bits and ensures a non-negative result.
+*/
+static Node *hashint (const Table *t, lua_Integer i) {
+  lua_Unsigned ui = l_castS2U(i);
+  if (ui <= (unsigned int)INT_MAX)
+    return hashmod(t, cast_int(ui));
+  else
+    return hashmod(t, ui);
+}
+
 
 /*
 ** Hash for floating-point numbers.