Java data structure that has efficient add, delete, and random

Question

I need a Java data structure that I can efficiently add, delete, and access a random object.

This is what doesn't work:

ArrayList has efficient add (constant time), and random access (just "get" with a random integer), but deletes can take linear time because it has to potentially search the whole list for it.

TreeSet or HashSet has efficient add and delete, but I can't figure out how to get a random object.

Any ideas?

In theory, a B Tree would work, if I could traverse the tree myself with random Lefts or Rights, but I don't think a standard Java class gives me this ability.

I'm willing to use a third party library if nothing in the standard Java classes will work.

I do not need to support duplicates or nulls, nor does it need to be thread safe.

Thanks.

Answer 1

You can get this with an ArrayList/HashMap pair (where the map will store the index of objects in the list) if you make list removal unordered. On removal, instead of shifting all subsequent elements in the list down one position, you just move the last element to fill the space of the removed item. Then there are at most two different elements that need to be touched during removal. A quick example (which I haven't tested and hope I didn't bungle):

class SpecialSet<E> extends AbstractSet<E> implements Set<E> {
    private final List<E> list = new ArrayList<>();
    private final Map<E,Integer> indexMap = new HashMap<>();

    @Override
    public boolean add(E e) {
        if (contains(e)) return false;
        indexMap.put(e, list.size());
        list.add(e);
        return true;
    }

    @Override
    public boolean remove(Object o) {
        Integer indexBoxed = indexMap.remove(o);
        if (indexBoxed == null) return false;
        int index = indexBoxed;
        int last = list.size() - 1;
        E element = list.remove(last);
        if (index != last) {
            indexMap.put(element, index);
            list.set(index, element);
        }
        return true;
    }

    public E removeRandom() {
        E element = list.get((int)(Math.random() * size()));
        remove(element);
        return element;
    }

    @Override
    public boolean contains(Object o) {
        return indexMap.containsKey(o);
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }

    @Override
    public int size() {
        return list.size();
    }
}

Depending on what object equality testing behavior you want, you maybe could swap out the HashMap for an IdentityHashMap for a little better speed.

Answer 2

I'd propose that you use a Map, with an Integer key. That way you can generate a random number for the remove.

Problem left for the reader: on subsequent removes (or any operation) there will be gaps.

Answer 3

Note that a simple array will do the job, if you pre-allocate to the max size you'll need. Keep a "top" index value and insert by incrementing "top" and storing into that array element. When you delete, copy the "top" value down into the deleted element and decrement "top".

If you don't know your max size you can still allocate an array of arrays and use the same basic algorithm, only you need to first compute the major and minor array index values before accessing an element.