Suitable java collection for fast get and fast removal

Question

I would like to know if there is a suitable java interface for "fast" get (by index) and "fast" removal. By "fast" I mean better than O(n).

EDIT: The get method is only needed for randomly selecting an element from the collection. Also, the title should say "collection" rather than "interface".

Answer 1

A balanced binary search tree has O(log n) "get" and "remove" operations. A hash table implements these same operations in O(1) time. In Java you can use the TreeMap or HashMap classes. For example:

TreeMap<Integer, String> map = new TreeMap<>();
map.put(0, "hello");
map.put(1, "world");
map.remove(0);

If you don't care about the order of items you can use an ArrayList. Naturally "get" is O(1). To remove an item move the last item into the place of the one that you remove, this gives you an O(1) "remove." That is:

temp = list.remove(list.size()-1);
return list.set(index, temp);

Answer 2

I am not sure that I understand how you suggest to deduce which index you want to get the object from.

If you are looking for fast get() and fast remove() operation - what is wrong with standard HashMap<Object, Object> (i.e. using the object itself as a key)?

Then your get()/remove() operations will be dependent on your implementation of hashCode() and equals() methods and can be O(1)