Re: symbol tables and search tries

anton@mips.complang.tuwien.ac.at (Anton Ertl)
31 Jan 2006 00:32:08 -0500

          From comp.compilers

Related articles
symbol tables and search tries mr.waverlye@verizon.net (Mr.E) (2006-01-28)
Re: symbol tables and search tries haberg@math.su.se (2006-01-28)
Re: symbol tables and search tries gah@ugcs.caltech.edu (glen herrmannsfeldt) (2006-01-30)
Re: symbol tables and search tries haberg@math.su.se (2006-01-30)
Re: symbol tables and search tries anton@mips.complang.tuwien.ac.at (2006-01-31)
Re: symbol tables and search tries RLake@oxfam.org.uk (2006-01-31)
Re: symbol tables and search tries vmakarov@redhat.com (Vladimir Makarov) (2006-01-31)
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)
[16 later articles]
| List of all articles for this month |
From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: 31 Jan 2006 00:32:08 -0500
Organization: Institut fuer Computersprachen, Technische Universitaet Wien
References: 06-01-085 06-01-111 06-01-112
Keywords: symbols
Posted-Date: 31 Jan 2006 00:32:07 EST

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.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html


Post a followup to this message

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