The Self-Indexed Search Algorithm: A bit-level approach to minimal perfecthashing

A novel algorithm for generating minimal perfect hash tables for large amou nts of data is presented. Functions considered are of the form h (key) = g( f(1)(key)) + f(2)(key), where g is retrieved from a lookup table, and f(i) are bit strings contained in the key itself. Since keys are considered as b inary strings, and only a few bits from the key itself are used to produce the address in the hash table, search time is independent of the length of the keys and the size of the character set. (C) 1999 Published by Elsevier Science B.V. All rights reserved.