Simple and Space Efficient Minimal Perfect Hash Functions 2007 (wads07) 计算机科学

Simple and Space-EfficientMinimal Perfect Hash Functions ⋆Fabiano C. Botelho1, Rasmus Pagh2 and Nivio Ziviani11 Dept. of Computer Science, Federal Univ. of Minas Gerais, Belo Horizonte, Brazil {fbotelho,nivio}@dcc.ufmg.br2 Computational Logic and Algorithms Group, IT Univ. of Copenhagen, Denmark pagh@itu.dkAbstract. A perfect hash function (PHF) h : U → [0, m − 1] for a key set S is a function that maps the keys of S to unique values. The minimum amount of space to represent a PHF for a given se