Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| 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] |
| 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
Return to the
comp.compilers page.
Search the
comp.compilers archives again.