The trick is pairing a hash map with a dynamic array. The hash map stores each value mapped to its index in the array. The array holds the values themselves.
Inserting means appending to the array and recording the new index in the map. Getting a random element means picking a random array index, which is .
Deletion is the clever part. You can't remove from the middle of an array in . Instead, you swap the target element with the last element, update the swapped element's index in the map, then pop the last element. This keeps the array compact without shifting anything.