Re: symbol tables and search tries

haberg@math.su.se (Hans Aberg)
30 Jan 2006 02:05:00 -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)
[17 later articles]
| List of all articles for this month |

From: haberg@math.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 30 Jan 2006 02:05:00 -0500
Organization: Mathematics
References: 06-01-085 06-01-111
Keywords: symbols

  John Levine wrote:


> >Why not using a balanced tree, like for example the std::map of C++? I
> >gives the minimum logarithmic search/insertion times without having to
> >bother about balancing, as in a hash map. Is the overhead too big?


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


The hash tables I know of use a linked list on each hash value, and if
there are k hash values (= number of linked list), the average search
time is O(N/k) = O(N). By choosing the value k suitably relative to N,
one can achieve fast searches by keeping the overhead down. If k is
chosen poorly, the hash table must be rebuilt, in order to achieve
this efficiency. Or are you using another type of hash tables? And for
balanced trees, the insert time is logarithmic. If k is doubled when
too low, perhaps insert time is logarithmic for hash tables too.


--
    Hans Aberg
[I make my hash tables big enough that the chains are short, i.e.,
design so that k>=N so it's O(1). Hash headers need only be one word
pointers, so pick a number larger than the number of symbols you
expect in a large program, say, 10,000, and use that. So it adds 40K
to the size of the program, that's down in the noise these days.
-John]



Post a followup to this message

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