Storing a Sparse Table with 0 (1) Worst Case Access Time
Michael L. Fredman, János Komlós, Endre Szemerédi · Journal of the ACM · 1984
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.