© 1991 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
On the Design of a Machine-Independent Perfect Hashing Scheme
1 Institute of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, Taiwan 62107, China, 2 Department of Electronics, Feng Chia University, Taichung, Taiwan 40724, China, 3 Department of Applied Mathematics, National Chung Hsing University, Taichung, Taiwan 40227, China
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.
Received February 1988. revised May 1988.
* Institute of Computer Science and Information Engineering, National Chung Cheng University, Chiayi, Taiwan 62107, Republic of China
Department of Electronics, Feng Chia University, Taichung, Taiwan 40724, Republic of China
¶ Department of Applied Mathematics, National Chung Hsing University, Taichung, Taiwan 40227, Republic of China