From: Junio C Hamano <junkio@cox.net>
Date: Mon, 16 Jan 2006 05:32:16 GMT
Subject: Re: [PATCH] new tutorial
Message-ID: <7vmzhwybz3.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <20060116035731.GA14849@fieldses.org>

"J. Bruce Fields" <bfields@fieldses.org> writes:

>> Empirically the first 7 hexdigits are enough (even 5 for small
>> projects such as git itself).  In fact, in the linux-2.6
>> repository itself, it appears 5 hexdigits are enough to identify
>> all 171902 objects (not just commits) uniquely currently
>
> Five hex digits is only 20 bits, and 171902/2^20 > 1/10, so each
> additional object has a better than 1-in-10 chance of colliding with an
> existing object.  The chances there hasn't been a collision in the first
> 5 digits by now must be practically zero.  Maybe you're thinking bytes,
> not hex digits?  Unless my math is wrong.

Your math is right and my script was wrong.

For linux-2.6 repository:

	$ git rev-list --objects HEAD | sort >/var/tmp/objnames
        $ wc -l </var/tmp/objnames
        171902
        $ sed -e 's/^\(........\).*/\1/' </var/tmp/objnames | uniq | wc -l
        171899
        $ sed -e 's/^\(.........\).*/\1/' </var/tmp/objnames | uniq | wc -l
        171902

So 8 is enough for most but not all objects; you need 9 to
uniquely cover everybody.