Any collection O(1) indexOf time complexity?

Question

Can anyone help me to figure out that, is there any collection type in java (or any language agonistic one) that offers O(1) time complexity for indexOf(Item item) operation? [You may assume there are no duplicates or simply the first index to be returned]

If there is nothing, can anyone help me out to deduct the reason why such has not been formed? Any particular reason?

HashMap: https://stackoverflow.com/questions/1055243/is-a-java-hashmap-search-really-o1 — tgdavies, Oct 11 '20 at 12:25
@tgdavies thanks for the link, but I'm specifically asking about a collection with that characteristic. I know, I can possibly use a map as a workaround. [not perfect though] — Supun Wijerathne, Oct 11 '20 at 12:30
Why you think _[not perfect though]_ ? Think if objects are not unique how you will find the index ? — Eklavya, Oct 11 '20 at 12:31
@Eklavya I was searching for a collection like data structure. In my specific case elements are unique (non-duplicate) — Supun Wijerathne, Oct 11 '20 at 15:08
The only way I can think to do this is if the list index can be derived from properties of the element. For example, you can find `list.indexOf(3)` if `list` is `[0,1,2,3,4,5]`. But in general, you can't, because you need to search through the list. — Andy Turner, Oct 13 '20 at 13:54

Stephen C · Accepted Answer · 2022-01-13T05:19:51.040

There is no Java (standard) collection type with that property.

The indexOf(Object) method is declared in List, and there are no List implementations that provide better than O(N) lookup.

There are other collection types that provide O(logN) or O(1) lookup, but they do not return a position (and index) like indexOf(Object) does. (HashMap and HashSet provide respectively get(key) and contains(object) that are O(1).)

If there is nothing, can anyone help me out to deduce the reason why such has not been formed? Any particular reason?

Because a data structure that did provide such functionality would be complicated, and (probably) slower and/or combine the drawbacks of both an ArrayList and a HashMap.

^{I can't think of a good way to implement a list with fast lookup; i.e. one that didn't have serious drawbacks. And if there was a good way, I would have expected the Java team to know about it ... and to have included it in the Java SE library. This is similar to why there are no general purpose concurrent list types.}

^{I am not saying that it is impossible. I'm saying that if it is possible, nobody has discovered a way to do it. AFAIK.}

Designing an general purpose collection type involves compromise. When you optimize for one mode of access, you will often de-optimize for another.

Thiyagu · Answer 2 · 2020-10-11T12:35:20.250

To find the index of an element in a Collection in O(1) you need to be able to directly retrieve the index of the element without searching. A List or an array doesn't allow us to do this (requires O(N)) and a Set is not ordered ¹.

We are left with a Map but a Map is a key-value pair.

You can create a map with key as the element and value as the index as an auxiliary data structure to your collection. The downside is you need to update the map when you update your collection (List/Array)

or just use the map and get rid of your collection.

¹ indexOf method is on a List and not on Collection.

score 0 · Answer 3 · answered Oct 11 '20 at 12:58

A Map would seem to be the simplest solution, but just for fun: (implementing the rest of List is left as an exercise for the reader)

package org.example;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class HashList<E> {
    private final List<E> list = new ArrayList<>();
    private final Map<E,Set<Long>> indexes = new HashMap<>();

    public long indexOf(E item) {
        Set<Long> indexSet = indexes.get(item);
        if (indexSet == null || indexSet.isEmpty()) {
            return -1;
        } else {
            return indexSet.iterator().next();
        }
    }

    public void add(E item) {
        list.add(item);
        long index = list.size() - 1;
        Set<Long> indexSet = indexes.get(item);
        if (indexSet == null) {
            indexSet = new TreeSet<>();
            indexes.put(item, indexSet);
        }
        indexSet.add(index);
    }

    public static void main(String... args) {
        HashList<String> list = new HashList<>();

        assertTrue(list.indexOf("foo") == -1);
        list.add("foo");
        assertTrue(list.indexOf("foo") == 0);
        list.add("bar");
        assertTrue(list.indexOf("bar") == 1);
        list.add("foo");
        // still 0 for the first occurrence
        assertTrue(list.indexOf("foo") == 0);
    }

    private static void assertTrue(boolean truth) {
        if (!truth) {
            throw new RuntimeException();
        }
    }
}

Quite expensive. And why are you using `Long` when the index can never exceed the `int` value range? — Holger, Oct 14 '20 at 11:25

Any collection O(1) indexOf time complexity?

3 Answers3