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.)
diff --git a/ltable.c b/ltable.c
index 33c1ab3..af87836 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 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.
