哪一个更快？List.contains（） 或 Map.containsKey（）

后来我意识到，我并没有真正使用我的遗嘱中包含的值就足够了。MapList

Map它不仅仅是键值对的列表，它是从键到值的唯一映射。因此，当您从 更改为 时，您将允许以前没有的重复项。另一方面，a 恰好是没有值的 a。因此，请考虑使用 .MapListSetMapHashSet

至于搜索的复杂性：

list.contains是 O（n），是 O（1），并且是 O（log n）。hashSet.containstreeSet.contains

有关现在工作的一般信息，谷歌为“hashtable”。对于 ，谷歌为“二叉树”或类似。维基百科在这些主题上有很好的条目。HashMapTreeMap

但是，请注意避免类 。这是现代图书馆中的考古文物。对于您的情况可能是最好的选择。HashtableHashSet

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

如果使用 ，则实现是完全不同的：包含一个数组，其中包含的条目数多于其中的元素（实际上，对于映射中的 n 个元素，数组大小介于 4n/3 和 3n/2 之间）。它计算密钥的哈希值，这是一个int，并将其包装在0和数组大小之间（假设这个数字是）。然后，它将元素放在数组的索引处（或 ， ...如果之前的索引已被获取）。因此，当您使用 检查密钥存在时，它将重新计算哈希值和值，并检查 ， ...索引，直到找到一个空数组单元格。从理论上讲，你可以有一个O（n）最坏的情况，如果数组几乎满了，所有的键都有几乎相同的值，但是有了一个好的哈希函数，你就有了常量时间和函数。（但是，如果您不需要调整数组的大小，则添加元素的速度很快，这真的很慢 - 我认为您需要重新计算每个键的索引）。HashMapHashMapiii+1i+2containsKeyiii+1icontainsget

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

另外，如果你不需要键值的东西，你可以使用一个（它在内部与一个相同）。HashSetHashMap