[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Efficiency and flexibility of hash-tables

From: Roland Orre
Subject: Re: Efficiency and flexibility of hash-tables
Date: 08 Feb 2003 14:57:58 +0100

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>
> GNU TeXmacs scientific text editor
> personal homepage
> -----------------------------------------------------------
> _______________________________________________
> Guile-user mailing list
> address@hidden

reply via email to

[Prev in Thread] Current Thread [Next in Thread]