33

我正在编写一个算法，在其中寻找成对的值，当它们相加时会产生我正在寻找的另一个值。

我发现使用 aMap可以从 O(n²) 加速我的算法。后来我意识到我并没有真正使用我的值中包含的值，Map所以一个List就足够了。

我在 Google 上进行了强力搜索，但在我的问题标题中没有找到有关这些方法的渐近运行时间的任何信息。

你能指出我应该在哪里寻找这些信息吗？

4

4 回答 4

58

后来我意识到我并没有真正使用我的值中包含的值，Map所以一个List就足够了。

Map不仅仅是键值对的列表，它是从键到值的唯一映射。因此，当您从 更改为Map时List，您将允许以前不允许的重复项。另一方面， aSet完全是 aMap没有值。所以考虑使用HashSet.

至于搜索的复杂性：

list.contains是 O(n)，hashSet.contains是 O(1)，treeSet.contains是 O(log n)。

有关 now HashMapworks 的一般信息，请在谷歌搜索“哈希表”。对于TreeMap，谷歌“二叉树”或类似的。维基百科在这些主题上有很好的条目。

但是，要小心避免上课Hashtable。它是现代图书馆中的一件考古文物。对于您的情况HashSet可能是最好的选择。

于 2012-07-23T13:23:52.323 回答
6

Map并且List是接口，因此没有关于它们的实现和性能的信息。但是，如果您使用最新的实现（LinkedList或ArrayListforList和HashMapfor Map），contains()在最坏的情况下，该方法必须遍历整个列表，并将您的元素与每个条目进行比较。这是一个 O(n) 操作。

如果使用 an HashMap，则实现完全不同：HashMap包含一个数组，其中的条目比其中的元素多（实际上，对于映射中的 n 个元素，数组大小在 4n/3 到 3n/2 之间）。它计算密钥的哈希值，它是一个 int，并将其包装在 0 和您的数组大小之间（假设这个数字是i）。然后它将元素放在i数组的索引处（或者i+1，i+2......如果先前的索引已经被占用）。因此，当您使用 来检查键是否存在时containsKey，它将重新计算散列和i值，并检查i, i+1... 索引，直到找到一个空数组单元格。理论上，你可以有一个 O(n) 最坏的情况，如果数组几乎满了，所有的键都几乎相同i值，但具有良好的散列函数，你有常数时间contains和get函数。（但是，如果您不需要调整数组的大小，那么添加元素会很快，这真的很慢 - 我认为您需要重新计算每个键的索引）。

因此，如果您需要检查集合中的键外观，并且不需要保持顺序（有一个SortedHashMap用于那个，但我不知道它的性能），那么映射确实更快，但它会占用更多内存。

此外，如果您不需要键值，您可以使用 a HashSet（在内部与 a 相同HashMap）。

于 2012-07-23T13:40:55.677 回答
1

HashSet 似乎更快：

  • 哈希图：267
  • 数组列表：2183
  • 哈希集：57

另请注意， .contains() 通常不需要在 HashMap 和 HashSet 上调用，但我将其保留在代码中以更准确地回答您的问题：

    long t = System.currentTimeMillis();
    HashMap<String, Boolean> map = new HashMap<>();
    for (int i = 0; i < 10000; i++) {
        String s = (Math.random() * 100) + "";
        if (!map.containsKey(s)) {
            map.put(s, true);
        }
    }
    System.out.println("HashMap: " + (System.currentTimeMillis() - t));

    t = System.currentTimeMillis();
    ArrayList<String> list = new ArrayList<>();
    for (int i = 0; i < 10000; i++) {
        String s = (Math.random() * 100) + "";
        if (!list.contains(s)) {
            list.add(s);
        }
    }
    System.out.println("ArrayList: " + (System.currentTimeMillis() - t));

    t = System.currentTimeMillis();
    HashSet<String> set = new HashSet<>();
    for (int i = 0; i < 10000; i++) {
        String s = (Math.random() * 100) + "";
        if (!set.contains(s)) {
            set.add(s);
        }
    }
    System.out.println("HashSet: " + (System.currentTimeMillis() - t));
于 2020-11-21T16:49:10.390 回答
0

Map.containsKey() 考虑到您使用的是 HashMap，因为在 HashMap 中的搜索是在 O(1) 中完成的。

List.contains() 通常应该采用顺序搜索或二分搜索，因此复杂度至少为 O(log n)

于 2012-07-23T13:25:10.873 回答