A backtracking method for constructing perfect hash functions from a set of mapping functions (Q1059411)

Given a set of mapping functions \(h_ j(k)\) from key space to address space (AS) the problem of constructing a perfect hashing scheme is to find a hash indicator table (HIT): iff HIT \([h_ j(k)]=j\) then k is stored in AS \([h_ j(k)].\) A backtracking method superior to those proposed previously (single-pass and multipass methods) is presented, which can always find for given mapping functions a perfect hash function when such a function does exist.