任何集合 O(1) indexOf 时间复杂度？

Question

谁能帮我弄清楚，java 中是否有任何集合类型（或任何语言竞争性集合类型）为 indexOf(Item item) 操作提供 O(1) 时间复杂度？ [您可以假设没有重复项或只是要返回的第一个索引]

如果没有，谁能帮我推导出没有形成的原因？有什么特别的原因吗？

Answer 1

属性没有 Java（标准）集合类型。

indexOf(Object) 方法在 List 中声明，并且没有 List 实现提供比 O(N) 更好的查找。

还有其他集合类型提供 O(logN) 或 O(1) 查找，但它们不像 indexOf(Object) 那样 return 位置（和索引）。（HashMap和HashSet分别提供get(key)和contains(object)即O(1)。）

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

因为确实提供这种功能的数据结构会很复杂，而且（可能）较慢 and/or 结合了 ArrayList 和 ArrayList 的缺点HashMap.

^{我想不出好的方法来实现具有快速查找功能的列表；即没有严重缺点的。如果有好的方法，我希望 Java 团队知道它……并将其包含在 Java SE 库中。这类似于为什么没有通用 concurrent 列表类型。}

^{我不是说不可能。我是说，如果可能的话，没有人找到一种方法来做到这一点。据我所知。}

设计通用集合类型涉及妥协。当您针对一种访问模式进行优化时，您通常会 de-optimize 另一种。

Answer 2

要在 O(1) 中的 Collection 中查找元素的索引，您需要能够直接检索元素的索引而无需搜索. List 或 array 不允许我们这样做（需要 O(N)）并且 Set 未排序 ¹ .

我们剩下 Map，但地图是 key-value 对。

您可以创建一个以键为元素，以值为索引的映射，作为您的collection的辅助数据结构。缺点是您需要在更新 collection (List/Array)

时更新地图

或者只使用地图并摆脱你的 collection。

¹ indexOf 方法在 List 而不是 Collection.

Answer 3

Map 似乎是最简单的解决方案，但只是为了好玩：（实现 List 的其余部分留作 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();
        }
    }
}

任何集合 O(1) indexOf 时间复杂度？

Any collection O(1) indexOf time complexity?

java

collections

big-o

indexof