3

谈论性能和资源。

添加和编辑值时，ArrayList 和 TreeMap 哪个更快且需要的资源更少？

或者是否有任何类型的数据可以击败这两者？（它必须能够以某种方式使数据排序）

4

3 回答 3

6

ArrayLists 和 TreeMaps 是用于不同事物的不同类型的结构。了解您计划使用这些结构的目的会很有帮助。

数组列表

  • 允许重复（它是一个列表）
  • 摊销 O(1) 添加到列表末尾
  • O(n) 插入列表中的任何其他位置
  • O(1) 访问
  • O(n) 移除

树状图

  • 不允许重复键（它是一个 Map）
  • O(logn) 插入
  • O(logn) 访问
  • O(logn) 删除

对 ArrayList 进行排序将花费 O(nlogn) 时间（在插入所有内容之后），而 TreeMap 将始终被排序。

编辑

您已经提到您正在处理从数据库中检索到的记录。由于它们来自数据库，我会假设它们已经排序 - 在这种情况下，您应该将它们一一插入到 ArrayList 中。

于 2013-05-23T23:27:20.840 回答
5

取决于你需要什么。

如果我们谈论的是排序数据，因为它ArrayList是一个列表/数组，如果它是排序的，你可以得到一个O(log n)速度值。但是，要插入它是O(n)，因为您在插入新元素时可能必须移动整个数组。

TreeMap数据结构实现为红黑树，插入时间和搜索时间均为O(log n)。

所以，简而言之：

Data Structure         Insertion Speed    Search Speed
ArrayList (sorted)     O(n)               O(log n)
TreeMap                O(log n)           O(log n)

我肯定会去TreeMap。它还有一个额外的好处，那就是现在一切都准备好了（你必须自己实现一些代码才能完成ArrayList工作）。

注意：
 如果您没有得到（称为大哦）符号，请将其视为结构具有元素O(n)时所需的秒数的公式。n因此，如果您有一个ArrayList包含 1000 个元素的 ( n=1000)，则需要3几秒钟 ( log 1000 = 3) 才能在其中找到一个项目。但是插入一个新元素需要 1000 秒。

TreeMap另一方面，搜索和插入都需要3秒。

于 2013-05-23T23:25:44.213 回答
4

ArrayList 只需要 O(1) 来添加和编辑一个值，因为您只使用索引访问它。但是，在 ArrayList 中搜索一个元素是 O(n)，因为您最多必须遍历列表中的所有元素。

但是你必须知道你将实现什么数据结构。很难在 ArrayList 和 TreeMap 之间进行选择，因为它们的目的并不相同（Map 不允许重复，但 ArrayList 不允许，等等）。

这是两张表，描述了两者（以及其他类型的集合）之间的差异。

List和Map：

在此处输入图像描述

也添加Set了：

在此处输入图像描述

于 2013-05-23T23:20:42.987 回答