Re: symbol tables and search tries

RLake@oxfam.org.uk
31 Jan 2006 00:33:59 -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)
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)
[15 later articles]
| List of all articles for this month |

From: RLake@oxfam.org.uk
Newsgroups: comp.compilers
Date: 31 Jan 2006 00:33:59 -0500
Organization: Compilers Central
References: 06-01-117
Keywords: symbols, comment

Hans Aberg wrote:


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


But if k is chosen to be proportional to N, it's O(1).


> If k is doubled when
> too low, perhaps insert time is logarithmic for hash tables too.


A symbol table (presumably) only grows, so exponentially increasing
the size of the hash table is similar to exponentially increasing the
size of an expandable array; it is on average O(1). (Each element in
the hash table is rehashed an average of one time.)


In any event, it would seem that lookup time is more important
than insert time for a symbol table implementation, although
that depends on the language. In almost any program, a given
symbol will be used more than once, but that doesn't take into
account the myriad of otherwise unused symbols introduced by
libraries (C header files, standard preludes, or whatever).


Having said that, I don't think that a hash table is the best
data structure for an IDE, although it probably is for a
compiler. An IDE will want to be able to do things like
tab-completion, which would militate for a data structure
which facilitates prefix searches, such as a trie or
PATRICIA tree.
[In block structured languages the symbol table can shrink, typically
dumping a block's symbols at the end of the block. I suppose that if
you have one of those quaint compilers that makes more than one pass
over the source you might need to leave them all in and just mark them.
-John]


Post a followup to this message

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