This is the mail archive of the guile@cygnus.com mailing list for the guile project.
Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|
Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |
> > 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.