Fastest and minimal random access data structure in Java

I have written up a data structure in Java that supports the following features:

• get(i)

• set(i, e)

• add(e)

• remove(e)

• contains(e)

• size

Elements must remain in order and iteration needs to be as fast as possible. The code does not require thread safety.

I am looking for ways to improve the speed further. It is critical to reduce times to as small as possible because this code will be invoked hundreds of thousands of times per second. I believe it's possible to optimize my stream() method!

This is my current solution which seems to work:

import java.util.Iterator;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

public final class Indexer implements Iterable {

    private final int minIndex;
    private final Object[] arr;

    private int size = 0;
    private int highest;

    public Indexer(int minIndex, int capacity) {
        this.minIndex = highest = minIndex;
        arr = new Object[capacity];
    }

    public Indexer(int capacity) {
        this(0, capacity);
    }

    @SuppressWarnings("unchecked")
    public E get(int index) {
        return (E) arr[index];
    }

    @SuppressWarnings("unchecked")
    public E set(int index, E element) {
        Object last = arr[index];
        arr[index] = element;
        if (last == null && element != null) {
            size++;
            if (highest  iterator() {
        return new Iterator() {

            private int pointer = minIndex;

            @Override
            public boolean hasNext() {
                return size > 0 && pointer  stream() {
        return StreamSupport.stream(spliterator(), false);
    }

}

Wow, this is pretty nice code. I've only got a few little nitpicks.

NB: I have not benchmarked the code before and after making these changes. If you'd like, I can, but as of right now, these are untested changes.

NB2: Most of these are just conforming to convention, since after a bit of research I've discovered that the JIT makes things scary fast after a few thousand iterations by putting in every optimization I'd never think of.

-
In remove(E) and contains(E), you compare equality with == instead of equals. This is a bad idea, because sometimes people want to specify their way of comparing objects. If they don't, this will default to Object's implementation, which is just ==. The exception, of course, is when you're dealing with either primitives or null, but you don't have to worry about that, since you can't use primitive types as E, and their class equivalents all define equals appropriately.

-
It's standard for remove to return the element it just removed, so you'll want to change the internals of the for a little bit:

if (element.equals(arr[i])) {
    set(i, null);
    return element;
}

and change the method signature to match.

-
I'd recommend adding a remove(int) as well, which does basically the same thing as remove(E) but doesn't have to loop through. It would look something like this:

public E remove(int index) {
    E ret = get(index);
    set(index, null);
    return ret;
}

-
Continuing with the trend of "I think your methods are bad and here's how I think you should do them instead", I think your lack of indexOf is bad and here's how I think you could implement it:

public int indexOf(E element) {
    for (int i = minIndex; i < size; i++) {
        if (element.equals(arr[i]))
            return i;
    }
    return -1;
}

-
In set(int, E) I'd recommend renaming last to original, or it might be confused with the last element of the array.

-
In iterator()'s anonymous class's next(), you should add a check to make sure that you're not overstepping the array's bounds, even if all you end up doing is throwing a different error. corsiKa suggested using an IllegalStateException, which makes a good bit of sense. The most important thing is that, from the name of the exception alone, you can figure out roughly what went wrong, though not necessarily the details.

That's about it! Well-written code all. If you give me some test cases, I can benchmark the version with my tips and the version without.

StackExchange Code Review Q#95113, answer score: 10