Re: symbol tables and search tries

Hans Aberg wrote:
> John Levine wrote:


> [I make my hash tables big enough that the chains are short, i.e.,
> design so that k>=N so it's O(1). Hash headers need only be one
> word pointers, so pick a number larger than the number of symbols
> you expect in a large program, say, 10,000, and use that. So it adds
> 40K to the size of the program, that's down in the noise these days.
> -John]


I am agree that hash tables are more suitable in practice than
balanced trees.


If you look at GCC, it uses extendable hash tables in many places.
The hashtables are very compact (one element takes only one pointer in
the table) because no chains are used. Also deletions of elements
from the hash table are permitted. The hashtable are rebuilt when
there are many collisions (after the rebuilding the size can be bigger
or smaller). Big number of collision might be because there are many
elements in the table or too many deletions were made.


So the hashtables in gcc are better practically in all respects than
balanced trees (speed and size). They permit deletion too as balanced
trees. Although the balance trees have one adavantage which is
possibility to traverse elements in some order (gcc hashtables permit
to do only unordered traversing easily).


As I know hashtables form gcc is used in many order compilers and
interpreters.


A standalone version of the hashtables can be found on
http://cocom.sf.net. Its description is on
http://cocom.sourceforge.net/ammunition-5.html

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