Hash collision count
- From
- Jeff Garzik <jgarzik@pobox.com>
- Date
- Apr 23, 2005, 20:27 UTC
- Message-ID
- <426AAFC3.800@pobox.com>
Ideally a hash + collision-count pair would make the best key, rather than just hash alone.
A collision -will- occur eventually, and it is trivial to avoid this problem:
$n = 0 attempt to store as $hash-$n if $hash-$n exists (unlikely) $n++ goto restart key = $hash-$n
Tangent-as-the-reason-I-bring-this-up:
One of my long-term projects is an archive service, somewhat like Plan9's venti: a multi-server key-value database, with sha1 hash as the key.
However, as the database grows into the terabyte (possibly petabyte) range, the likelihood of a collision transitions rapidly from unlikely -> possible -> likely.
Since it is -so- simple to guarantee that you avoid collisions, I'm hoping git will do so before the key structure is too ingrained.
Jeff