A set with insert, remove and a random element, all O(1): the values in an array, so a random index picks one, and a hash map from each value to its index, so remove can fill the hole with the last value. Against the array alone, which scans.
This interactive visualization needs JavaScript.