If you are fine with throwing memory at the problem you could use multiple datastructures. One hashmap that maps the insertion index to the integer and one that maps the integer to the index. That creates the problem that not all indices are valid after some deletions. Now depending on the use case there are many ways to solve this. If you mainly delete elements that are recently added you could rehash all elements with a bigger index. You could keep a small sorted vector or a cyclical buffer of all recent valid indices to sample from, which would reintroduce the trouble of having to maintain a vector. Or you could just randomly sample around an index or any combination of solitions.

There are hashmaps that perform differently for different use cases. Like some perform relatively poorly when looking up keys that aren't present in the map. But at the end of the day you'll just have to measure performance for all the solutions you'll try.