(Java) data structure for fast insertion, deletion, and RANDOM SELECTION
algorithm, data-structures, hashset, java, performance
Solution
You can use combination of HashMap and ArrayList if memory permits as follows:-
- Store numbers in ArrayList arr as they come.
- Use HashMap to give mapping arr[i] => i
- While generating random select random form arrayList
Deleting :-
- check in HashMap for num => i
- swap(i,arr.size()-1)
- HashMap.remove(num)
- HashMap(arr[i])=> i
- arr.remove(arr.size()-1)
All operation are `O(1)` but extra `O(N)` space
Problem
I need a data structure that supports the following operations in O(1): - myList.add(Item) - myList.remove(Item.ID) ==> It actually requires random access myList.getRandomElement() (with equal probability) --(Please note that getRandomElement() does not mean random access, it just means: "Give me one of the items at random, with equal probability") Note that my items are unique, so I don't care if a List or Set is used. I checked some java data structures, but it seems that none of them is the solution: - HashSet supports 1,2 in O(1), but it cannot give me a random element in O(1). I need to call mySet.iterator().next() to select a random element, which takes O(n). - ArrayList does 1,3 in O(1), but it needs to do a linear search to find the element I want to delete, though it takes O(n) Any suggestions? Please tell me which functions should I call? If java does not have such data structure, which algorithm should I use for such purpose?