Hash algorithm (for hashmap, strings, etc.)

[dumblob]

There was a request to use a better hash function for strings. I don't think it's necessary, but for a hashmap, it already matters a lot. There are also other possible use cases in V as well as just having a high quality (passes SMHasher and other tests) hash function standalone in V lib (maybe a template for strings, ints, floats, and arrays of all these primitive types).

I was waiting with this request for half a year to let the best known hash function (which passes all the quality criteria incl. speed) mature. I think time came, so let me introduce wyhash v4. I'm not sure though how the V variant will perform as if there won't be any intrinsics used (e.g. through conditional compilation $if ! js { /* let's use intrinsics */ }), the speed will unnecessarily degrade.

[medvednikov]

It uses Java's hash function, which is pretty battle tested :)

[dumblob]

It uses Java's hash function, which is pretty battle tested :)

I suppose you're referring to string. I'm OK with string using the simple hash (even though it's slower than the proposed wyhash and has way lower quality). My proposal is about a universal hash in V stdlib. Such hash shall be crossplatform-stable (i.e. on little/big endian, on x86/ARM, etc. always the same results) and very fast (both for very short inputs as well as for very long inputs - though short inputs are slightly more important).

As I wrote, I'd also like to see wyhash in the V hashmap. Speaking about Java, it uses it's built-in hash() function which is JRE-specific and has very bad quality (see how it's implemented e.g. in OpenJDK) - therefore also proposal JEP draft: Better hash codes proposing actually still worse hash functions than wyhash (but way better than the current hash() and than the hash used for string hashing: for i := 0; i < s.len; i++ { hash = hash * int(31) + int(s.str[i]) }).

[ka-weihe]

We have been working on putting wyhash in the hashmap. It currently uses FNV1a, but if wyhash provides an improvement it will naturally be the hash-function in the hashmap. And I agree, dbj2 hash (the current string hash) should not used. It has a lot of collisions and biased hashes.

[ka-weihe]

The hashmap is now using wyhash4 as the default hash-function a14a5fb.

This issue can be closed.

[joe-conigliaro]

a14a5fb

[dumblob]

One small change from the hash author making it few percent faster: rurban/smhasher#96 (comment)

[dumblob]

Feel free to update wyhash as the newest version solves one potential security issue and is even a tiny bit faster than the previous versions 😉.

[ka-weihe]

We are working on it 🙂

[dumblob]

No need to hurry - it's just a reminder to not forget about it before next release.

[dumblob]

New version of wyhash got released (it shall fix the bad seeds issue and couple of others).

See also #9553 (comment) and rurban/smhasher#243 .