Re: symbol tables and search tries

henry@spsystems.net (Henry Spencer)
31 Jan 2006 00:37:47 -0500

          From comp.compilers

Related articles
[3 earlier articles]
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)
Re: symbol tables and search tries danwang74@gmail.com (Daniel C. Wang) (2006-01-31)
Re: symbol tables and search tries mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-01-31)
Re: symbol tables and search tries DrDiettrich@compuserve.de (Hans-Peter Diettrich) (2006-01-31)
Re: symbol tables and search tries henry@spsystems.net (2006-01-31)
Re: symbol tables and search tries blume@tti-c.org (Matthias Blume) (2006-01-31)
[11 later articles]
| List of all articles for this month |

From: henry@spsystems.net (Henry Spencer)
Newsgroups: comp.compilers
Date: 31 Jan 2006 00:37:47 -0500
Organization: SP Systems, Toronto, Canada
References: 06-01-085 06-01-111 06-01-117
Keywords: symbols
Posted-Date: 31 Jan 2006 00:37:47 EST

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


Post a followup to this message

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