4 ms·

It's "fast" and "strong"? No measurements are given other than one informal speed comparison against murmur64. What is the goal, and where's the comparison, re

It's "fast" and "strong"? No measurements are given other than one informal speed comparison against murmur64. What is the goal, and where's the comparison, relative to xxhash, siphash, highwayhash? https://en.wikipedia.org/wiki/List_of_hash_functions#Non-cryptographic_hash_functions https://en.wikipedia.org/wiki/List_of_hash_functions#Non-cry... I'm not sure what the point of the blog post's universal hash functions is, within the domain of practical software engineering. Who's the audience, programmers or number theorists? Who's going to implement this, and how are they going to choose (or write a function to randomly choose) a, b, and c to give at least adequate properties for their task?

stochastic_monk 8y ago
Lemire has done a lot with fast universal hashing (see clhash, for example). I’m somewhat surprised by this post. Normally he’s a lot more clear about exactly how fast and what kinds of guarantees he has. I just don’t think this is that exciting of a post.
CodesInChaos 8y ago
It's not "strong", it's "strongly universal", which is a well defined mathematical property. Universal hash functions are the basis of MAC part of popular authenticated encryption algorithms, like GCM and ChaCha-Poly1305 (though for this purpose 128-bit tags are preferred). Though I don't see what the point of this particular implementation is, with its hardcoded keys and fixed 64-bit inputs instead of a random secret key and variable length inputs.
- stochastic_monk 8y ago
  Because it’s hashing an item of fixed size. This is specialized for 32 or 64-bit integers. clhash supports arbitrary length strings. There is a performance cost for that generality. For example, in my experiments, clhash is 1/3 as fast as murmurhash or Wang’s 64-bit hash for 64-bit integers.

4 ms·

It's "fast" and "strong"? No measurements are given other than one informal speed comparison against murmur64. What is the goal, and where's the comparison, re

by harshreality 8y ago

stochastic_monk 8y ago
Lemire has done a lot with fast universal hashing (see clhash, for example). I’m somewhat surprised by this post. Normally he’s a lot more clear about exactly how fast and what kinds of guarantees he has. I just don’t think this is that exciting of a post.
CodesInChaos 8y ago
It's not "strong", it's "strongly universal", which is a well defined mathematical property. Universal hash functions are the basis of MAC part of popular authenticated encryption algorithms, like GCM and ChaCha-Poly1305 (though for this purpose 128-bit tags are preferred). Though I don't see what the point of this particular implementation is, with its hardcoded keys and fixed 64-bit inputs instead of a random secret key and variable length inputs.
- stochastic_monk 8y ago
  Because it’s hashing an item of fixed size. This is specialized for 32 or 64-bit integers. clhash supports arbitrary length strings. There is a performance cost for that generality. For example, in my experiments, clhash is 1/3 as fast as murmurhash or Wang’s 64-bit hash for 64-bit integers.