Monthly Archives: June 2018

Milan skies after fires in the alps, 2018

Hash functions – efficency and speed

hash function is any function that can be used to map data of arbitrary size to data of a fixed size. The values returned by a hash function are called hash valueshash codesdigests, or simply hashes. Hash functions are often used in combination with a hash table, a common data structure used in computer software for rapid data lookup.

If you happen to need a non cryptographic hash function (and you might need it even if your are using languages that have builtin hashtables like java or c++ ) here are some references taken from various parts:

Interesting comparison of different hash tables :

http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

Some more hash functions here :

http://www.cse.yorku.ca/~oz/hash.html

Some really interesting benchmarks strchr.com/hash_functions by Peter Kankowsky.

And again hash benchmarks sanmayce.com/Fastest_Hash/.

Hash benchmarks in Rust by https://medium.com/@tprodanov/benchmarking-non-cryptographic-hash-functions-in-rust-2e6091077d11

And more benchmarks : https://medium.com/logos-network/benchmarking-hash-and-signature-algorithms-6079735ce05

Some (a mininum set) benchmarks ran using random keys of random len, 1.5 multiply factor on hash size, next power of 2 hash sizes :

Tests are run on random keys
--- hash_function speed on random long (100-350) keys
Keys    HashFunc         HashSize AvgTime(ns) Collisions LongestChain DimFactor
1000000 djb_hash         4194304    191.03      110620    6            1.500000
1000000 murmur64a_hash   4194304    60.87       110830    7            1.500000
1000000 wyhash_hash      4194304    36.69       110170    5            1.500000
1000000 elf_hash         4194304    444.25      110488    5            1.500000
1000000 jen_hash         4194304    143.90      110471    5            1.500000
1000000 djb2_hash        4194304    189.63      111048    6            1.500000
1000000 sdbm_hash        4194304    247.92      110087    6            1.500000
1000000 fnv_hash         4194304    247.87      110170    6            1.500000
1000000 oat_hash         4194304    309.55      110538    6            1.500000

--- hash_function speed on short keys (10 to 45 char len)
Keys    HashFunc        HashSize AvgTime(ns) Collisions LongestChain DimFactor
1000000 djb_hash         4194304    31.14       110363    6            1.500000
1000000 murmur64a_hash   4194304    28.24       110264    6            1.500000
1000000 wyhash_hash      4194304    21.84       109798    5            1.500000
1000000 elf_hash         4194304    49.88       110845    5            1.500000
1000000 jen_hash         4194304    33.28       110541    5            1.500000
1000000 djb2_hash        4194304    31.21       110664    6            1.500000
1000000 sdbm_hash        4194304    35.60       109906    6            1.500000
1000000 fnv_hash         4194304    35.59       109940    6            1.500000
1000000 oat_hash         4194304    43.28       110123    6            1.500000

Tests done with the hash table code you can find github.com/paulborile/clibs

And last a research study for SIMD optimized hash functions : arxiv.org/pdf/1612.06257.pdf  some theory and code github.com/google/highwayhash/blob/master/c/highwayhash.c. The all use the vector extensions present in gcc.