Storing a Sparse Table with O(1) Worst Case Access Time 1984 (fks perfecthash)

Storing a Sparse Table with O(1) Worst Case Access TimeMICHAEL L. FREDMAN AND J/~NOS KOMLOSUniversity of Califorma, San Dtego, La Jolla, CahformaANDENDRE SZEMERI3DIUntverstty of South CarohnaAbstract. A data structure for representing a set of n items from a umverse of m items, which uses space n + o(n) and accommodates membership queries m constant time is described. Both the data structure and the query algorithm are easy to ~mplement.Categories and Subject Descriptors: E. 1 IData Strncture