Any collection O(1) indexOf time complexity?

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?

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.

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.

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();
}
}
}