/wyhash

The dream fast hash function and random number generators that passed SMHasher, BigCrush and practrand.

Primary LanguageCThe UnlicenseUnlicense

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)