[plt-scheme] Weak hash tables

On Thu, Sep 09, 2004 at 10:31:53PM +0200, ifconfig nslookup wrote:
> I wonder how much memory the buckets reserve?
> Is there a way to set the weak-hash-tables (and normal hash-tables on
> delete) to actually remove the buckets?
> I have seen code that operates like this, at work:
> A main hash-table is created to contain all keys, which are every
> first name and every last name of every client in a database
> (approximately 40,000 keys in an average customer's database).
> Then, that hash-table is added the keys "A".."Z", and each is
> populated with - guess what - a hash-table, that contains every name
> without its first character.
> You can pretty much guess the rest.

That data structure is usually called a "trie."

> In the end, every table is left with up to 26 keys. But for some
> reason, these tables are all first populated with their entire list,
> and only then broken down into subtables, contained in the same
> hash-table (I would use a new one).

That's a bizarre way to implement a trie. You normally wouldn't use a
hash table to create a trie -- it's a lot more work and overhead than
you really need.

> In this hash-table or weak-hash-table, this would probably take up
> very much space. As the average customer name is 6 characters, we can
> calculate a total of 240,000 empty buckets.
> So is there a way to cause non-reservance of empty buckets?

It'd be better to avoid the pathological input in the first place. While
there are cases where you might reasonable want a hash table to shrink,
this is not a good example.
-- 
Bradd W. Szonye
http://www.szonye.com/bradd