ON THE DESIGN OF A MACHINE-INDEPENDENT PERFECT HASHING SCHEME

This paper proposes a new approach to be used for assigning keywords to addresses in the way that no two different keywords are assigned in the same address. In this approach, the assigned address of each keyword is determined as following form: address <-- v1 (the keyword's ith character) + v2 (the keyword's jth character), where v1 and v2 are two integer-valued functions defined on the set of twenty-six English letters. The approach can be used for searching reserved words in compilers, function names in Operating Systems and so on. In considering heuristics to design the v1 and v2 functions, we were led to develop a letter-oriented merging-and-exchanging algorithm that finds the letter value assignments for v1 and v2 and achieves the reducing blank spaces in the constructed table.