Filling up an array randomly

I'm looking to build a data structure where an array is filled at a random empty position by calling add(). Once a position is filled it cannot be overwritten by another add(). Calling remove(i) frees the position at A[i]. Calls to add() and remove() can be intermixed.

My first thought was to randomly generate a numbers between 0 and n-1 each time add() is called. If it is empty, fill it; if it is full, do a sequential search until an empty one is found. This however has two problems: 1) if the array is mostly full it will take close to O(n) time 2) the random selection will not be uniform.

My second thought was to use a shuffle on the number 1 to n-1 and add in this order, however this doesn't support remove().

Is there a way to implement this guaranteeing constant performance for add() and remove()?