Tetris-Hashing or optimal table compression

In this paper, we present a new method for mapping a static set of n keys, each an integer between 0 and N-1, into a hash table of size n without any collision. Our data structure requires only an additional array of n intege rs, each less than n, and achieves a worst-case lookup time of O(1). This m ethod is based on a randomized compression scheme, and it finds a minimal p erfect hash function in average time O(n). Our concept can be easily adapte d for dynamic key sets. Then, the hash table has no longer minimal size but the storage location remains very small. Because of its simplicity our app roach is particularly interesting for practical purposes. (C) 2001 Elsevier Science B.V. All rights reserved.