Re: symbol tables and search tries

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]

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