My idea is to maintain an ArrayList **pool** to store values inserted, an HashMap **index** to store the mapping from values to their indices and a Queue **holes** to store all the "holes" after remove value in **pool**. To get a random element in the set, simply keep generating random index until the corresponding value in **pool** is not a hole (nonempty). To lower the retries, the RandomSet keeps the number of holes (size of **holes**) less than half of the size of the **pool**. Therefore the probability of 1 retry is 50%, of 2 retries is 25%, of 3 retries is 12.5 and so on. The probability of more than 3 reties is small. Therefore we could consider the complexity of getRandom is constant in average.

To achieve this, every time remove an element from the RandomSet, check whether the number of holes is larger than half of the pool. If it is, it constructs a new ArrayList **newPool**, reconstructs the mapping from values to indices and empties the **holes**. It takes O(n) time to reconstruct them but like appending an **ArrayList**, the possibility is low. The average time complexity is O(1) for each remove.

When inserting a new element, exam if there are available holes. If it is, poll a hole from the **holes** and put the new element to that hole in **pool**. If not, just append it to **pool** with a new mapping in **index**.

```
public class RandomizedSet {
private int count;
private ArrayList<Integer> pool;
private Map<Integer, Integer> index;
private Queue<Integer> holes;
private Random random;
/** Initialize your data structure here. */
public RandomizedSet() {
this.count = 0;
this.pool = new ArrayList<Integer>();
this.index = new HashMap<Integer, Integer>();
this.holes = new LinkedList<Integer>();
this.random = new Random();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (index.containsKey(val)){
return false;
}
Integer i = this.holes.poll();
if (i != null) { /* There are still holes in the holes pool */
this.pool.set(i, val);
this.index.put(val, i);
} else { /* There are no holes left in the holes pool. Extends the pool in this case */
this.pool.add(val);
this.index.put(val, this.pool.size() - 1);
}
this.count++;
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!index.containsKey(val)) {
return false;
}
int i = this.index.get(val);
this.holes.offer(i);
this.pool.set(i, null);
this.index.remove(val);
this.count--;
if (this.count * 2 < this.pool.size()) {
ArrayList<Integer> newPool = new ArrayList<Integer>();
int curr = 0;
this.index.clear();
for (Integer p: this.pool) {
if (p != null) {
newPool.add(p);
this.index.put(p, curr++);
}
}
this.pool = newPool;
this.holes = new LinkedList<Integer>();
}
return true;
}
/** Get a random element from the set. */
public int getRandom() {
Integer ret = null;
while (ret == null) {
int randomIndex = this.random.nextInt(this.pool.size());
ret = this.pool.get(randomIndex);
}
return ret;
}
}
```