  We consider space efficient hash tables that can grow and shrink dynamically
and are always highly space efficient, i.e., their space consumption is always
close to the lower bound even while growing and when taking into account
storage that is only needed temporarily. None of the traditionally used hash
tables have this property. We show how known approaches like linear probing and
bucket cuckoo hashing can be adapted to this scenario by subdividing them into
many subtables or using virtual memory overcommitting. However, these rather
straightforward solutions suffer from slow amortized insertion times due to
frequent reallocation in small increments.
  Our main result is DySECT ({\bf Dy}namic {\bf S}pace {\bf E}fficient {\bf
C}uckoo {\bf T}able) which avoids these problems. DySECT consists of many
subtables which grow by doubling their size. The resulting inhomogeneity in
subtable sizes is equalized by the flexibility available in bucket cuckoo
hashing where each element can go to several buckets each of which containing
several cells. Experiments indicate that DySECT works well with load factors up
to 98\%. With up to 2.7 times better performance than the next best solution.

Data Structures and Algorithms