Re: symbol tables and search tries

Matthias Blume <blume@tti-c.org> writes:
>If you double your hashtable when the load factor exceeds 1, then you
>waste an expected number of buckets that is bounded by something very
>close to the number of actual elements in the table. If you do not
>double the size, then you have to use more chain links in each bucket.
>In a typical implementation, the required number of extra pointers is
>the same as the number of those wasted buckets.


If you are using chaining, the number of wasted pointers is the number
of buckets: Even if a bucket is used, there is an unused pointer at
the end of the chain. So you can ensure that no more than one pointer
per element is wasted by always keeping the load factor >=1 (e.g., by
doubling when the load factor reaches 2).


Now if we compare this to a binary tree, the tree always wastes one
pointer per element: there are two pointers in each element, and one
pointer to the element, so one pointer is wasted on average.


So, if you can afford the space for a tree, you can also afford the
space for a hash table with chaining that doubles when the load factor
reaches 2.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html

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