(Java) data structure for fast insertion, deletion, and RANDOM SELECTION

Question

I need a data structure that supports the following operations in O(1):

1. myList.add(Item)
2. myList.remove(Item.ID) ==> It actually requires random access

3. 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:

1. 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).
2. 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?

Answer 1

You can use combination of HashMap and ArrayList if memory permits as follows:-

1. Store numbers in ArrayList arr as they come.
2. Use HashMap to give mapping arr[i] => i
3. While generating random select random form arrayList

Deleting :-

1. check in HashMap for num => i
2. swap(i,arr.size()-1)
3. HashMap.remove(num)
4. HashMap(arr[i])=> i
5. arr.remove(arr.size()-1)

All operation are O(1) but extra O(N) space

Answer 2

You can use a HashMap (of ID to array index) in conjunction with an array (or ArrayList).

add could be done in O(1) by simply adding to the array and adding the ID and index to the HashMap.

remove could be done in O(1) by doing a lookup (and removal) from the HashMap to find the index, then move the last index in the array to that index, update that element's index in the HashMap and decreasing the array size by one.

getRandomElement could be done in O(1) by returning a random element from the array.

Example:

Array: [5,3,2,4]
HashMap: [5->0, 3->1, 2->2, 4->3]

To remove 3:

Look up (and remove) key 3 in the HashMap (giving 3->1)
Swap 3 and, the last element, 4 in the array
Update 4's index in the HashMap to 1
Decrease the size of the array by 1

Array: [5,4,2]
HashMap: [5->0, 2->2, 4->1]

To add 6:

Simply add it to the array and HashMap

Array: [5,4,2,6]
HashMap: [5->0, 2->2, 4->1, 6->3]