LinkedHashMap access by index vs Performance

Question

I would like to discuss a bit of performance of a particular collection, LinkedHashMap, for a particular requirement and how Java 8 or 9 new features could help on that.

Let's suppose I have the following LinkedHashMap:

private Map<Product, Item> items = new LinkedHashMap<>();

Using the default constructor means this Map follows the insertion-order when it is iterated.

--EDITED-- Just to be clear here, I understand that Maps are not the right data structure to be accessed by index, it happens that this class needs actually two remove methods, one by Product, the right way, which is the key, and the other by position, or index, which is not common so that's my concern about performance. BTW, it's not MY requirement.

I have to implement a removeItem() method by index. For those that doesn't know, a LinkedHashMap doesn't have some sort of map.get(index); method available.

So I will list a couple of solutions:

Solution 1:

public boolean removeItem(int position) {
    List<Product> orderedList = new ArrayList<>(items.keySet());
    Product key = orderedList.get(position);

    return items.remove(key) != null;
}

Solution 2:

public boolean removeItem(int position) {
    int counter = 0;
    Product key = null; //assuming there's no null keys

    for(Map.Entry<Product, Item> entry: items.entrySet() ){
        if( counter == position ){
            key = entry.getKey();
            break;
        }
        counter++;
    }

    return items.remove(key) != null;
}

Considerations about these 2 solutions.

S1: I understand that ArrayLists have fast iteration and access, so I believe the problem here is that a whole new collection is being created, so the memory would be compromised if I had a huge collection.

S2: I understand that LinkedHashMap iteration is faster than a HashMap but not as fast as an ArrayList, so I believe the time of iteration here would be compromised if we had a huge collection, but not the memory.

Considering all of that, and that my considerations are correct, can I say that both solutions have O(n) complexity?

Is there a better solution for this case in terms of performance, using the latest features of Java 8 or 9?

Cheers!

Answer 1

As said by Stephen C, the time complexity is the same, as in either case, you have a linear iteration, but the efficiency still differs, as the second variant will only iterate to the specified element, instead of creating a complete copy.

You could optimize this even further, by not performing an additional lookup after finding the entry. To use the pointer to the actual location within the Map, you have to make the use of its Iterator explicit:

public boolean removeItem(int position) {
    if(position >= items.size()) return false;
    Iterator<?> it=items.values().iterator();
    for(int counter = 0; counter < position; counter++) it.next();
    boolean result = it.next() != null;
    it.remove();
    return result;
}

This follows the logic of your original code to return false if the key was mapped to null. If you never have null values in the map, you could simplify the logic:

public boolean removeItem(int position) {
    if(position >= items.size()) return false;
    Iterator<?> it=items.entrySet().iterator();
    for(int counter = 0; counter <= position; counter++) it.next();
    it.remove();
    return true;
}

You may retrieve a particular element using the Stream API, but the subsequent remove operation requires a lookup which makes it less efficient as calling remove on an iterator which already has a reference to the position in the map for most implementations.

public boolean removeItem(int position) {

    if(position >= items.size() || position < 0)
        return false;

    Product key = items.keySet().stream()
        .skip(position)
        .findFirst()
        .get();

    items.remove(key);
    return true;
}

Answer 2

Considering all of that, and that my considerations are correct, can I say that both solutions have O(n) complexity?

Yes. The average complexity is the same.m In the first solution the new ArrayList<>(entrySet) step is O(N).

In the second solution the loop is O(N).

There is difference in the best case complexity though. In the first solution you always copy the entire list. In the second solution, you only iterate as far as you need to. So the best case is that it can stop iterating at the first element.

But while the average complexity is O(N) in both cases, my gut feeling is that the second solution will be fastest. (If it matters to you, benchmark it ...)

Is there a better solution for this case in terms of performance, using the latest features of Java 8 or 9?

Java 8 and Java 9 don't offer any performance improvements.

If you want better that O(N) average complexity, you will need a different data structure.

The other thing to note is that indexing the Map's entry sets is generally not a useful thing to do. Whenever an entry is removed from the set, the index values for some of the other entries change ....

Mimicking this "unstable" indexing behavior efficiently is difficult. If you want stable behavior, then you can augment your primary HashMap<K,V> / LinkedHashMap<K,V> with a HashMap<Integer,K> which you use for positional lookup / insertion / retrieval. But even that is a bit awkward ... considering what happens if you need to insert a new entry between entries at positions i and i + 1.