[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: symbols hash table
From: |
Martin Grabmueller |
Subject: |
Re: symbols hash table |
Date: |
Tue, 23 Jan 2001 18:35:27 +0100 (MET) |
> From: Dirk Herrmann <address@hidden>
> Date: Tue, 23 Jan 2001 18:09:12 +0100 (MET)
>
[snip]
> I have thought about such a representation, but I think that it is
> probably not the best solution for our case: The hash table for symbols
> should be a weak hash table. That means, that entries from that table may
> disappear. In other words, when looking for a symbol in the hash table,
> the fact that you stumble across an empty slot does not mean that you can
> finish your search: The symbol you are looking for may have been added to
> the hash table when the slot was in use.
>
> Thus, when looking for a symbol you will always have to search a
> predefined number of slots before you can be sure that a symbol is not
> contained in the table. Alternatively, the code that removes unreferenced
> symbols from the table during gc will have to do some clever rehashing.
> However, this will complicate things a lot since you must handle the case
> that the hash table was in the process of being resized just when the gc
> was issued.
Have you thought about storing a special value into the table when
deleting symbols, so that an insertion operation will use a freed slot
(with that special value) for entering a new symbol, but a search will
deal with that slot as if it was in use? That would be a solution to
the problem you mentioned above.
Regards,
'Martin
--
Martin Grabmueller address@hidden
http://www.pintus.de/mgrabmue/ address@hidden on EFnet
- symbols hash table, Dirk Herrmann, 2001/01/23
- Re: symbols hash table,
Martin Grabmueller <=