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.