For a small amount of short keys hash tables perform worse than a simple linear scan. 127 is a good number but it depends on the design.
O(1) is completely missing the point of hidden constant factors. For many applications, like the one used in javascript, ruby or perl - map as objects with 3-7 short keys - hash tables are totally overblown.
For compile-time known keys you better create a perfect hash table, where the fastest could be a switch of pre-compiled word-aligned memcmp statements. http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-an...
Haven't done that yet with SIMD instructions, which should be much faster.
For mostly read maps (like e.g. for mysql applications) it's mostly faster to run-time compile a shared lib with a perfect hash table. Compilers are very fast with data-only.
For many other use cases a judy tree, compressed patricia tree, ctrie, HAMT, CHAMP or even a btree may be faster than a typical hash table. Esp. considering cache oblivious architectures.
The modern swiss table doesn't look like an old-style hash table anymore, more like a patricia tree.
E.g. almost everything is faster than the default C++ hash table.
O(1) is completely missing the point of hidden constant factors. For many applications, like the one used in javascript, ruby or perl - map as objects with 3-7 short keys - hash tables are totally overblown.
For compile-time known keys you better create a perfect hash table, where the fastest could be a switch of pre-compiled word-aligned memcmp statements. http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-an... Haven't done that yet with SIMD instructions, which should be much faster.
For mostly read maps (like e.g. for mysql applications) it's mostly faster to run-time compile a shared lib with a perfect hash table. Compilers are very fast with data-only.
For many other use cases a judy tree, compressed patricia tree, ctrie, HAMT, CHAMP or even a btree may be faster than a typical hash table. Esp. considering cache oblivious architectures. The modern swiss table doesn't look like an old-style hash table anymore, more like a patricia tree.
E.g. almost everything is faster than the default C++ hash table.