Also someone in this list suggested a possibly better prime (not Mersenne) than 0xAAAB, which was just selected by a small manual incremental search with some properties.
As the list of all 16-bit primes is small and known it is easy to assert and finally check with a long enough lists of words of the same length that are full hashed (not sampled), generated from a sequence: this can be used to evaluate the various primes (or we could just use the primes listed by Knuth, none of them are Mersenne as they have randomized distribution of bits 1 and 0, without any overlong sequences of 1s or overlong sequences of 0s).
Common usage patterns for Lua tables will use for example timestamps, GUID (limited to 16 bytes), or SHA1-computed strong hashes (e.g. identification of arbitrary files by their content), or IPv6 addresses (128-bit, i.e. 16 bytes if indexed as
binary-packed strings), or IPv4 addresses (4 bytes when packed in binary strings).
Your test is suitable for indexing filenames, or common field names/variable names in objects (including for example ISO 639 or BCP-47 language codes in tables of translations with many codes of the same length 2 or 3)
For small objects with few keys like {x=2, y=3}, hashing is not significant as possible collisions have no significant effect:
Using a hash table for these small tables is even unnecessary, up to keys could be kept in a single array (e.g.
less than about 16 keys), and even kept sorted for lookups by binary search of their hash values (the cost is when adding/removing keys in random hashvalue order, but on average it will not "slide" a lot of keys in the array by memcpy() for insertion or deletion: less than 16 keys to move on average, and rarely, 0 keys to move at best and 31 keys at most): the binary search however would have to take into account possible duplicate hash values (so when dividing the range in two "equal" parts with a central position, you have to scan some positions forwards and backwards as long as they have the same hash value before subdividing again):
This would be the first step before extending the sorted scheme, to create a B-tree (with pages of 16 keys for example) for larger tables, with a warrantied O(log(tablesize/pagesize)*log(pagesize)) access time and a warrantied O(tablesize)
space used (so never with any critical worst case): correctly balanced B-trees have a minimum and maximum fill level for all pages, except the root page which may have less keys,
and all leaf pages are at the same depth
(these levels are tunable even at runtime for specific tables: if you want fewer reorganizations during insertion/deletion, you can use a low minimum at 50% instead of the common 85% level; the maximum does not be set to something else than 100%, unless you want to prepare the table at a reasonnable depth for some later insertions when splitting/merging the nearest sibling pages at the same depth, preferably those with the same parent page as it avoids the recursive splitting/merging of the parent page with its own nearest siblings).
