6

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

Alexandre Vandermonde
  • 579
  • 1
  • 6
  • 13
  • Are you talking about a sequential container, where the order of elements do not change during removal? Well, the interface `java.util.List` exists, but as far as I know there is no implementation shipped with Java. – nosid Oct 05 '13 at 19:51
  • Yes, that's right; the order of elements are not supposed to change during removal. I am currently using a List, but for an ArrayList, remove is O(n), and for a LinkedList, get is O(n). – Alexandre Vandermonde Oct 05 '13 at 19:56
  • @Dave Newton Thanks for the edit! Bye the way, why doesn't Stack Overflow support LaTeX? – Alexandre Vandermonde Oct 05 '13 at 19:57
  • @nosid On second thought, it is possible to do it with changing order. I actually only need to pick a random element with the get method. – Alexandre Vandermonde Oct 05 '13 at 19:59
  • If the order can be changed, you can use the approach described at the end of @Joni's answer. Please clarify your question accordingly. – nosid Oct 05 '13 at 20:02

3 Answers3

6

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);
Joni
  • 108,737
  • 14
  • 143
  • 193
  • That's probably true, let's see if OP confirms. – Joni Oct 05 '13 at 19:56
  • @Joni Thanks for the suggestion! I'll have to think about how the TreeMap could be implemented considering that I don't really wan't to keep track of the indices but merely use the get method for random selection. About ArrayList: is move O(1), then? – Alexandre Vandermonde Oct 05 '13 at 20:03
  • @AlexandreVandermonde, by "move" I mean remove the last item and set the index you want to remove: both operations are O(1). – Joni Oct 05 '13 at 20:09
  • @Joni I see your edit. Thanks! It seems a bit counterintuitive that a remove operation should not be void, but I can certainly see it being useful in this case. – Alexandre Vandermonde Oct 05 '13 at 20:17
1

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)

Germann Arlington
  • 3,315
  • 2
  • 17
  • 19
  • How would such an implementation of hashCode() look? Admittedly, I am not quite used to working with HashMap:s. – Alexandre Vandermonde Oct 05 '13 at 20:11
  • Read about hashCode() and equals() implementation for HashMap (Google). Ideally (the best for HashMap storage) implementation of hashCode() should return unique integer representation of object's state, example: unique object ID may be a good choice. Then the hashCode() will define which HashMap bucket the object will be stored in and therefore you will be able to access to the objects via bucket index (like array index) directly – Germann Arlington Oct 05 '13 at 20:18
0

I don't believe there is an implementation of List in the JDK which is faster than O(n) for both lookup and removal.

Data structures which might suit you are the rope, the indexable skiplist, and the enfilade. You might be able to find implementations of those you can use on the web, or in one of the major collections libraries (Guava, Commons Collections, Trove, etc).

However, if what you really want is not fast lookup and removal, but fast random selection and removal, you could use an open-addressed hashtable. You get O(1) lookup by value (not that you care about that), O(1) removal by value, and O(1) selection of a random value. You can select a random value by picking a random slot in the table and using the entry in it; if it's empty, try again.

Tom Anderson
  • 46,189
  • 17
  • 92
  • 133