[plt-scheme] Weak hash tables

From: Matthew Flatt (mflatt at cs.utah.edu)
Date: Thu Sep 9 16:52:16 EDT 2004

At Thu, 9 Sep 2004 22:31:53 +0200, ifconfig nslookup wrote:
> I wonder how much memory the buckets reserve?

Non-weak hash table:

There's are two arrays, each with 2-4 times the number of pointer slots
as buckets. So that's a factor of 16 to 32 bytes per entry on a 32-bit
machine, or 8 MB for your table of 240,000 items.

Weak hash table:

There's only one array, and bucket records (to store the key and value)
are added to array slots as necessary. Each bucket is 12 bytes, but
there's also overhead in the GC to manage the weak pointer, typically
also around 12 bytes. So that's up to 4 * 4 * N bytes for the array and
24 * N bytes for the buckets and weak records, which is about 10 MB for
240,000 items.

> So is there a way to cause non-reservance of empty buckets?

It wouldn't be too difficult to re-hash when the number of mapped items
becomes small enough. That may be a worthwhile addition.


Posted on the users mailing list.