|Extensible hash tables think!cullvax!drw%eddie.mit.edu (1987-02-18)|
|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.
[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]
Return to the
Search the comp.compilers archives again.