Premium
Some recursive constructions for perfect hash families
Author(s) -
Atici M.,
Magliveras S. S.,
Stinson D. R.,
Wei W.D.
Publication year - 1996
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/(sici)1520-6610(1996)4:5<353::aid-jcd4>3.0.co;2-e
Subject(s) - hash function , perfect hash function , mathematics , combinatorics , set (abstract data type) , construct (python library) , discrete mathematics , dynamic perfect hashing , double hashing , theoretical computer science , hash table , computer science , programming language
An ( n, m, w)‐perfect hash family is a set of functions F such that for each f ϵ F, and for any X ⊆ {1,…, n } such that |X| = w, there exists at least one f ϵ F such that f | x is one‐to‐one. Perfect hash families have been extensively studied by computer scientists for over 15 years, mainly due to their applications in database management. In particular, much attention has been given to finding efficient algorithms to construct perfect hash families. In this article, we study perfect hash families from a combinatorial viewpoint, and describe some new recursive constructions for these objects. © 1996 John Wiley & Sons, Inc.