A backtracking method for constructing perfect hash functions from a set of mapping functions |
| |
Authors: | W P Yang M W Du |
| |
Institution: | (1) Institute of Computer Engineering, National Chiao Tung University, 45 Po Ai Street, Hsinchu, Taiwan, Republic of China |
| |
Abstract: | This paper presents a backtracking method for constructing perfect hash functions from a given set of mapping functions. A hash indicator table is employed in the composition. By the nature of backtracking, the method can always find a perfect hash function when such a function does exist according to the composing scheme. Simulation results show that the probability of getting a perfect hash function by the backtracking method is much higher than by the single-pass and multipass methods previously proposed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|