Re: symbol tables and search tries

Anton Ertl wrote:
>
> glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
> >Hash tables are O(1) until you have to resize them.
>
> And with proper (i.e., exponential, e.g., doubling when a certain
> density is reached) resizing, they are still O(1):
>
> Resizing is an O(n) operation (where n is the number of entries in the
> hash table at the time of resizing), but you resize only once every
> O(n) elements, so the amortized cost of resizing per insertion is
> O(n/n)=O(1); of course, there is no resizing cost when you are only
> doing lookups.


That's fine :-)


I had expected that resizing costs O(log n) once, for about log(n)
resizes until the final n is reached.


Now I can continue to use my symbol tables, where the hash links are
already part of the symbol entries, to reduce memory management
operations and memory fragmentation.


DoDi

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