Two results on tables
type: Item
instance of: scholarly article
title: Two results on tables
zbMATH Open document ID: 0584.68066
DOI: 10.1016/0020-0190(86)90041-4
author: Christiaan T. M. Jacobs
author: Peter van Emde Boas
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
review text: \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.].
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3936523
zbMATH Keywords: single-probe table lookup strategies
zbMATH Keywords: perfect hashing
MaRDI profile type: Publication
full work available at URL: 0020-0190(86)90041-4
OpenAlex ID: W2055618684
cites work: Storing a Sparse Table with 0 (1) Worst Case Access Time
cites work: Q3219751
cites work: Should Tables Be Sorted?
description: scientific article; zbMATH DE number 3936523