title: Choosing a minimum hash size for a given allowable number of collisions
body: <p>I am parsing a large amount of network trace data.  I want to split the trace into chunks, hash each chunk, and store a sequence of the resulting hashes rather than the original chunks.  The purpose of my work is to identify identical chunks of data - I'm hashing the original chunks to reduce the data set size for later analysis.  It is acceptable in my work that we trade off the possibility that collisions occasionally occur in order to reduce the hash size (e.g. 40 bit hash with 1% misidentification of identical chunks might beat 60 bit hash with 0.001% misidentification).  </p>
  
  <p>My question is, given a) number of chunks to be hashed and b) allowable percentage of misidentification, how can one go about choosing an appropriate hash size?</p>
  
  <p>As an example:</p>
  
  <p>1,000,000 chunks to be hashed, and we're prepared to have 1% misidentification (1% of hashed chunks appear identical when they are not identical in the original data).  How do we choose a hash with the minimal number of bits that satisifies this?</p>
  
  <p>I have looked at materials regarding the <a href="http://en.wikipedia.org/wiki/Birthday_paradox" rel="nofollow">Birthday Paradox</a>, though this is concerned specifically with the probability of a <em>single</em> collision.  I have also looked at materials which discuss choosing a size based on an acceptable probability of a single collision, but have not been able to extrapolate from this how to choose a size based on an acceptable probability of <em>n</em> (or fewer) collisions.     </p>