Which hashing algorithm is best for uniqueness and speed?
programmers.stackexchange.com
programmers.stackexchange.com
https://code.google.com/p/smhasher/
Here is the output for some popular hash functions:
For those who are interested, the probability of collision, then size of the hash destination, and the number of objects chosen are related by this formula:
Choosing from N items, with N large, and wanting a
probability T of having no collisions, the number of
items you can choose at random with replacement is:
k ~ sqrt( -2 N ln(T) )
T ~ exp(-(k^2)/(2N))
For example, if you assume your hash will not have collisions, and design your hash table without any mechanism for coping with one, and it happens to have a clash on "Jones" and "Smith", your address book app will become unreliable for a rather large fraction of your users.
It depends a lot on what you're hashing. For strings, both City and Spooky are great. You should benchmark both on your target architecture(s). If you're trying to take, e.g., integers to integers, we've found that CRC32c is a pretty darn good fallback if you need insanely high performance.
If you're running a hash table exposed to externally controlled input, then you also want to consider (whether you need) algorithms that provide decent resistance against "hash flooding". SipHash is the strongest contender there short of throwing your hands in the air and using MD5 with a local secret seed.
http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.h...
I can see trying to prevent data breaches and such, but going so far as to be wary of denial of service attacks from people who have your source code might be wasted effort.
I think most people here don't fall under the umbrella of those who need to consider denial-of-service attacks. When your primary goal should be to launch your product (which you aren't even sure will take off) I would think trying to prevent denial-of-service attacks is a waste of time.
This specific denial of service attack hit a lot of systems in 2012, and all you needed to know was which framework they were using (or just try all of them, as the attack has incredible leverage)
It's as simple as crafting a query-string that results in an O(n²) hashtable building, and allows you to burn minutes of server CPU with each request.
These are problems you only run into if you've got a successful product (which happens very rarely) - and solving these problems before you have users might not be a good allocation of engineering resources for startups.
I liken it to making a system that scales in advance to millions of concurrent users when you haven't even got one.
The fact is it's often difficult to tell the difference between a place where the security properties of the digest algorithm you use are irrelevant, and a place where it might be critical. For example, a zip file uses a CRC32 checksum to validate each file; git uses SHA1 to uniquely identify objects; CouchDB shard mapping uses a strategy based on CRC32... if git had used murmur, would that cause problems for it? Is CouchDB being clever by using a fast hash for sharding at the expense of being secure?
Now, quick, make a decision which algorithm to use to generate Etag headers for your web API HTTP response entities: are you going to go with SHA256 or Murmur2? Murmur2 is much faster, and it's certainly a clever solution... but are you sure you didn't create a security hole?
I'm not saying "nobody ever got fired for choosing SHA256," but I am kind of saying that you have to be very sure you know the security model you're operating in before you build on a hash algorithm that doesn't provide strong extension and preimage resistance.
>>altarage collides with zinke
>>altarages collides with zinkes
I found this most interesting. I have no idea how FNV-1a is constructed but I'm sure this is an interesting (mathematical?) quirk in an otherwise great algorithm since it had only 4 collisions for more than a couple of hundred thousand inputs.
>>playwright collides with snush
>>playwrighting collides with snushing
Since the hash iterates over the characters in the string, once you find two colliding strings S and T, if you append any other string to both S and T, the hashes of S' and T' will also be identical. Try it yourself:
#include <stdio.h>
#include "hash_32a.c"
int main(int argc, char* argv[])
{
const char* s[] = {
"altarage",
"zinke",
"altarage_foo",
"zinke_foo",
"altarage_xyzzy",
"zinke_xyzzy"
};
int i;
for (i = 0; i < sizeof s / sizeof (char*); ++i)
{
Fnv32_t x = fnv_32a_str(s[i], FNV1_32A_INIT);
printf("%s: %08x\n", s[i], x);
}
}
$ ./test_fnv1a
altarage: e460d8b6
zinke: e460d8b6
altarage_foo: 3d8619c5
zinke_foo: 3d8619c5
altarage_xyzzy: 2a6373cf
zinke_xyzzy: 2a6373cf [1] https://code.google.com/p/xxhash
[2] https://code.google.com/p/xxhash/wiki/xxh32SipHash was developed to replace CityHash, Murmurhash as well as being a fast and secure PRF.
Since that post was submitted Murmurhash 3 and a number of other notable hash functions have been released. If you liked the linked post you should go read Aggregate Knowledge's series of posts on hash functions for a look at some newer algorithms: http://blog.aggregateknowledge.com/2012/02/02/choosing-a-goo...
If the source of the data might benefit (DoS attack being a common example) from deliberately causing collisions then there are additional constraints and looking at cryptographic hash functions may be warranted.
When i look at the FNV-1a "number" map, i think i see subtle
vertical patterns. With Murmur i see no patterns at all.
What do you think?
Here is FNV, quite a lot of reds: http://home.comcast.net/~bretm/hash/6.html And of course all green for SHA-1: http://home.comcast.net/~bretm/hash/9.html
This may be an interesting weakness with the StackOverflow system; if there's an answer that used to be very good, it may take a lot to knock it out of the first position when reality changes.
This should be no surprise. The birthday paradox, as Knuth points in in TAoCP, makes it clear why collisions happen. Given 23 people in a room, there is a greater that 50% chance that at least two have the same birthday.
Placing only 23 keys into a hash table with 365 entries with a perfectly random hash function will probably result in at least one collision.
Placing only 23 keys into a hash table with 365 entries with
a perfectly random hash function will probably result in at
least one collision.
Probably: almost certainly; as far as one knows or can tell
The answers were:
* 80%
* 50% to 90%
* 90%
* > 80%
* 80%
* 80% to 90%
From an Information Theory point of view, 50% probability means zero information, and 25%/75% probabilities mean one bit of information against/in-favor-of the event. This sounds roughly consistent with the results of the poll, with people assigning higher probabilities implying higher information density of the evidence.
I would think that at least in the latter, that less fast, more cpu/memory intensive would be more desirable. Something like SCRYPT may be overkill, especially if you use if for password hashes, under load for a lot of logins, but the comparison seems to fly in the face of that.
This also doesn't really mention random seed/salt values.
For example, if I can sufficiently reverse your hashing process, I can degrade a hash tree in to a linked list for a particular set of data - something your firewalls and other security measures will have virtually no chance of stopping, but which will greatly increase the run time taken to parse (malicious) instructions about that data.
A common use of this is maliciously chosen inserts of new items, to cause the tree structure to become a list building on it.
This is changing a bit now when SipHash is available. Unfortunately SipHash still is a bit too slow and forces an uncomfortable trade-off.
2.6x slower than DJB2 in my recent Rust trial. (SipHash is the hashing function in Rust's standard library.)
If you know the tree will be cached and/or the keys you have to hash are large then sure a tree might be a win, but hashing a small key might only be the same as two or three cache misses. Comparing tree nodes is not instruction free either.
I think it is really a case by case sort of thing, but there is no substitute for measuring (and nailing down the comparison to specific hash functions).
> Example (good) uses include hash dictionaries.
which I interpret as meaning hash tables or similar. If so hash function performance matters a lot, especially for short strings.
If you want to use Murmur you use std::_Hash_impl::hash and for FNV you use std::_Fnv_hash_impl::hash. (Include bits/functional_hash.h)
The implementation is at libsupc++/hash_bytes.cc
Security of such algorithms now where everyone has a 64-bit device: none.
Don't confuse hash functions like these and cryptographic hash functions.
Also interesting is universal hashing, which has applicability in cryptography (for randomness extraction, among other things):
This question is about non-cryptographic hash functions, as are commonly used in hash tables[1] which implement associative arrays, or sharding databases based on the hash of the record key.
Non-cryptographic hash functions are simply not in the same league as cryptographic ones; cryptographic hash functions are optimized to make it infeasible for an attacker to generate a different message with the same hash, while a non-cryptographic hash function generally simply has to have uniformly random output over its keyspace.
The original article did not descend into that obvious area of research. I see no particular reason why a hash algo that has the worst randomness shoved into the least significant byte (which I simply don't care about) might be an inherent result of smooshing the best randomness into its most significant nibble, which I do care very much about. Given the likely use case for a sharding hash, a smart hash designer would make sure that most of his effort is put into smooth distribution in MSB and perhaps totally ignore the LSB for a given amount of latency / computation / electrical power. After all, the actual users are more likely to hash based on the first 4 bits than the first 24 bits. Although you'll always run into people who think its funny to pull their shard subset out of the hash using the LSB (why?) or some random byte in the middle (why?)
I think MSB for shard key comes out of the tradition in the really olden days of sharding based on raw unhashed data. Sometimes thats random enough such that the MSB of the data makes an excellent shard key and hashing would just slow things down for a minimal gain, even today.
bucket = hash(x) & mask
bucket = hash(x) % buckets
Unless you're stuck supporting non power of two number of shards in which case you need modulus. And shoving more randomness into the LSB is more important than the MSB.
I've thought about it some and I think anyone with a networking background is automatically going to "subnet" their data from MSB down out of pure raw habit. Of course you split top down, just like IP addrs.
I've also seen non-technical popular explanations of sharding which stereotypically use something like phone numbers and start at the most significant digit.
And a stereotypical test question is this does not work well with stuff like customer IDs or transaction IDs because they tend toward sequential-ish, unless you're talking about some kind of data mining thing not daily live transactions.
On the other hand it works well if you shard (sorta) by date if you use the right (usually non-native) format. So if you have dates like 2013-10-14 and shard by YYYYMM somehow, then it could be easy to wipe 201210 from the database because whichever shard its on, its probably not impacting the latency figures for 201310 today. Unless you wanted to speed up the delete by smoothing it across all shards in which case sharding by hash ends up being the smart idea.
Trying to do tricky things can turn into a mess when the tricky thing changes mid project, too.
I am taking the first 4-bytes of the hash function output and using that. I checked and MurmurHash3 mixes the first and last 8 bytes of hash output as a last step, but I am not sure how much differentiation there is in the first 4-bytes.
I guess it is something I should check.
That difference is computationally extremely significant. It took the SO poster ~9ms to find a collision with, e.g., Murmur. If you mapped those results to the 160-bit hash, finding a collision, even ignoring the added time to compute the larger hash, would take 97 octillion years.
It is also worth pointing out that the hash size is not necessarily a measure of security. Very Smooth Hash is a good example of this: VSH has security that depends on the hardness of a problem that is closely related to integer factorization, and produces hashes that are as long as its parameters. You might need 3072 bit parameters for VSH to be secure, and will thus have 3072 bit hashes; but the hardness of finding a collision will be about as hard as brute-forcing a 128 bit keyspace (estimating these things is something of a dark art, and I am not an expert; it might be that VSH requires much larger parameters than RSA for equivalent security).
>codding collides with gnu
accident?