30 Jan 2006 02:05:00 -0500

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

[17 later articles] |

From: | haberg@math.su.se (Hans Aberg) |

Newsgroups: | comp.compilers |

Date: | 30 Jan 2006 02:05:00 -0500 |

Organization: | Mathematics |

References: | 06-01-085 06-01-111 |

Keywords: | symbols |

Posted-Date: | 30 Jan 2006 02:05:00 EST |

John Levine wrote:

*> >Why not using a balanced tree, like for example the std::map of C++? I*

*> >gives the minimum logarithmic search/insertion times without having to*

*> >bother about balancing, as in a hash map. Is the overhead too big?*

*> I don't understand what you're proposing. Balanced trees are O(log N)*

*> to search and require rebalancing whenever you insert something. Hash*

*> tables of the sort we usually use for compiler symbol tables are O(1)*

*> and balancing isn't an issue.*

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). 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. Or are you using another type of hash tables? And for

balanced trees, the insert time is logarithmic. If k is doubled when

too low, perhaps insert time is logarithmic for hash tables too.

--

Hans Aberg

[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]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.