Subject: Re: Fwd: Re: New hash algorithm - FNV - for use in the kernel
To: Seth Kurtzberg <seth@cql.com>
From: John Franklin <franklin@elfie.org>
List: tech-kern
Date: 11/27/2001 13:39:26
On Mon, Nov 26, 2001 at 11:06:39PM -0700, Seth Kurtzberg wrote:
> However, on the subject of hash table sizes, it is not difficult to allow the
> hash table to dynamically increase in size.  This does not impose significant
> overhead; you can simply count the length of the hash buckets as you traverse
> them, and trigger a dynamic resize when some threshhold is exceeded.
> 
> There would be some issues in doing so, such as memory fragmentation, but it
> can be done.

Would an extensible hashing scheme work well here.  That is, one where
you hash into a small set of buckets initially, and then split only the 
full buckets as they fill up?

I've seen a number of papers on it, some dating back to the '70s.

jf
-- 
John Franklin
franklin@elfie.org
ICBM: N37 12'54", W80 27'14" Z+2100'