Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 1 is the only number in the set, getRandom always return 1.
randomSet.getRandom();

 1 public class RandomizedSet {
 2     HashMap<Integer, Integer> map;
 3     ArrayList<Integer> arr;
 4 
 5     /** Initialize your data structure here. */
 6     public RandomizedSet() {
 7         map = new HashMap<Integer, Integer>();
 8         arr = new ArrayList<Integer>();
 9     }
10     
11     /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
12     public boolean insert(int val) {
13         if (map.containsKey(val)) return false;
14         arr.add(val);
15         map.put(val, arr.size()-1);
16         return true;
17     }
18     
19     /** Removes a value from the set. Returns true if the set contained the specified element. */
20     public boolean remove(int val) {
21         if (!map.containsKey(val)) return false;
22         int lastItem = arr.get(arr.size()-1);
23         if (val != lastItem) {
24             int index = map.get(val);
25             arr.set(index, lastItem);
26             map.put(lastItem, index);
27         }
28         arr.remove(arr.size()-1);
29         map.remove(val);
30         return true;
31     }
32     
33     /** Get a random element from the set. */
34     public int getRandom() {
35         return arr.get((int)(Math.random()*arr.size()));
36     }
37 }
38 
39 /**
40  * Your RandomizedSet object will be instantiated and called as such:
41  * RandomizedSet obj = new RandomizedSet();
42  * boolean param_1 = obj.insert(val);
43  * boolean param_2 = obj.remove(val);
44  * int param_3 = obj.getRandom();
45  */