An extendable data structure for incremental stable perfect hashing

We consider the problem of dynamically assigning n elements unique indices, known as hashcodes, in the range [(1+o(1))n]. This problem is known as perfect hashing and is considered a fundamental building block in the design of more involved data structures. The challenge we address is that of designing a data structure that meets several, seemingly opposing, requirements: (1) the range and the space of the data structure must be, at all times, proportional to the current cardinality nt of the input set, and (2) the hashcodes it assigns must be stable in that the hashcode of an element must not change while the element is continuously in the set. A simple argument shows that these two desiderata are impossible to achieve when arbitrary deletions and insertions are allowed.