Premium
The design and implementation of dynamic hashing for sets and tables in icon
Author(s) -
Griswold William G.,
Townsend Gregg M.
Publication year - 1993
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380230402
Subject(s) - computer science , icon , hash table , table (database) , dynamic perfect hashing , set (abstract data type) , hash function , linear hashing , key (lock) , perfect hash function , space (punctuation) , theoretical computer science , algorithm , database , programming language , double hashing , operating system
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.