I have a data structure that implements the following operations all in $O(1)$:
- $\text{insert(x)}$, inserts a value into the data structure and returns a unique key $k$ to the value
- $\text{delete(k)}$, deletes the value at key $k$ and returns it
- $\text{get(k)}$, returns a reference to the element at key $k$
Internally the storage is simply a contiguous array $A$ of $(x, v)$ tuples. $x$ is either a value or is used to store a freelist. $v$ is a version tag. When $v$ is odd $x$ is a valid item with version $v$. When $v$ is even $x$ is unoccupied and is re-used to store the index of the next unoccupied item after this.
The key $k$ is a tuple of $(i, v)$, an index into the contiguous array and a version. Only when $A[k_i]_v = k_v$ is this key valid and contained in the data structure. Finally, on every insert and delete $A[i]_v$ is incremented.
Now this is very similar to a memory allocator (which returns pointers instead of keys), but the difference is that physical memory locations can be safely re-used here without spurious errors where old pointers point to new items. So from the perspective from the user every key that $\text{insert}$ ever gives is unique.
The question is, what is a good name for this data structure? I've seen similar data structures called "slot maps" in game development, but it's not quite the same. They don't use versioning and support dense iteration through using two indirections (one key -> idx and idx -> item), whereas this data structure can have a sparse memory layout.
It's also very similar to a slab allocator, but again it has added safety of returning permanently unique keys, even when re-using storage.
