java - 在 List 和 HashMap 之间使用 retainAll() 函数的时间复杂度是多少？

Question

假设我有一个嵌套列表，其中包含 n^2 元素，并且我有一个 HashMap，其中包含 n^2 键。我想使用 retainAll() 获得列表和哈希图之间的共同元素功能。在这种情况下，retainAll() 的时间复杂度是多少？

List<List<Integer> list = new ArrayList<>();
Map<List<Integer>, Integer> hashmap = new HashMap<List<Integer>, Integer>();
list.retainAll(hashmap);

为了获得共同点，我正在使用这个循环，但它有 n^2 的复杂性。

List<List<Integer>> commons = new ArrayList<>();

    for (int i = 0; i < list.size(); i++) {
        if (hashmap.get(list.get(i)) != null) {
            commons.add(list.get(i));
        }
    }

此外，如果您有一个具有更好时间复杂度的算法来获得它们的交集，我需要它。
编辑:
实际上问题是，我有一个大小为 n 的整数列表。但我将该列表划分为子列表，子列表计数变为 n^2。因为我想找出 hashmap 包含每个子列表作为其中的键，所以我使用了 n^2 。但根据我的整个项目，它太大了。我正在寻找降低复杂性的方法。

Answer 1

好吧，我的意思是如果你有 n^2列表中的项目，则复杂度为 O(n^2) ，虽然这是一件很奇怪的事情。通常 n是集合的大小，所以 retainAll 的时间复杂度考虑O(n) .
据我所知，不可能有一种算法为此产生更好的时间复杂度。您必须至少迭代一次列表...
你可以做的是切换你的数据结构。阅读更多:Data structures for fast intersection operations?