Two results on tables

Abstract

A.C. Yao (1981) has determined the maximal size of a finite universe U such that it is possible to store all subsets A of U with k elements in a table of k slots in such a way that membership in A can be determined in a single probe. In his model it is assumed that all elements of A are physically stored in the table. If this assumption is relaxed and arbitrary elements in U can be stored in order to encode subsets A, then Yao's upper bound is no longer valid. It fails for trivial reasons only: a single probe lookup strategy only exists when it is possible to encode arbitrary subsets of U by a bitmap. Our second result is an improvement of the optimal program size for perfect hash functions, solving an open problem from Slot and Van Emde Boas (1984): For every value u, value k ≤ u, and every subset A of U = {0, ..., u - 1} there exists a perfect hash function F which scatters A completely into a hash table of size O(k), such that the program size of F is O(k·log log k + log log u) and the evaluation time of F is O(1). These estimates are expressed in standard RAM space and instructions respectively. This improves the O(k·log k + log log u) upper bound established by Mehlhorn (1984) and Slot and Van Emde Boas (1984). © 1986.