Re: symbol tables and search tries

Hans Aberg <haberg@math.su.se> wrote:
>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...


Hash tables can be extended incrementally to keep fill factor under
control, rather than requiring full rebuilds. See, e.g., the Larson
paper in CACM April 1988. Given a good hashing function, it's not
that hard to make a hash table keep its efficiency while scaling up
indefinitely, *without* requiring you to guess a maximum size in
advance.


You can combine the advantages by hanging a tree, rather than a list,
on each hash bucket. But it hardly seems worth the trouble.


The only good reason to use trees for symbol tables is if you also have a
requirement to traverse the table in sort order.
--
spsystems.net is temporarily off the air; | Henry Spencer
mail to henry at zoo.utoronto.ca instead. | henry@spsystems.net

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