Construction of minimal perfect hashing function based on the approximation of piecewise linear function. (English) Zbl 0792.68028
Summary: The step hashing function is presented. This function is an extended version of the Sprugnoli’s quotient reduction function. Two construction algorithm are proposed. These algorithms are derived from the condition that the hashing function is ordered minimal and the approximation of a piecewise linear function, respectively. In particular, the computational complexity of the latter is \(O(n)\) time.