W.G. Griswold, G.M. Townsend, "The Design and I
mplementation of Dynamic Hashing for Sets and Tables in Icon",
Software - Practice and Experience, Wiley and Son, vol.23,
(no.4):351-67, April 1993.
Two key features in the Icon programming language are tables and sets. An
Icon program may use one large set or table, or thousands of small ones. To
improve space and time performance for these diverse uses, their hashed data
structures were reimplemented to dynamically resize during execution,
reducing the minimum space requirement and achieving constant-time access to
any element for virtually any size set or table. The implementation is
adapted from Per-Äke Larson's dynamic hashing technique by using well-known
base-2 arithmetic techniques to decrease the space required for small tables
without degrading the performance of large tables. Also presented are
techniques to prevent dynamic hashing from interfering
with other Icon language features. Performance measurements are included
to support the results.