Re: [Chicken-users] Re: Better algorithm for growing hash tables

[Ed Watkeys]

On Aug 2, 2005, at 10:50 AM, Nelson Castillo wrote:

> On 8/1/05, Ed Watkeys <address@hidden> wrote:
>
> > _The Practice of Programming_ (Kernighan & Pike) deals with a
> > situation analgous to this; they grow storage for a string by powers
> > of two. This works well because it heavily tests the algorithm --
> > from 1 to 2 to 4 to 8... -- but also causes a grow for every log n
> > inserts i.e. rarely.
>
> Yup. But you really should use prime numbers for hash tables.

Is there a paper or book that offers a convincing, empirical argument  
for this? I've read and heard this exhortation before but the  
justification in the presence well designed hash and rehash functions  
has always been "just to be safe."

Ed


--
Transmogrify, LLC * <http://xmog.com/>