5

您能否让我知道性能方面为什么Array比Collection更好？

4

5 回答 5

7

它不是。这实际上取决于您对容器的使用。

某些算法可能在数组上以 O(n) 运行，在另一个集合类型（实现 Collection 接口）上以 O(1) 运行。

  • 例如，考虑移除一个项目。在这种情况下，即使是本机类型，数组的执行速度也会比链表及其方法调用慢（在某些 VM 上无论如何都可以内联）：它在 O(n) VS O(1) 中运行列表
  • 考虑搜索一个元素。对于数组，它在 0(n) 中运行，而对于树，它在 0(n) 中运行。

一些 Collection 实现使用数组来存储它们的元素（我认为是 ArrayList），因此在这种情况下性能不会有显着差异。

您应该花时间优化您的算法（并利用各种可用的集合类型），而不是担心数组 VS 集合的优缺点。

于 2012-12-17T08:15:42.393 回答
3

许多集合是数组的包装器。这包括 ArrayList、HashMap/Set、StringBuilder。对于优化的代码，操作的性能差异很小，除非您遇到更适合该数据结构的操作，例如查找 Map 比查找数组快得多。

对基本上是原语的集合使用泛型可能会更慢，不是因为集合更慢，而是额外的对象创建和缓存使用（因为所需的内存可能更高）这种差异通常太小而无所谓，但如果你担心这个您可以使用 Trove4J 库，它们是基元数组而不是对象数组的包装器。

集合速度较慢的地方是当您使用它们不适合的操作时，例如随机访问 LinkedList，但明智的编码可以避免这些情况。

于 2012-12-17T08:28:37.880 回答
1

基本上，因为数组是 Java 中的原始数据结构。对它们的访问可以直接转换为本地内存访问指令，而不是方法调用。

尽管如此，数组在所有情况下都会严格胜过集合并不是很明显。如果您的代码引用了集合变量，其中运行时类型可以在 JIT 时单态地知道，Hotspot 将能够内联访问方法，并且在它们很简单的地方，可以同样快，因为无论如何基本上没有开销。

然而，许多集合的访问方法本质上比数组引用更复杂。例如，HashMap无论 Hotspot 对它进行了多少优化，a 都不会像简单的数组查找那样高效。

于 2012-12-17T08:19:51.327 回答
0

你无法将两者进行比较。ArrayList 是一个实现，Collection 是一个接口。Collection 接口可能有不同的实现。

在实践中，选择实现作为对数据的简单访问。如果您需要遍历所有元素，通常使用 ArrayList。哈希表，如果您需要按键访问。

只有在进行测量后才应考虑性能。然后很容易更改实现，因为集合框架具有像 Collection 接口这样的通用接口。

于 2012-12-17T08:25:45.043 回答
0

问题是使用哪一个以及何时使用？

数组基本上是固定大小的元素集合。数组的缺点是它不可调整大小。但是如果你清楚你的元素大小，它的恒定大小会提供效率。因此，当您知道可用的元素数量时，最好使用数组。

收藏

ArrayList是另一个可调整元素数量的集合。因此，如果您不确定集合中的元素数量，请使用 ArrayList。但是在使用 ArrayList 时需要考虑一些事实。

  • ArrayLists 不同步。因此，如果有多个线程访问和修改列表，则可能需要在外部处理同步。

  • ArrayList 在内部实现为数组。因此，每当添加一个新元素时，就会创建一个由 n+1 个元素组成的数组，然后将所有 n 个元素从旧数组复制到新数组，然后将新元素插入到新数组中。

  • 添加 n 个元素需要时间。

  • isEmpty、size、iterator、set、get 和 listIterator 操作
    需要相同的时间，与您访问的元素无关。

  • 只有对象可以添加到 ArrayList

  • 允许空元素

如果需要向 ArrayList 添加大量元素，可以使用 ensureCapacity(int minCapacity) 操作来确保 ArrayList 具有所需的容量。这将确保在添加所有元素时仅复制一次 Array，并提高将元素添加到 ArrayList 的性能。此外，在 1000 个元素的中间插入一个元素需要您向上或向下移动 500 个元素，然后在中间添加元素。

使用 ArrayList 的好处是访问随机元素很便宜，并且不受 ArrayList 中元素数量的影响。但是在尾巴的头部或中间添加元素是昂贵的。

Vector与 ArrayList 类似，不同之处在于它是同步的。它提供了一些其他好处，例如它具有初始容量和增量容量。因此，如果您的向量的容量为 10，增量容量为 10，那么当您添加第 11 个元素时，将创建一个包含 20 个元素的新向量，并将这 11 个元素复制到新向量中。因此，添加第 12 到第 20 个元素不需要创建新向量。

默认情况下，当向量需要增加其内部数据结构的大小以容纳更多元素时，内部数据结构的大小会增加一倍，而对于 ArrayList，大小只会增加 50%。所以ArrayList在空间上比较保守。

LinkedList更加灵活，允许您从集合的两侧插入、添加和删除元素 - 它可以用作队列甚至双端队列！LinkedList 在内部不使用数组。LinkedList 是一个节点序列，它们是双链接的。每个节点都包含标题，实际存储对象的位置，以及指向下一个或前一个节点的两个链接或指针。LinkedList 看起来像一条链条，由手拉手的人组成。您可以将人员或节点插入该链或删除。链接列表允许在恒定时间内在列表中的任何点进行节点插入/删除操作。

所以在链表中插入元素（无论是在头部还是尾部或中间）并不昂贵。此外，当您从头部检索元素时，它很便宜。但是当你想随机访问链表的元素或访问链表尾部的元素时，操作就很繁重了。因为，要访问第 n+1 个元素，您需要解析前 n 个元素才能到达第 n+1 个元素。

链表也不同步。因此，修改和读取列表的多个线程需要在外部同步。

因此，选择使用哪个类来创建列表取决于需求。当您需要在列表末尾添加元素并随机访问元素时，可以使用 ArrayList 或 Vector（如果您需要同步） - 访问操作多于添加操作。而当您需要从列表的头部或中间进行大量添加/删除（元素）操作并且您的访问操作相对较少时，应该使用 LinkedList。

于 2012-12-17T08:26:28.257 回答