Obtain Index of a Given LinkedHashSet Element Without Iteration

1. Overview

In this tutorial, we’ll learn how to address a rare case where we need to ensure element uniqueness when querying their indexes. The most reasonable idea is to use what already exists in classes, but it might not be the best option, and we’ll learn why.

Overall, the approaches presented in this article should be tailored to the specific task, taking into account their pros and cons.

2. LinkedHashSet

When we’re looking for a data structure that ensures uniqueness and maintains element order, LinkedHashSet is often the first choice. Also, we can iterate over it to find the position of a given element:

public static <E> int getIndex(LinkedHashSet<E> set, E element) {
    int index = 0;
    for (E current : set) {
        if (current.equals(element)) {
            return index;
        }
        index++;
    }
    return -1;
}

Another option is to get an iterator from LinkedHashSet, but, in general, the approach won’t change; we make the iteration process more explicit:

public static <E> int getIndexUsingIterator(LinkedHashSet<E> set, E element) {
    Iterator<E> iterator = set.iterator();
    int index = 0;
    while (iterator.hasNext()) {
        if (iterator.next().equals(element)) {
            return index;
        }
        index++;
    }
    return -1;
}

The main benefit is that it does almost everything out of the box. However, there’s a minor problem: we don’t have a way to get an element by its index in constant time. This operation would be linear, so if we do many lookups, it could dramatically affect our code’s performance. At the same time, if the size of the LinkedHashSet doesn’t grow much and lookups are rare compared to additions, this approach might be the one we should consider.

3. Conversion

As an option, we can create a special data structure for lookups, for example, by converting the LinkedHashSet to a List, or an array:

public static <E> int getIndexByConversion(Set<E> set, E element) {
    List<E> list = new ArrayList<>(set);
    return list.indexOf(element);
}

In some cases, this approach is assumed to be more performant. The confusion stems from the fact that we’re using a simple indexOf() method, which leads us to assume it somehow optimizes the process. Actually, it performs the same iteration as we did previously:

public static <E> E getElementByIndex(Set<E> set, int index) {
    List<E> list = new ArrayList<>(set);
    if (index >= 0 && index < list.size()) {
        return list.get(index);
    }
    throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + list.size());
}

Converting a LinkedHashSet to an array is possible, but requires a few additional type-casting steps:

@SuppressWarnings("unchecked")
public static <E> E[] convertToArray(Set<E> set, Class<E> clazz) {
    return set.toArray((E[]) java.lang.reflect.Array.newInstance(clazz, set.size()));
}

public static <E> int getIndexByArray(Set<E> set, E element, Class<E> clazz) {
    E[] array = convertToArray(set, clazz);
    for (int i = 0; i < array.length; i++) {
        if (array[i].equals(element)) {
            return i;
        }
    }
    return -1;
}

In general, this approach doesn’t make sense for a simple reason: the indexOf() method performs an exact linear search, as we did explicitly in the first example. Additionally, we create a new data structure, doubling the space required for this solution. However, if we want to find an element by its index, we can achieve constant-time lookups. Thus, we need to know which operations we would like to prioritize to pick an approach.

4. List and Set

We can change our perspective a bit and separate these two requirements, uniqueness and order maintenance. Thus, we can use two separate structures: List and Set. The List would maintain the order and the Set uniqueness, so every time we want to add an element, we would check it with the  set first and only after that insert it into the List:

public class ListAndSetApproach<E> {
    private final List<E> list;
    private final Set<E> set;

    public ListAndSetApproach() {
        this.list = new ArrayList<>();
        this.set = new HashSet<>();
    }

    public boolean add(E element) {
        if (set.add(element)) {
            list.add(element);
            return true;
        }
        return false;
    }

    public int indexOf(E element) {
        return list.indexOf(element);
    }

    // Other methods
}

However, we should ensure that we remove elements correctly. In the previous approach, it was done transparently. In this case, we have to move the element to keep the order manually:

public class ListAndSetApproach<E> {

    // Initialization, fields, and a constructor

    public boolean remove(E element) {
        if (set.remove(element)) {
            list.remove(element);
            return true;
        }
        return false;
    }

   // Other methods
}

