{"thread":{"id":"298","subject":"Re: Hash collision count","startedAt":"2005-04-24T23:12:24Z","lastAt":"2005-04-24T23:12:24Z","messageCount":1,"participants":["linux@horizon.com"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"1560","messageId":"20050424231605.30173.qmail@science.horizon.com","threadId":"298","inReplyTo":null,"subject":"Re: Hash collision count","fromName":"","fromEmail":"linux@horizon.com","sentAt":null,"receivedAt":"2005-04-24T23:12:24Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"*Sigh*.\n\n> A collision -will- occur eventually, and it is trivial to avoid this \n> problem:\n\nYes, it will occur *eventually*.  Let's put some numbers on this\n\"eventually\" business.\n\nThe earth's sun will run out of hydrogen and become a red giant in about\n6 billion years, 1.3 * 2^57 seconds.  (Many people say 5 billion. but\nI'll round up for safety.)  Suppose we add 1 file per second to our\nrepository until we are interrupted by the sun's photosphere engulfing\nthe planet and melting all our computers.\n\nThat's a total of n*(n-1)/2 = 1.7 * 2^113 pairs of files which can\npossibly collide.  I'll round up to 2^114 for simplicity.\n\nAssuming we have a good uniform hash function, the chance that any given\npair of different file versions produces an identical hash is 1/2^160.\n\nThe chance that there are no collsions is (1-1/2^160)^(2^114).  What is\nthis numerically?  Well, (1-a)*(1-b) = 1 - a - b + a*b.  When multiplying\nprobabilities very close to 1 (a and b small), the probability is\na little bit larger than (1-(a+b)).\n\nLikewise, when exponentiating proabilities very close to 1, (1-a)^n is\na bit larger than 1-n*a.\n\nThus, the probability of no collisions is a bit larger than (1 - 2^114/2^160),\nor (1 - 2^-46).  The probability of one or more collisions is a bit *less*\nthan 2^-46, 1 in 70 trillion.\n\n\nWith odds like that, I submit that it's not worth fixing; the odds\nof introducing a bug are far higher than that.\n\n\nIf you can't find a hard drive large enough to store 183 quadrillion\nfile versions, the probability of a collision decreases as the square of\nthe fraction of that number you do store.  For example, if you only have\n400 billion versions, the chance of a collision is around 2^-84.\n\nWe have a fair bit of safety margin in our \"good uniform hash\" assumption.\n\nRunning out of 32-bit inode number space is a *far* more urgent problem.\n\nNot to mention that over the next 1000 years of kernel maintainers, one\nof them may find something they like better than git.\n"}]}