Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!ima!johnl
From: johnl@ima.UUCP
Newsgroups: mod.compilers
Subject: Extensible hash tables
Message-ID: <489@ima.UUCP>
Date: Wed, 18-Feb-87 11:59:53 EST
Article-I.D.: ima.489
Posted: Wed Feb 18 11:59:53 1987
Date-Received: Thu, 26-Feb-87 20:00:33 EST
Sender: johnl@ima.UUCP
Lines: 20
Approved: compilers@ima.UUCP

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]
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | cca}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request