1

Here is a little conundrum for you: If you use a hash algorithm like CRC-64 then how many bytes in a string would be necessary to read to calculate a good hash? Lets say all your strings are at least 2 KB long then it seems a waste or resources using the whole string to calculate the cache, but just how many characters do you think is enough? Would just 8 ASCII-characters be enough since it equals 64-bits? Wont using more than 8 ASCII characters just be pointless? I want to know your though on this.

Update: With a 'good hash' I mean the point where the likelihood of hash collisions can not get any less by using even more bytes to calculate it.

2 Answers2

2

If you use CRC-64 over 8 bytes or less then there is no point in using CRC-64: just use the 8 bytes "as is". A CRC does not have any added value unless the input is longer than the intended output.

As a general rule, if your hash function has an output of n bits then collisions begin to appear once you have accumulated about 2n/2 strings. In shorter words, if you use 64 bits, then it is very unlikely that you encounter a collision in the first 2 billions of strings. If you get a 160-bit or more output, then collisions are virtually unfeasible (you will encounter much less collisions than hardware failures such as the CPU catching fire). This assumes that the hash function is "perfect". If your hash function begins by selecting a few data bytes, then, necessarily, the bytes that you do not select cannot have any influence on the hash output, so you'd better use the "good" bytes -- which utterly depends on the kind of strings that you are hashing. There is no general rule here.

My advice would be to first try using a generic hash function over the whole string; I usually recommend MD4. MD4 is a cryptographic hash function, which has been utterly broken, but for a problem with no security involved, it is still very good at mixing data elements (cryptographically speaking, a CRC is so much more broken than MD4). MD4 has been reported to actually be faster than CRC-32 on some platforms, so you could give it a shot. On a basic PC (my 2.4 GHz Core2), a MD4 implementation works at about 700 MBytes/s, so we are talking about 35000 hashed 2 kB strings per second, which is not bad.

Community
  • 1
  • 1
Thomas Pornin
  • 72,986
  • 14
  • 147
  • 189
  • Ok, so 8 characters are pointless to generate a hash from. But if I use 32 characters vs. 16 characters, is the hash *more* random with 32? At what number of characters does the benefit of randomness go away? –  Aug 05 '11 at 16:46
1

What are the chances that the first 8 letters of two different strings are the same? Depending on what these strings are, it could be very high, in which case you'll definitely get hash collisions.

Hash the whole thing. A few kilobytes is nothing. Unless you actually have a need to save nanoseconds in your program, not hashing the full strings would be premature optimization.

Dan Grossman
  • 51,866
  • 10
  • 112
  • 101
  • If I need to optimize, then what if I get 8 bytes spread over the whole string. If the string is 8kb then I will get the first byte every KB to spread the bytes the hash is generated by. –  Aug 02 '11 at 09:49
  • Do you actually need to optimize? Are you implementing hardware or drivers or something? No consumer application would ever need this optimization. – Dan Grossman Aug 02 '11 at 09:57
  • Is there a reason programmers like yourself choose to obfuscate the actual situation rather than be up-front? Instead of yes/no, "perhaps"? You need situational advice yet won't provide the situation. It's as if you are purposely choosing to waste others' time rather than provide the path of least resistance to the proper answer. – Dan Grossman Aug 02 '11 at 10:36
  • I'm sorry, Sir. I did not mean to offend you or waste your time in any manner. It is a for a custom B+ Tree hashing algorithm I have written in C++. I answered "perhaps it is" because I mostly asked the question of curiosity and less of necessarity. Thank you for you help. –  Aug 02 '11 at 12:29