Suitable java collection for fast get and fast removal

java

Solution

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);

Problem

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".

Original source