From: Jeff Garzik <jgarzik@pobox.com>
To: Git Mailing List <git@vger.kernel.org>,
Linus Torvalds <torvalds@osdl.org>
Subject: Hash collision count
Date: Sat, 23 Apr 2005 16:27:47 -0400 [thread overview]
Message-ID: <426AAFC3.800@pobox.com> (raw)
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
next reply other threads:[~2005-04-23 20:23 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-04-23 20:27 Jeff Garzik [this message]
2005-04-23 20:33 ` Hash collision count Jeff Garzik
2005-04-23 23:00 ` Ray Heasman
2005-04-23 23:20 ` Jeff Garzik
2005-04-23 23:46 ` Petr Baudis
2005-04-24 0:35 ` Jeff Garzik
2005-04-24 0:40 ` Petr Baudis
2005-04-24 0:43 ` Jeff Garzik
2005-04-24 21:24 ` Imre Simon
2005-04-24 22:25 ` Whales falling on houses - was: " Jon Seymour
2005-04-25 23:50 ` Tom Lord
2005-04-26 0:00 ` Petr Baudis
2005-04-24 1:01 ` Ray Heasman
2005-04-24 7:56 ` David Lang
-- strict thread matches above, loose matches on Subject: below --
2005-04-24 23:16 linux
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=426AAFC3.800@pobox.com \
--to=jgarzik@pobox.com \
--cc=git@vger.kernel.org \
--cc=torvalds@osdl.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.