Version française
Home     About     Download     Resources     Contact us    
Browse thread
range of hash function
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Richard Jones <rich@a...>
Subject: Re: [Caml-list] range of hash function
On Sat, Feb 20, 2010 at 10:54:12PM +0900, Jacques Garrigue wrote:
> Since you have the algorithm, you can predict collisions. Basically
> shifting character n by 1 is equivalent to shifting character n+1 by
> 19, so you have lots of collisions. But this hash function being
> intended for hashtables, collisions are not a problem, uniform
> distribution matters more.

I would slightly dispute your assertion that collisions are not a
problem, because of algorithmic complexity attacks:

http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003/index.html

The hash implementation used by Perl was changed to avoid this attack:

http://perl5.git.perl.org/perl.git/blob/HEAD:/perl.c#l1465

Rich.

-- 
Richard Jones
Red Hat