Re: symbol tables and search tries

On 2006-01-30, Hans Aberg <haberg@math.su.se> 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). 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.


The average probe length for a hash table using chaining with N
elements distributed over M chains (buckets) is N/M. It is not O(N)
unless you do something naive like use a poor hash function or don't
maintain the load factor accordingly (for chains, allow the load
factor to vary between .5 and 2). Once the performance decays to
O(N), you are essentially using a linked list.


You don't need to choose M ahead of time. It's completely reasonable
to do a resize on the fly. This happens so infrequently that it's in
the noise. Doubling the number of chains for every resize is a
reasonable policy. This has been done in numerous free libraries and
works just fine (See Kaz's Kazlib or Vo's CDT from AT&T) for complete
working examples.


To respond to the original posters question, tries are only beneficial
if the keys are extremely long, and the hash function would dominate
the execution profile. Traditionally, symbols in compilers aren't all
that long (what was the original UNIX linker limit? John? [Eight]).
Tries also don't work well when the symbols have the same or similar
prefixes. You can fight this by changing the criteria for key
insertion into the trie. You can use the suffix of the key for
insertion if the prefixes are the same or similar. Or you can
alternate using characters from the prefix and suffix. Like a hash
function, a proper trie function is important, and you have to
consider the keys you're inserting in order to obtain good
performance.


Anyway, this is more of a data structure argument and has little to do
with compilers. See comp.programming for more discussion on this
topic.


-Clint

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