Re: Resizing hash tables in Guile

[Harvey J. Stein]

Joris van der Hoeven <address@hidden> writes:

 > >  > average.  This means that, on average, operations are O(1).
 > > 
 > > Inserts are, but lookups aren't necessarily.
 > 
 > Both aren't necessarily, because inserting requires looking up too.

Yes, if you want to return an error for inserting 2 items with the
same key.  No, if you allow multiple items with the same key.

 > > And good hashing functions are still hard to write.
 > 
 > I do not really agree. A good hash algorithm for lists (or strings),
 > which I use in TeXmacs, is ...

I guess "hard" isn't quite the word for it.  What I meant was that the
obvious ones don't work well.  You basically need to look up a good
one to get good behavior.  Tcl's fcn works pretty well too.  I forget
what it does.

 > > With this many items, log(N) is still just 32, so an O(log(N))
 > > algorithm will still beat an O(1) algorithm if it's really
 > > log_2(N) vs 32.
 > 
 > Yes, but the O(1) is really *table lookup* multiplied by a small
 > constant here, so this is *fast*. You may adjust the small constant
 > by choosing an appropriate threshold for "size/nr buckets".

Not just table lookup.  Also hash calculation from the key, which can
be more time consuming than a key comparison, and key comparisons for
everything in the bucket.

 > > Trees also sort the data for you, which hash tables don't give you.
 > 
 > But you need a compairison operation for that,
 > which may be even less natural than a hash function.

Yes.  For hash tables you just need a key equality test.  For trees
you need to be able to order the keys.

 > > So, ideally, one would have a hash table object with & without
 > > resizing, and various sorts of tree (AVL, red/black, B*, etc) objects.
 > > insert and delete and map would be methods that work on all of the
 > > above, with map on trees returning the data in sorted order.  For that
 > > matter, insert & delete might as well also work on lists...
 > 
 > Agreed: ideally, we have everything :^)

I think we're on the same page here...

STk had a nice scheme interface for hash tables.  The code uses the
Tcl hash tables, they autoresize and if I recall correctly, many of
the important parameters can be modified.  You might want to model the
guile stuff on this, or utilize this work.  I advocated this when the
discussion came up years ago on the guile mailing list.

BTW, there was a long discussion of hash tables on the guile list some
number of years ago.  At the time I didn't like liked the guile (aka
scm) hash tables.  They were a very minimal implementation.  The user
had to do too much to use them.  I don't know what it's like these
days, but it'd certainly be nice to have a good implementation
available which includes autosizing.

-- 
Harvey Stein
Bloomberg LP
address@hidden