Two results on tables (Q1069703)

\textit{A. C. Yao} [J. Assoc. Comput. Mach. 28, 615-628 (1981; Zbl 0462.68079)] 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 a paper by \textit{C. Slot} and \textit{P. van Emde Boas} [Proc. 16th ACM Symp. Theory of Computing, 391-400 (1984)]: For every value u, value \(k\leq 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\cdot \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\cdot \log k+\log \log u)\) upper bound established by \textit{K. Mehlhorn} [Data structures and algorithms. Vol. I: Sorting and searching (Berlin, 1984; Zbl 0556.68003)] and Slot and van Emde Boas [loc. cit.].