[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: |
10 Feb 2003 18:09:30 +0100 |
On Mon, 2003-02-10 at 17:52, Mikael Djurfeldt wrote:
> The idea of having an upper threshold comes from the idea of
> maintaining the load factor of the hash table in a reasonable
> interval. But the purpose of the load factor is to prevent to large
> clusters forming in the same hash bucket. What about simply counting
> the pairs in a bucket during insertion and rehashing when we reach a
> threshold? Then no extra data needs to be stored in the table. (We
> would need to globally serialize rehashing with an external mutex,
> though.)
The risk with this is that if the hash function in a specific situation
is bad, not spreading enough, we may form clusters anyway. With a
risk that we will reallocate hash tables much too often.
> Another disadvantage is that the tables wouldn't shrink. Is this an
> issue?
For most of our applications it isn't because we will reallocate all
hash tables after each run.
In all my code over the years hash-remove! is very very rare.
Best regards
Rolan
- Re: Resizing hash tables in Guile, (continued)
- Re: Resizing hash tables in Guile, Marius Vollmer, 2003/02/12
- Re: Resizing hash tables in Guile, Mikael Djurfeldt, 2003/02/12
- Re: Resizing hash tables in Guile, Roland Orre, 2003/02/12
- Re: Resizing hash tables in Guile, Mikael Djurfeldt, 2003/02/13
- Re: Resizing hash tables in Guile, Harvey J. Stein, 2003/02/13
- Re: Resizing hash tables in Guile, Joris van der Hoeven, 2003/02/13
- Re: Resizing hash tables in Guile, Harvey J. Stein, 2003/02/13
- Re: Resizing hash tables in Guile, Paul Jarc, 2003/02/13
- Re: Resizing hash tables in Guile, Joris van der Hoeven, 2003/02/13
- Re: Resizing hash tables in Guile, Rob Browning, 2003/02/12
- Re: Efficiency and flexibility of hash-tables,
Roland Orre <=
- Re: Efficiency and flexibility of hash-tables, Paul Jarc, 2003/02/12
- Re: Efficiency and flexibility of hash-tables, Roland Orre, 2003/02/12