git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Hash collision count

From
JGJeff 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
Next: Jeff Garzik
Message 1 of 14 in “Hash collision count”
  1. Jeff GarzikApr 23, 2005
  2. Jeff GarzikApr 23, 2005
  3. Ray HeasmanApr 23, 2005
  4. Jeff GarzikApr 23, 2005
  5. Petr BaudisApr 23, 2005
  6. Jeff GarzikApr 24, 2005
  7. Petr BaudisApr 24, 2005
  8. Jeff GarzikApr 24, 2005
  9. Imre SimonApr 24, 2005
  10. Whales falling on houses - was: Hash collision countJon Seymour, Apr 24, 2005
  11. Tom LordApr 25, 2005
  12. Petr BaudisApr 26, 2005
  13. Ray HeasmanApr 24, 2005
  14. David LangApr 24, 2005

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.