A set data structure to insert, remove and get a random element in constant time

If you are a coder, and you need to implement a set data structure that requires insert, remove and "get random element" operations all working in constant time, so here the solution!

Simply use a dynamic array (for example: vector in C++ or ArrayList in Java) and an hash table (for example: unordered_map in C++ 11 or HashMap in Java) together.

The key idea is to store the set elements consecutively in the array, and keep track of their indexes in the (inverted) hash table. Thus, the hash table keys are the array values (i.e. the set elements) and the hash table values are the array indexes.

Now the semantics of the operations.

INSERT(val): append the value at the end of the array, so at index array.size-1 (if the array is 0-based), and create a new entry in the hash table with val as key and array.size-1 as value. Obviously, you have also to check if val is already in the set. Anyway, the complexity is always O(1) (using amortized analysis).

REMOVE(val): use the hash table to get the array index of val, say it is ind. Get the last element in the array (the one in position array.size-1), say it is lastval. Swap the array elements at positions ind and array.size-1 (so you swap the values val and lastval). Decrease by 1 the array size (e.g. using pop_back in C++). Update the hash table entry for lastval with the value ind. Finally, remove the entry with key val from the hash table. Obviously, you have also to check that val is really contained in the set. Anyway, the complexity is always O(1) (using amortized analysis).

GET_RANDOM_ELEMENT(): this is now the easy part. Simply pick up a random integer r between 0 and vector.size-1 and return the r-th value from the vector. Complexity O(1).

Other operations like random access and value check are easy and O(1) as well!