One-Probe Search

single word of memory, knowing only the size of the data structure. We
describe a randomized dictionary where a lookup returns the correct
answer with probability 1-epsilon, and otherwise returns "dont know".
The lookup procedure uses an expander graph to select the memory
location to probe. Recent explicit expander constructions are shown to
yield space usage much smaller than what would be required using a
deterministic lookup procedure. Our data structure supports efficient
deterministic updates, exhibiting new probabilistic guarantees on
dictionary running time.