Skip to content

Latest commit

 

History

History
77 lines (62 loc) · 5.49 KB

README.md

File metadata and controls

77 lines (62 loc) · 5.49 KB
Raw

Hash function implementations in JavaScript

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

Algorithm Hash size Speed Notes
CRC-32 32-bit 147/575 For speed reference (it's pretty slow)
FNV 32-bit 3041/2649 variants: FNV-0, FNV-1, FNV-1a, FNV-1a_BM
MurmurHash1 32-bit 3296/2822 Original version. Super fast.
MurmurHash2 32-bit 3027/2518 aka MurmurHash2_x86_32
MurmurHash2A 32-bit 3053/2484 Fixes a flaw in MurmurHash2. Uses Merkle–Damgård construction.
MurmurHash3 32-bit 3090/2515 aka MurmurHash3_x86_32
xxHash 32-bit 2968/2492 not as fast as you'd think, but still good
SuperFastHash 32-bit -/- Higher collision rates in some cases: 90 of 131072
(vs. Murmur3=0, Lookup2=2, Lookup3=3, xxHash=4)
Marvin32 32-bit -/- Obscure function, but seems decent. Almost as fast as MurmurHash3.
CityHash32 32-bit -/- The only 32-bit variant in Google's City/Farm families. Not recommended, it's just a slower Murmur3 clone.
FunnyHash32 32-bit -/- Yet another 32-bit hash.

64-bit or higher

Algorithm Hash size Speed Notes
Lookup2_x86 32-bit 2412/1985 (Obsolete) 32-bit. 64/96-bit is possible but with worse statistics.
Lookup3_x86 32/64-bit 2553/1038 32 or 64-bit. 96 is possible but with weaker statistics.
MurmurHash2_x86_64 64-bit 2759/2406 Slightly modified to avoid a flaw in the original, see comments.
MurmurHash3_x86_128 128-bit 2498/2162 Modified version. Contains a possible flaw, see comments.
MurmurHash2_160 160-bit 1968/1590 Unofficial mod that outputs five 32-bit hash states.
HalfSipHash 32/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