# Extensible hash tables

## think!cullvax!drw%eddie.mit.edu (Dale Worley)

Wed, 18 Feb 87 11:59:53 est

*From comp.compilers*

| List of all articles for this month |

**Date: ** | Wed, 18 Feb 87 11:59:53 est |

**From: ** | think!cullvax!drw%eddie.mit.edu (Dale Worley) |

An algorithm that extends (but does not shrink) a hash table is: When

the table 'fills', allocate a new one of twice the original size.

Each reallocation is slow, but on the n-th extension, the total time

taken for all of the reallocations is

O(1 + 2 + 4 + ... + 2^n) = O(2^(n+1))

which is linear in the number of entries (2^n) added so far! This can

probably be modified for contraction as well.

Dale

[This is probably the best approach so long as running out of space isn't

a problem. Then again, if running out of space really isn't a problem,

you might as well allocate a huge symbol table to minimize the likelihood

of hash collisions. -John]

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.