Re: [Tux3] Comparison to Hammer fs design

[Maxim Sobolev <sobomax@xxxxxxxxxxx>]

Matthew Dillon wrote:
>     Well, you've described both sides of the debate quite well.  I for
>     one am in the 0-risk camp.  ReiserFS got into trouble depending on
>     a collision space (albeit a small one).  I did extensive testing of
>     64 bit collision spaces when I wrote Diablo (A USENET news system
>     contemporary with INN, over 10 years ago) and even with a 64 bit space
>     collisions could occur quite often simply due to the volume of article
>     traffic.

This is due well-known mathematical property, called birthday problem or 
birthday paradox. As a result of that property for ideal hash function 
of size N bits you only need 2^(N/2) random inputs to generate a 
collision with sufficient probability. Therefore, for 64 bit hash 
function you will get one collision for approximately every 2^32 inputs.

http://en.wikipedia.org/wiki/Birthday_attack

-Maxim