Re: symbol tables and search tries

  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]

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