Re: Hash collision count

From: Jeff Garzik <jgarzik@pobox.com>
Date: Apr 23, 2005, 20:33 UTC
Message-ID: <426AB10F.9050300@pobox.com>
In-Reply-To: <426AAFC3.800@pobox.com>

Jeff Garzik wrote:

Show 13 quoted lines

> 
> 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

This of course presumes that you know that your new data does not exist in the cache.

Otherwise, you would need to hash the on-disk $hash-0 to determine if its a collision or a reference.

	Jeff