Fastest and minimal random access data structure in Java

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.

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

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

3. 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;
   }
   

4. 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;
   }
   

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

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

I'm not sure about the use of minIndex. Let's say I create an instance new Indexer<E>(5,20); it implies that the indexes 0,1,2,3,4 will never be used? Therefore it seems like a useless use of memory, though I might misunderstand what you're achieving with this. If it is the case, consider that your code might use comments in order to explain why you use the minIndex!

There's a bug with the minIndex too. You check for this index when you add and remove from your data structure but not when you set. Meaning that if I wanted, I could do this :

Indexer<Integer> indexer = new Indexer<>(2,5);
indexer.set(0,2);
//My value wasn't removed because it's index is before the minIndex
indexer.remove(2);

In the set method, the variable name last is confusing, I thought it implied the last value of your Object[]. I think naming it previous might be better. Also, it is confusing as why your set returns the previous value. You should comment your methods to explain what they do and what they return. Because in this case I might think it would return the new value. The same problem applies to your add method, it isn't intuitive to understand that the int returned is the new index. Comments should make this a lot clearer :)

You should use equals over == in your comparisons. == compared the reference value whereas equals will compare using the equals override of the type you are using, which leads to less errors.

What happens if I have multiple times the same element. Is it intended that you remove only the first instance that is found?

Speed concerns

Many of your operations are \$O(n)\$ and could be made faster. You didn't say which operations were the most commonly used operations, so I'm not sure if you care about the following.

add(), nextIndex()

These are both \$O(n)\$ operations, because they both need to search the array for a free slot. If you kept a set or list of free slots, this could be faster. To retain the behavior that the lowest numbered free slot is used next, you need to use an ordered set/list. So for example, if you used a TreeSet to track your free slots, you could have \$O(\log n)\$ adds.

remove(), contains()

These are both currently \$O(n)\$, because you search the array for the element. You could make these \$O(1)\$ by keeping a HashMap of elements mapped to indices, for elements added to the array.

MinIndex and capacity

I don't like the way that minIndex and capacity are used. If I create an Indexer with minIndex=100 and capacity=100, I would expect that I could use indices [100..199]. But in the current implementation, I get a useless Indexer with no usable slots. Right now, capacity acts more like a maxIndex so it is somewhat misnamed. Another thing is that if minIndex is not 0, you are currently allocating an array where some of the slots will never be used.

If the minIndex concept is to be kept, I would suggest that the Indexer support indices in the range [minIndex .. minIndex+capacity-1]. You should then allocate an array of size capacity, and then subtract minIndex from your index whenever you access the array.

Then again, if minIndex is only ever going to be 1, it would be faster to just keep your code as is. But you should probably allocate an array of size minIndex+capacity instead of just capacity, or else document what capacity actually means.