java - 映射/数组列表 : which one is faster to search for an element

Question

我有一个巨大的数据集，我必须将其存储到一个集合中，并且需要查找其中是否有任何重复项。

数据量可能超过 100 万。我知道我可以将 ArrayList 中的更多元素存储到 Map 中。

我的问题是:

1. 在 Map 中搜索键是否比在排序的 ArrayList 中搜索更快？
2. 在 HashMap 中搜索 Key 是否比 TreeMap 快？
3. 仅就存储 n 元素所需的空间而言，在 TreeMap 和 HashMap 实现之间哪个更有效？<

Answer 1

1) 是的。搜索 ArrayList平均为 O(n)。 Map 中键查找的性能取决于具体的实现。你可以写一个 Map 的实现那是 O(n) 或者更糟，但标准库中的所有实现都比 O(n) 快。

2) 是的。 HashMap简单键查找的平均复杂度为 O(1)。 TreeMap是 O(log(n))。

Class HashMap<K,V>

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

Class TreeMap<K,V>

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

3) 在这两种情况下，空间要求都是 O(n)。我会猜 TreeMap需要稍微多一点的空间，但只是一个常数。