Hash table methods for case statements

ABSTRACT

The CASE statement evaluates an expression, selects an action according to the value of the expression and then executes the action. The most efficient runtime behavior is exhibited when the action can be selected via a jump table, which provides an entry for every possible value in the range of the expression but has execution time that is constant as the number of cases increases. If the range of the expression is too large then the jump table becomes impractical because of excessive space requirements. Implementations of the CASE statement that limit table size to increase linearly with the number of cases either require linear execution time or capitalize on the subrange structure of the expression to reduce the time requirement. Hash methods also limit space requirements, and in the case of hashing with chaining to resolve collisions can provide log n time performance. Open addressing methods provide constant time performance as the number of cases increases and, since the hash table is static and can be closely packed in an optimal fashion, the execution time can be limited to an average of less than two probes per selection even for closely packed tables. Open addressing in optimally packed tables leads to selection of the default case in fewer than eight probes. One can choose a hash function that facilitates extension of allowed data types from the usual byte and integer types to strings and double precision integers with minimal penalty in execution time.

REFERENCES

• 1: SALE 81. Sale, A., The Implementation of CASE Statements in PASCAL, Softw. Pract. and Exper., 11(1981)929-42.
• 2: Renzo Sprugnoli, Perfect hashing functions: a single probe retrieving method for static sets, Communications of the ACM, v.20 n.11, p.841-850, Nov. 1977 [doi>10.1145/359863.359887]
• 3: Richard J. Cichelli, Minimal perfect hash functions made simple, Communications of the ACM, v.23 n.1, p.17-19, Jan. 1980 [doi>10.1145/358808.358813]
• 4: BRENT75. Brent, R., Reducing the Retrieval Time in Scatter Storage Techniques, CACM, 18(1975)651-6.
• 5: Gordon Lyon, Packed scatter tables, Communications of the ACM, v.21 n.10, p.857-865, Oct. 1978 [doi>10.1145/359619.359633]
• 6: James R. Bell, The quadratic quotient method: a hash code eliminating secondary clustering, Communications of the ACM, v.13 n.2, p.107-109, Feb 1970 [doi>10.1145/362007.362040]
• 7: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 8: MAUR7,5 Maurer, W. and T. Lewis, Methods, Comp. Surv., 7(1975)
• 9: Robert Morris, Scatter storage techniques, Communications of the ACM, v.11 n.1, p.38-44, Jan. 1968 [doi>10.1145/362851.362882]
• 10: P. Quittner , S. Csóka , S. Halász , D. Kotsis , K. Várnai, Comparison of synonym handling and bucket organization methods, Communications of the ACM, v.24 n.9, p.579-583, Sept. 1981 [doi>10.1145/358746.358760]

INDEX TERMS

Keywords:
Case Statements, Compiler Implementation, Computer Architecture, Hashing, Open Addressing