You can get this with an ArrayList/HashMap pair (where the map will store the index of objects in the list) if you make list removal unordered. On removal, instead of shifting all subsequent elements in the list down one position, you just move the last element to fill the space of the removed item. Then there are at most two different elements that need to be touched during removal. A quick example (which I haven't tested and hope I didn't bungle):
class SpecialSet<E> extends AbstractSet<E> implements Set<E> {
private final List<E> list = new ArrayList<>();
private final Map<E,Integer> indexMap = new HashMap<>();
@Override
public boolean add(E e) {
if (contains(e)) return false;
indexMap.put(e, list.size());
list.add(e);
return true;
}
@Override
public boolean remove(Object o) {
Integer indexBoxed = indexMap.remove(o);
if (indexBoxed == null) return false;
int index = indexBoxed;
int last = list.size() - 1;
E element = list.remove(last);
if (index != last) {
indexMap.put(element, index);
list.set(index, element);
}
return true;
}
public E removeRandom() {
E element = list.get((int)(Math.random() * size()));
remove(element);
return element;
}
@Override
public boolean contains(Object o) {
return indexMap.containsKey(o);
}
@Override
public Iterator<E> iterator() {
return list.iterator();
}
@Override
public int size() {
return list.size();
}
}
Depending on what object equality testing behavior you want, you maybe could swap out the HashMap for an IdentityHashMap for a little better speed.