Re: Hashtables in guile.

[Telford Tendys <telford@triangle.triode.net.au>]

> > Hash tables are fast to pull things out of and fast to put things
> > into but slow to resize -- them's the breaks.
> 
> Well, yes and no.  The standard hash table implementation is like
> that.  There are a number of other hash table algorithms; one, in
> particular, only requires rehashing one bucket at a time as it
> resizes.  Still as much work, but not all in one lump. 

Is there a URL that explains this algorithm, I'm curious to see
if it might be useful to me. (a book reference would make an
acceptable second choice :-)

> We'd also want some good string-hashing functions preimplemented.
> Doing it right is hard. 

I wrote a hasher that had a lookup table of 256 constant random ints.
Each byte in the input is used as an index into the lookup table
and the random int that returns from the lookup is xored into
an accumulator. The accumulator rotates by one bit after each
xor into it. It was simple, reasonably fast, and had statistical
characteristics virtually the same as a uniform random generator
would. I have C++ source somewhere if anyone is interested.

> > c) ??  - not quite sure how to apply this to B-Trees,
> >          would appreciate if someone explained the issue of weak
> >          and double-weak keys to me.
> 
> If you want to use your hash table as a cache of some sort, you
> wouldn't want it preventing GC.  So a weak hash table stores keys and
> items, but doesn't count as a reference to the item.  A double-weak
> hash table doesn't count as a reference to the keys either.

Hmmm, OK my B-Tree implementation always flags the garbage collector
so it won't do the weak stuff. If an item in a weak hash table is
collected, how does the garbage collector tell the hash table to toss
out the dead item?

	- Tel

PS: for anyone who downloaded my database code, there is a memory
    bug in the `table' SMOB, it is data dependent and I haven't
    found it yet.