An algebraic approach to Cichelli's perfect hashing |
| |
Authors: | M. Gori G. Soda |
| |
Affiliation: | (1) Dipartimento di Sistemi e Informatica, Università di Firenze, Via S. Marta, 3, 50139 Firenze, Italy |
| |
Abstract: | The aim of this paper is to describe a new approach to building minimal and perfect hash functions for a predefined set of keys. Several papers have dealt with this problem and proposed various kinds of functions. This study is based on a function whose address depends both on the letter codes and the letter position in the key, and therefore represents an extension of Cichelli's function. The weights associated with the position are considered to be fixed, and letter code computing is considered to be an interpolation problem. As a result, hash building only requires the solution of an algebraic linear system and then the time complexity is polynomialO(n3). |
| |
Keywords: | E2 |
本文献已被 SpringerLink 等数据库收录! |
|