Collection Class ArrayListMap

[Jeff Gent]

I'm in the transition from a beginner to a intermediate in my Java Foo, so I lack confidence in some of this. Wanted to get some advice from the masters.

I know to try and choose the best collection for the task, but I find sometimes that I need a collection to do a couple things quickly - mainly I want to know the index and value. Primarily, I need something fast on get(), indexOf, contains(). So here is my attempt to increase performance over an ArrayList by optimizing the return for the type of call by complementing it with a HashMap. It is a little slower on add() of an ArrayList and takes a little more memory for the map, but the trade off is fast returns when using indexOf() and contains(). I'm thinking the additional memory consumption is minor since it's using Objects, so it shouldn't have to store it twice... correct?

So looking for any advice, suggestions, comments.

Anyway, here are my quick benchmarks in ms running a 50,000 loop.

add()
50.0 ArrayList
90.0 HashMap
55.0 ArrayListMap

contains()
13790.0 ArrayList
61934.0 HashMap containsValue()
41.0 HashMap containsKey() using value as key
41.0 ArrayListMap

get()
1.0 ArrayList
1.0 ArrayListMap
3.0 HashMap

indexOf()
13639.0 ArrayList
19.0 ArrayListMap
19.0 HashMap using value as key

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class ArrayListMap<E> {

	private ArrayList<E> keyValue;
	private Map<E, Integer> valueKey;

	public ArrayListMap() {
		keyValue = new ArrayList<E>();
		valueKey = new HashMap<E, Integer>();
	}

	public ArrayListMap(final int capacity) {
		keyValue = new ArrayList<E>(capacity);
		valueKey = new HashMap<E, Integer>(capacity);
	}

	public void add(final E value) {
		keyValue.add(value);
		valueKey.put(value, valueKey.size());
	}

	public void clear() {
		keyValue.clear();
		valueKey.clear();
	}

	public int indexOf(final E value) {
		return valueKey.get(value);
	}

	public boolean contains(final E value) {
		return valueKey.containsKey(value);
	}

	public E get(final int key) {
		return keyValue.get(key);
	}

	public void set(final int key, final E value) {
		valueKey.remove(keyValue.get(key));
		keyValue.set(key, value);
		valueKey.put(value, key);
	}

	public int size() {
		return keyValue.size();
	}

	public void remove(final int key) {
		valueKey.remove(keyValue.get(key));
		keyValue.remove(key);
	}

	public void remove(final E value) {
		keyValue.remove(valueKey.get(value));
		valueKey.remove(value);
	}

	public void ensureCapacity(final int capacity) {
		if (valueKey.isEmpty()) {
			keyValue = new ArrayList<E>(capacity);
			valueKey = new HashMap<E, Integer>(capacity);
		} else {
			keyValue.ensureCapacity(capacity);
		}
	}

	public boolean isEmpty() {
		return keyValue.isEmpty();
	}

	public Object[] toArray() {
		return keyValue.toArray();
	}
	
	public ArrayList toArrayList() {
		return keyValue;
	}
}

[Winston Gutkowski]

Jeff Gent wrote:So looking for any advice, suggestions, comments.

A few:
1. In order to be most useful, I reckon your class should implement at least one of the collection interfaces. List<E> seems the most obvious, although in fact your class is closer to a Set (see below). You could even implement both.
2. Because you are storing your elements in a HashMap, you will not be able to store duplicates. If that's OK, great; but you should be aware of it.
3. If you want your set() method to replicate ArrayList's, then it needs to return an element. Also, you don't strictly need to do a remove() before you do the put().

But otherwise, congratulations - your first collection wrapper class. Fun, aren't they?

Winston

[Jeff Gent]

Thanks! I think for that Set, I meant to do the following. Since the value is what is being changed, it may not be there in the HashMap to change.

valueKey.remove(keyValue.get(key));
keyValue.set(key, value);
valueKey.put(value, key);

Also, thanks for the reminder that it doesn't support duplicates - I ran some checks and verified I'm not adding any in my overall program. I'll look into the implements - that's not something I've done yet. The whole implements, extends, abstract stuff is still something I'm learning and I find a bit confusing.

[Jeff Verdegan]

Winston Gutkowski wrote:

Jeff Gent wrote:So looking for any advice, suggestions, comments.

A few:
1. In order to be most useful, I reckon your class should implement at least one of the collection interfaces. List<E> seems the most obvious, although in fact your class is closer to a Set (see below). You could even implement both.

No class can fulfill both contracts. Equality pops to mind. There may be other incompatibilities, but nothing that I can think of at the moment.

He can of course still choose to implement both and document the deviations from the contracts, but I wouldn't advise it without a really pressing need.

[Winston Gutkowski]

Jeff Verdegan wrote:No class can fulfill both contracts. Equality pops to mind.

Yes, that's true; although the basic contract for both interfaces can be overriden (and is in some subclasses). It's often seemed a little odd to me that there is no hybrid of the two - ie, a List that can't contain duplicate values, or a Set that offers randomized access.

Winston

[Matthew Brown]

Winston Gutkowski wrote:It's often seemed a little odd to me that there is no hybrid of the two - ie, a List that can't contain duplicate values, or a Set that offers randomized access.

It doesn't provide random access, but a LinkedHashSet is a set with an order, which is a hybrid of List and Set to some extent.

[Martin Vashko]

Correct me if I'm wrong, but I'd say that removing an item should cause the indexes of subsequent items to be adjusted, which is not happening at the moment. Straightforward correction of this deficiency will make item removal an O(n) operation. Of course, depending on the need this might not pose a problem.

[Winston Gutkowski]

Martin Vajsar wrote:Correct me if I'm wrong, but I'd say that removing an item should cause the indexes of subsequent items to be adjusted...

Ah yes. Well spotted that man. I suppose you could define an interface of your own (SparseList?) that extends java.util.List but redefines some of the operations. It also tends to suggest that null values should be disallowed.

Winston

[Jeff Gent]

Martin Vajsar wrote:Correct me if I'm wrong, but I'd say that removing an item should cause the indexes of subsequent items to be adjusted, which is not happening at the moment. Straightforward correction of this deficiency will make item removal an O(n) operation. Of course, depending on the need this might not pose a problem.

Thanks, I've adjusted it as the following to update the hash values, so the index lines up after a removal.

	public void remove(final int key) {
		for (int i = key+1; i < valueKey.size(); i++) {
			valueKey.put(keyValue.get(i), i-1);
		}
		valueKey.remove(keyValue.get(key));
		keyValue.remove(key);
	}

	public void remove(final E value) {
		final int key = valueKey.get(value);
		remove(key);
	}

[Jeff Gent]

Just wanted to post this in case anyone else happen to use it. I made a change to the indexOf to better conform to the ArrayList return of -1 instead of a Null.

	public int indexOf(final E value) {
		Integer x = valueKey.get(value);
		if (x != null) {
			return x.intValue();
		}
		return -1;
	}