Even with all these modifications and two data structures, the lookup remains linear. Thus, we have the same problem we had previously. While we can add caching, it won’t change much, since the lookup and the creation of a data structure would have the same time complexity. The only way to optimize our solution is to create a custom implementation to address all our requirements.

However, the same is true about this approach as for the previous one. The lookups by index would run in constant time, so if we want to optimize these operations, it might be a good solution:

public class ListAndSetApproach<E> {

    // Initialization, fields, and a constructor

    public E get(int index) {
        return list.get(index);
    }

   // Other methods
}

By combining two data structures, we can incorporate their features. In this case, we maintain the uniqueness with a Set, and order with a List.

5. Custom Implementation

To make the lookups constant, we can use Maps, but it would require a more complex mapping. Thus, the best approach is to encapsulate the logic into a separate class. When we connect multiple data structures by convention, for example, if we remove elements from the first one but forget to do the same for the second, we expose ourselves to many issues. Also, this approach helps us to reveal only the functionality we care about, limiting the interaction options:

public class IndexAwareSetWithTwoMaps<E> {
    private final Map<E, Integer> elementToIndex;
    private final Map<Integer, E> indexToElement;
    private int nextIndex;

    public IndexAwareSetWithTwoMaps() {
        this.elementToIndex = new HashMap<>();
        this.indexToElement = new HashMap<>();
        this.nextIndex = 0;
    }

    public boolean add(E element) {
        if (elementToIndex.containsKey(element)) {
            return false;
        }
        elementToIndex.put(element, nextIndex);
        indexToElement.put(nextIndex, element);
        nextIndex++;
        return true;
    }

    public boolean remove(E element) {
        Integer index = elementToIndex.get(element);
        if (index == null) {
            return false;
        }
        
        elementToIndex.remove(element);
        indexToElement.remove(index);
        
        for (int i = index + 1; i < nextIndex; i++) {
            E elementAtI = indexToElement.get(i);
            if (elementAtI != null) {
                indexToElement.remove(i);
                elementToIndex.put(elementAtI, i - 1);
                indexToElement.put(i - 1, elementAtI);
            }
        }
        
        nextIndex--;
        return true;
    }

    public int indexOf(E element) {
        return elementToIndex.getOrDefault(element, -1);
    }

    public E get(int index) {
        if (index < 0 || index >= nextIndex) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + nextIndex);
        }
        return indexToElement.get(index);
    }
}

This way, we can also simplify the solution by wrapping a LinkedHashSet in a custom class. Even if we’re using a single data structure, it helps us to hide caching or change the implementation in the future. For example, we can start with a simple conversion and then, as performance impacts our application, make the necessary improvements without changing the rest of the application.

6. Complexity Overview

All the listed approaches have pros and cons. To pick the best-suited one, we should know which operations would dominate, the size of the data set we expect to work with, and the rate of change in the data. We can use the following table to decide on the approach:

In most cases, the custom approach would perform best, since most operations would take constant time, except for removal.

7. Multithreading

When these data structures are accessed from multiple threads, correctness becomes just as important as time complexity. A solution that works perfectly in a single-threaded context may easily break under concurrent access if updates are not coordinated properly. If we use a single data structure, using concurrent collections can help. Java provides thread-safe implementations that protect individual operations and reduce the risk of race conditions.

Suppose we have an approach that relies on two collections working together. Even if both collections are concurrent, their operations are not synchronized. Compound actions such as checking uniqueness in one structure and then updating another must still be executed atomically to keep the data consistent.

The simplest and most reliable way to ensure this consistency is to use the synchronized keyword. By synchronizing the relevant methods or code blocks, we can guarantee that multi-step operations are performed as a single unit, preserving correctness with minimal complexity. In high-contention applications, this straightforward approach may not scale well. In such scenarios, it is worth exploring more advanced concurrency techniques and possibly rethinking the overall design to reduce shared mutable state.

8. Conclusion

In this article, we’ve discussed different ways to optimize the indexOf method. In some cases, the functionality of a single data structure isn’t enough for our goals. Thus, we would like to combine them. All approaches have pros and cons and are highly dependent on the context in which the code will run. Therefore, there’s no “best” solution. However, the most flexible approach is to wrap the code in a dedicated class. This makes it easier to change or improve the implementation when necessary.

As usual, all the code from this tutorial is available over on GitHub.