String hash function looses 2 "bits" per 8 bytes

stclib / STC

A modern, user friendly, generic, type-safe and fast C99 container library: String, Vector, Sorted and Unordered Map and Set, Deque, Forward List, Smart Pointers, Bitset and Random numbers.

MIT License

1.34k stars 73 forks source link

String hash function looses 2 "bits" per 8 bytes #50

Closed funny-falcon closed 1 year ago

funny-falcon commented 1 year ago

https://github.com/tylov/STC/blob/fddae5ef07fc0e9a018e56a9843e059a737e4db7/include/stc/ccommon.h#L144

rot(x,z)^x == rot(~x, z)^(~x)

And rotating even bytes introduces more collisions

m1 = 0x5555555555555555ull;
m2 = 0xaaaaaaaaaaaaaaaaull;
rot(x,26)^x == rot(x^m1, 26) ^ (x^m1) == rot(x^m2, 26) ^ (x^m2);

tylov commented 1 year ago

Hash function changed in unreleased v4.3, closed as not applicable.