Re: symbol tables and search tries

Perhaps, the suggestion that a search tree might be faster than a hash
tree came from this paper.


    http://www.cs.princeton.edu/~rs/strings/


It's worth pointing out that if you expect your lookup to fail most of
the time. a search tree can be more efficient than hashing, simply
because it doesn't need to examine the entire input string to
determine it's not in the tree. Any reasonable hashing scheme has to
examine the entire string.


With respect to compilers, I suspect hashing is more
efficient. However, I think there are legitimate situations where a
tree search may be more efficient.

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