|
From: | Ed Watkeys |
Subject: | Re: [Chicken-users] Re: Better algorithm for growing hash tables |
Date: | Tue, 2 Aug 2005 17:22:54 -0400 |
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/>
[Prev in Thread] | Current Thread | [Next in Thread] |