Choosing a hash function for best performance
.net, .net-4.0, hash
Solution
It depends on the number of files you have.
The chance of a collision `P(collision) = c/2^N` (in a perfect hash function), where `c` is your number of messages (files) and `N` is the number of bits in your collision algorithm.
As real-world hash functions aren't perfect so you have two options: optimize for speed and optimize for collision avoidance.
In the first case you will want to use CRC32. CRC32 is very common but, depending on the number of files you have, might not be enough: you're guaranteed to have a collision at ~4,3 billion messages (32 effective bits), but in practice you might encounter your first collision at ~10 million messages. CRC32 has very fast implementations (SSE 4.2 even has a hardware instruction for it). CRC64 has a lot lower chance of a collision but is not widely used, hence if you want more collision avoidance than CRC32 you better look at cryptographic hash functions.
If you want to avoid collisions while sacrificing speed you will want cryptographic hash functions, of which MD5 (128 bits), SHA-1 (160 bits) and SHA-2 (usually SHA-256 or SHA-512) are the most widely used and have fast implementations. Very efficient hash collision finding algorithms for MD5 are available, but if you input random messages you'll get as close to the `P(collision) = c/2^128` as you're ever going to get while still running in reasonable time.
Problem
I need to compare many files (some could be large, some are small) over the network. So I am planning to hash every file on every client and send only the hash value over the network. The main goal here is performance. This implies minimal network traffic. Security is not the issue. There should also be "zero" collisions since I don't want ever to mistakenly consider two different files as identical. Saying that, I know that theoretically there are always collisions, I just want the chance to ever practically meet them be absolutely negligible. So my question is: Which .net hash function is best for this task? I was thinking to use a buffered reader and `MD5CryptoServiceProvider` (since CNG may not be available on all clients). Is there a way to get better performance than that? (perhaps using some external library?)