Re: symbol tables and search tries

glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:


> Matthias Blume wrote:
>
>> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
>
>>>(snip)
>
>>>>[I don't understand what you're proposing. Balanced trees are O(log N)
>>>>to search and require rebalancing whenever you insert something. Hash
>>>>tables of the sort we usually use for compiler symbol tables are O(1)
>>>>and balancing isn't an issue. -John]
>
>>>Hash tables are O(1) until you have to resize them.
>
>> The cost of an insertion or an access of a hash table element is O(1)
>> amortized, taking the occasional need for resizing into account.
>> (This assumes that the resizing policy is chosen appropriately.
>> Example: Double the size when the load factor exceeds some fixed
>> threshold.)
>
> Assuming you can afford the extra memory, yes.


If you double your hashtable when the load factor exceeds 1, then you
waste an expected number of buckets that is bounded by something very
close to the number of actual elements in the table. If you do not
double the size, then you have to use more chain links in each bucket.
In a typical implementation, the required number of extra pointers is
the same as the number of those wasted buckets. Thus, doubling the
number of buckets does not waste memory (in comparison with chaining).


> Note that O() notation assumes the large N limit, though most
> compilers operate with more reasonable N.


Yes. But that is exactly what the "double the size on demand"
mechanism achieves.


I expect a binary tree implementation of the table to use _more_
memory than (or at best an equal amount as ) such a hashtable.


Matthias

Return to the comp.compilers page.
Search the comp.compilers archives again.