哪个更快？List.contains()还是Map.containsKey()？

Question

我正在编写一个算法，其中我要查找两个值的组合，使它们相加后得到我想要的另一个值。

我发现使用Map将会加快我的算法速度，从O(n²)降为更低。但后来我意识到实际上并不需要使用Map中的值，因此只需使用List。

我在谷歌上进行了强力搜索，但是没有找到有关本题目方法的渐进运行时间的任何信息。

请问您能指出我应该在哪里寻找这样的信息吗？

- Adam Arold

---

一个更公平的比较应该是 Set.contains() 和 Map.containsKey()，它们基本上是相等的——对于每种类型的 Map，在其实现中都有相应的 Set 类型。 - Bohemian

我知道，但我认为对JCF代码进行渐近分析需要几个小时的项目。 - Adam Arold

听起来你想把这些数值放入一个列表中，不规则地从两端开始迭代以尝试匹配总和。 仍然是O（n）时间复杂度。对于更复杂的匹配，Bloom过滤器可能更合适。 - Tom Hawtin - tackline

Answer 1

我后来意识到我并没有真正使用我的Map中的值，所以用List就足够了。 Map不仅仅是一组键-值对的列表，它是从键到值的唯一映射。因此，当您从Map更改为List时，您允许重复项，而之前则不行。另一方面，Set恰好是一个没有值的Map, 因此请考虑使用HashSet。

至于搜索复杂度： list.contains是O（n），hashSet.contains是O（1），treeSet.contains是O（log n）。

关于HashMap如何工作的一般信息，请搜索“哈希表”。对于TreeMap，请搜索“二叉树”或类似的内容。维基百科有良好的条目介绍这些主题。

然而，请注意避免使用类Hashtable。在现代库中，它是一个考古学文物。对于您的情况，HashSet可能是最好的选择。

- Marko Topolnik

Answer 2

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

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

因此，如果您需要检查集合中是否存在键，并且不需要保持顺序（有一个SortedHashMap用于此，但我不知道它的性能），则映射速度更快，但会占用更多内存。

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

- Ilod

---

那是因为我想知道所有实现的速度。 - Adam Arold

Answer 3

HashSet似乎更快：

• HashMap：267
• ArrayList：2183
• HashSet：57

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

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

- aurhe

Answer 4

如果你使用的是HashMap，那么Map.containsKey()的搜索复杂度为O(1)。

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

- Varun