A distribution-sensitive dictionary with low space overhead
John Howat

The time required for a sequence of operations on a data structure is usually
measured in terms of the worst possible such sequence. This, however, is often
an overestimate of the actual time required. Distribution-sensitive data
structures attempt to take advantage of underlying patterns in a sequence of
operations in order to reduce time complexity, since in many real-world
applications, access patterns are non-random. Unfortunately, many of the
distribution-sensitive structures in the literature require a great deal of
space overhead in the form of pointers. We present a dictionary data structure
that makes use of both randomization and existing space-efficient data
structures to yield very low space overhead while maintaining distribution
sensitivity in the expected sense.