Perfect hashing using sparse matrix packing

摘要

This article presents a simple algorithm for packing sparse 2-D arrays into minimal 1-D arrays in O(r2) time. Retrieving an element from the packed 1-D array is O(1). This packing algorithm is then applied to create minimal perfect hashing functions for large word lists. Many existing perfect hashing algorithms process large word lists by segmenting them into several smaller lists. The perfect hashing function described in this article has been used to create minimal perfect hashing functions for unsegmented word sets of up to 5000 words. Compared with other current algorithms for perfect hashing, this algorithm is a significant improvement in terms of both time and space efficiency.