Leetcode - Insert Delete GetRand

My code:

public class RandomizedCollection {
    HashMap<Integer, Set<Integer>> map =  new HashMap<Integer, Set<Integer>>();
    List<Integer> list = new ArrayList<Integer>();
    Random r = new Random();
    /** Initialize your data structure here. */
    public RandomizedCollection() {
        
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        boolean flag = false;
        if (!map.containsKey(val)) {
            flag = true;
            map.put(val, new LinkedHashSet<Integer>());
        }
        map.get(val).add(list.size());
        list.add(val);
        return flag;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int removed = map.get(val).iterator().next();
        map.get(val).remove(removed);
        if (removed < list.size() - 1) {
            Integer tail = list.get(list.size() - 1);
            list.set(removed, tail);
            map.get(tail).remove(list.size() - 1);
            map.get(tail).add(removed);
        }
        list.remove(list.size() - 1);
        if (map.get(val).size() == 0) {
            map.remove(val);
        }
        return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(r.nextInt(list.size()));
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

reference:
https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

这道题目还是挺有意思的。只是没能自己做出来。
有个小技巧是，如果我们想删除 ArrayList中的一个element，但是又想时间复杂度维持在 O(1),该如何做？？
不考虑顺序的情况下，可以把末尾的元素直接重写过去。
list.set(i, tail);
list.remove(tail);
然后再把末尾删除。 list 删除末尾的时间复杂度是 O(1)
set 时间复杂度是 O(1)
所以整体也是 O(1)

这里为什么要使用 LinkedHashSet?

Anyway, Good luck, Richardo! -- 09/30/2016

不一定非用LinkedHashSet, 但一定是 Set !
不能用 List, 否则会出错。

Anyway, Good luck, Richardo! -- 10/16/2016