Re: Efficiency and flexibility of hash-tables

[Roland Orre]

On Sat, 2003-02-08 at 12:00, Joris van der Hoeven wrote:
> Hi,
> 
> When declaring a hash table using
> 
>       (define H (make-hash-table 100))
No, the hash table is a vector of entries to lists where the actual
information is stored. A hash table in guile can therefore contain
any number of items. The number of entries is merely a choice of what
performance you need. If you declare too few entries you will get
a lot of linear search through the lists from each entry.
I myself use to estimate it so that the lists will rarely be deeper
than two or three to get a reasonable performance.

The performance is also reflected upon the hash function versus the
vector length. Usually it is advisable to use a prime number to avoid
systematic hashing to the same entries. Sometime it happened I missed
this and sloppily declared the hash table length to e.g. 1000000 if
needing about 3000000 items. The run took several hours instead of
the expected half an hour, which I got when changing the length to
1000003. If you have access to some mathematical package like maple
there is often a function nextprime which can be helpful.

Usually the built-in hash functions works fine but you may also
consider making a special hash functions for special needs if
the built-in function doesn't spread good enough.

        Best regards
        Roland Orre

> 
> does this mean that the number of slots will *always* remain 100?
> 
> I am frequently dealing with hash tables where I do not
> have a reasonable estimation of number of entires in advance.
> In TeXmacs, I therefore implemented a hash table type which
> doubles the number of slots each time that the number of entries
> becomes larger than a constant times the number of slots
> (and divides by two the number of slots when the number of
> entries becomes smaller than a constant times the number of slots).
> Has a similar system been implemented in (an extension of) guile?
> 
> Thanks for your help, Joris
> 
> 
> -----------------------------------------------------------
> Joris van der Hoeven <address@hidden>
> http://www.texmacs.org: GNU TeXmacs scientific text editor
> http://www.math.u-psud.fr/~vdhoeven: personal homepage
> -----------------------------------------------------------
> 
> 
> 
> _______________________________________________
> Guile-user mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/guile-user
--