[darcs-users] Re: [zander at kde.org: Re: Re: Frustrations diffing against the last change to a file]
Jamie Webb
j at jmawebb.cjb.net
Sun Apr 3 19:59:14 UTC 2005
On Sat, Apr 02, 2005 at 03:26:34PM -0800, Michael G Schwern wrote:
> We don't need to be cryptographically secure, but we do need to reasonably
> avoid collisions within a project. I don't know how to run the numbers to
> find out the odds of a collision. Anyone?
Patches in repo | Collision probability
----------------+----------------------
2048 | 0.00003
4096 | 0.00012
8192 | 0.00048
16384 | 0.00195
32768 | 0.00778
65536 | 0.03076
131072 | 0.11750
262144 | 0.39346
524288 | 0.86466
1048576 | 0.99966
So, much less than 1 per thousand real projects could be expected to
see collisions with a 36-bit hash. Provided that such conflicts were
merely a nuisance (i.e. darcs complains if you try to refer to a patch
by digest when there's a conflict involving that particular patch),
that is IMO quite acceptable.
I don't much like the idea of having to deal with base64 values
though. I'd prefer a 7-character (35-bit) 'base32' value that's case
insensitive. But a non-unique sequential number is probably still
nicer.
-- Jamie Webb
More information about the darcs-users
mailing list