Re: symbol tables and search tries

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.)

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