Hash function implementations in JavaScript

March 17, 2019 · View on GitHub

I've ported a bunch of hash functons to JS. These are all highly optimized for speed, and make use of ES6 features like Math.imul and default parameters. Sadly, only algorithms made for 32-bit architectures get good performance in JS. Emulating 64-bit math can decrease performance by 80-90%.

Also see: CRC functions

32-bit

AlgorithmHash sizeSpeedNotes
CRC-3232-bit147/575For speed reference (it's pretty slow)
FNV32-bit3041/2649variants: FNV-0, FNV-1, FNV-1a, FNV-1a_BM
MurmurHash132-bit3296/2822Original version. Super fast.
MurmurHash232-bit3027/2518aka MurmurHash2_x86_32
MurmurHash2A32-bit3053/2484Fixes a flaw in MurmurHash2. Uses Merkle–Damgård construction.
MurmurHash332-bit3090/2515aka MurmurHash3_x86_32
xxHash32-bit2968/2492not as fast as you'd think, but still good
SuperFastHash32-bit-/-Higher collision rates in some cases: 90 of 131072
(vs. Murmur3=0, Lookup2=2, Lookup3=3, xxHash=4)
Marvin3232-bit-/-Obscure function, but seems decent. Almost as fast as MurmurHash3.
CityHash3232-bit-/-The only 32-bit variant in Google's City/Farm families. Not recommended, it's just a slower Murmur3 clone.
FunnyHash3232-bit-/-Yet another 32-bit hash.

64-bit or higher

AlgorithmHash sizeSpeedNotes
Lookup2_x8632-bit2412/1985(Obsolete) 32-bit. 64/96-bit is possible but with worse statistics.
Lookup3_x8632/64-bit2553/103832 or 64-bit. 96 is possible but with weaker statistics.
MurmurHash2_x86_6464-bit2759/2406Slightly modified to avoid a flaw in the original, see comments.
MurmurHash3_x86_128128-bit2498/2162Modified version. Contains a possible flaw, see comments.
MurmurHash2_160160-bit1968/1590Unofficial mod that outputs five 32-bit hash states.
HalfSipHash32/64-bit-/-32-bit version of SipHash. Can output a 64-bit hash. Kind of slow.

Performance notes

Legend (for Speed): 256 / 31488 (InputLength)

These numbers don't really mean much, just a quick comparison. They're all pretty fast. My fastest table CRC-32 is still ~75% slower than MurmurHash2_160, which is the slowest in the table above.

  • MurmurHash3_x86_128 seems really fast considering it outputs 4 hashes, possibly one of the best choices for >32-bit.
  • MurmurHash1 is fastest 32-bit hash in JS. MurmurHash3 and xxHash are also very good for high quality hash.
  • If xxHash can be modified to properly mix v0-v4, this might be an efficient hash >32-bit.
  • lookup2 produces 3 hahses, but its quality is only ensured for one of them.
  • lookup3 is faster for 256, but is REALLY SLOW for 31488 (investigate). Unlike lookup2, its quality is ensured for 64-bit.
  • I cannot recommend MurmurHash2_x86_64 because of its flaw, and my modification that attempts to fix it needs to be benchmarked.
  • MurmurHash2_160 is only one more 32-bit hash larger than MurmurHash3_x86_128 but is quite slower. And cannot downscale without possibly hurting quality.
  • CybBeta2 is my custom 64-bit hash. Decent speed, but not much faster than MurmurHash2_x86_64 and has untested hash quality.
  • CybBeta0 is my custom 32-bit hash. Only slightly faster than MurmurHash1 and has untested hash quality.

Emulated 64-bit hash functions

I will put ports of 64-bit arithmetic hash functions here, but expect them to be extremely slow. If WebAssembly becomes viable that can be useful for 64-bit hash functions. BigInt does not currently seem to be a performant option.


Misc benchmarks