No hash function is perfect, but some are useful.
wyhash and wyrand are the ideal 64-bit hash function and PRNG respectively:
solid: wyhash passed SMHasher, wyrand passed BigCrush, practrand.
portable: 64-bit/32-bit system, big/little endian.
fastest: Efficient on 64-bit machines, especially for short keys.
simplest: In the sense of code size.
wyhash is the default hasher for a hash table of the great Zig, V and Nim language.
Simple Example:
#include "wyhash.h"
string s="fcdskhfjs";
uint64_t h=wyhash(s.c_str(),s.size(),0,_wyp);
g++-9 benchmark.cpp t1ha/src/t1ha2.c -o benchmark -Ofast -s -Wall -march=native
/usr/share/dict/words
hash function | short hash/us | bulk_256B GB/s | bulk_64KB GB/s |
---|---|---|---|
wyhash_final2 | 205.45 | 21.09 | 25.15 |
wyhash_final1 | 195.42 | 17.97 | 23.44 |
xxh3:avx2 | 147.33 | 9.73 | 45.39 |
xxh3:sse2 | 154.30 | 11.53 | 27.15 |
xxh3:scalar | 153.61 | 8.49 | 13.05 |
xxHash64 | 83.10 | 10.89 | 14.72 |
t1ha2_atonce | 115.12 | 12.96 | 17.64 |
benchmarking random size inputs [1-N] :
wyhash_final_2 , 460285061, 460321195, 460326704, 523971210, 589086019, 604722907, 621467661, 637449707, 652477835, 677025996, 681841441, 690852822, 690795369, 677118854, 708352741, 695829415, 681979855, 669038895, 647841020, 635435174, 624761233, 608436505, 596167728, 607634683, 596286528, 578279374, 586815217, 569988710, 563390716, 553515233, 562590641, 556485454, 548322810, 534633085, 524666972, 506698015, 518753786, 511688816, 491668139, 488508188, 482637257, 486158659, 479140634, 468260366, 476705359, 457339169, 455983878, 458531907, 446537256, 448179585, 437260235, 435774636, 436323210, 423798490, 423673513, 422865936, 414959101, 407922401, 399215200, 403119135, 397282522, 396687117, 399490974, 393969926, 390520502, 383932626, 381930801, 387972705, 374491915, 360941602, 370835220, 352384040, 359840650, 364645240, 347051926, 355327083, 344091413, 345941775, 354136643, 339470155, 331810472, 337654036, 333150933, 322758418, 328604867, 318729669, 327638387, 319337114, 303533881, 316587913, 315723811, 304694634, 307033672, 297682113, 302531713, 305579191, 306936662, 303791505, 302534356, 294426637, 293853712, 284420494, 288688941, 280371293, 287206945, 281151640, 285670624, 279656674, 270278392, 268002490, 276808538, 270678867, 272508536, 269092479, 267416114, 268448470, 263096349, 265313084, 263051200, 250612259, 255996307, 249706951, 255121573, 244234595, 245078240, 249779778, 245994223
wyhash_final_1 , 459650712, 459652136, 459654365, 493353916, 542751562, 566135148, 582101758, 595314929, 617032915, 615474974, 613632219, 607712805, 600627321, 596196545, 598863223, 575499026, 577347625, 537658054, 514464444, 512764844, 501734461, 481431878, 487928001, 484220739, 469181287, 454967201, 449590120, 452667058, 439151005, 449422008, 444462746, 441070074, 426244387, 404420283, 404707606, 402571822, 407862811, 394977880, 381118633, 386249963, 375861763, 380270200, 373238813, 365789520, 376763534, 353723845, 354649310, 356513054, 337930507, 330819080, 337486257, 333801301, 336471551, 327941637, 324099756, 328882493, 322687466, 314295127, 303262154, 314938909, 307251002, 307833955, 302064571, 305729415, 297150491, 288829606, 291584605, 298142902, 284223896, 279758494, 288672594, 276245080, 280605535, 280078455, 272299999, 279512481, 271948621, 269325551, 279740757, 261846564, 258677847, 265491362, 262512131, 255227722, 261358059, 250374021, 254744766, 250714905, 243480258, 244097089, 248051864, 238801740, 242301951, 234779060, 236506361, 237074089, 237037516, 227910218, 233674458, 221743976, 225871485, 222062717, 222098749, 211221976, 218572723, 209997561, 218875895, 215387080, 204070708, 200276676, 206792163, 201406023, 202980302, 204025887, 198565422, 194673888, 188335430, 195442050, 196381988, 186110762, 187124837, 186214935, 192368587, 184464279, 175094655, 180768108, 175243607
XXH3_avx2 , 307078136, 307014216, 305839386, 219537363, 182831759, 182018448, 176271606, 185800098, 252371671, 279432683, 285709243, 298737893, 300174849, 305271954, 296934641, 319858252, 352309064, 333177207, 333511331, 327444664, 326052217, 311594117, 307973133, 314623950, 303757273, 295405084, 295198703, 290662107, 292845050, 287938130, 286478076, 280962919, 281883926, 274396444, 271893735, 259421586, 267496195, 263156335, 257704964, 254230756, 245903090, 249869594, 245094381, 235668075, 244758397, 232689991, 230962584, 230564772, 229323509, 226453451, 223205736, 225065505, 224512148, 222181649, 222435635, 222218925, 219257719, 212841666, 210845321, 216341695, 212542957, 207327345, 210208178, 208923620, 205833181, 207326864, 205627565, 208098921, 198783860, 198951030, 201147450, 196183156, 195124698, 196416930, 190813512, 194715332, 188070060, 191113996, 192781117, 185440500, 184411299, 187795422, 187357523, 182925968, 187424718, 183034874, 184349482, 181824096, 179692605, 181748773, 180565103, 179245338, 177608692, 175290713, 175978460, 178594505, 176357899, 176264290, 175129154, 173712912, 174215249, 171658067, 171560188, 164965705, 168837231, 167839877, 165352386, 163801617, 160957084, 159581680, 161147099, 158460072, 161581182, 158951416, 158421447, 159357930, 155447802, 158962650, 157358577, 150646182, 155318648, 151018574, 152772233, 152000000, 150514137, 151064767, 148168633
C# https://github.com/cocowalla/wyhash-dotnet
C++ https://github.com/tommyettinger/waterhash
GO https://github.com/dgryski/go-wyhash
GO https://github.com/orisano/wyhash
GO https://github.com/littleli/go-wyhash16
GO https://github.com/zeebo/wyhash
GO https://github.com/lonewolf3739/wyhash-go
GO https://github.com/zhangyunhao116/wyhash (final version 1)
Java https://github.com/OpenHFT/Zero-Allocation-Hashing
Nim https://github.com/nim-lang/Nim/blob/devel/lib/pure/hashes.nim
Nim https://github.com/jackhftang/wyhash.nim
Nim https://github.com/littleli/nim-wyhash16
Rust https://github.com/eldruin/wyhash-rs
Swift https://github.com/lemire/SwiftWyhash
Swift https://github.com/lemire/SwiftWyhashBenchmark
Swift https://github.com/jeudesprits/PSWyhash
V https://github.com/vlang/v/tree/master/vlib/hash/wyhash (v4)
Zig https://github.com/ManDeJan/zig-wyhash
absl hashmap https://github.com/abseil/abseil-cpp/blob/master/absl/hash/internal/wyhash.cc
I thank these names:
Reini Urban
Dietrich Epp
Joshua Haberman
Tommy Ettinger
Daniel Lemire
Otmar Ertl
cocowalla
leo-yuriev
Diego Barrios Romero
paulie-g
dumblob
Yann Collet
ivte-ms
hyb
James Z.M. Gao
easyaspi314 (Devin)