Re: symbol tables and search tries

Hans-Peter Diettrich <DrDiettrich@compuserve.de>
31 Jan 2006 10:37:47 -0500

          From comp.compilers

Related articles
[7 earlier articles]
Re: symbol tables and search tries clint@0lsen.net (Clint Olsen) (2006-01-31)
Re: symbol tables and search tries haberg@math.su.se (2006-01-31)
Re: symbol tables and search tries henry@spsystems.net (2006-01-31)
Re: symbol tables and search tries find@my.address.elsewhere (Matthias Blume) (2006-01-31)
Re: symbol tables and search tries danwang74@gmail.com (Daniel C. Wang) (2006-01-31)
Re: symbol tables and search tries mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-01-31)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-01-31)
Re: symbol tables and search tries henry@spsystems.net (2006-01-31)
Re: symbol tables and search tries blume@tti-c.org (Matthias Blume) (2006-01-31)
Re: symbol tables and search tries mr.waverlye@verizon.net (Mr.E) (2006-01-31)
Re: symbol tables and search tries mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-02-02)
Re: symbol tables and search tries gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-02-02)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-02-02)
[7 later articles]
| List of all articles for this month |

From: Hans-Peter Diettrich <DrDiettrich@compuserve.de>
Newsgroups: comp.compilers
Date: 31 Jan 2006 10:37:47 -0500
Organization: Compilers Central
References: 06-01-085 06-01-111 06-01-112 06-01-118
Keywords: symbols

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


Post a followup to this message

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