0

我有一个 Web 应用程序，它ArrayList's广泛用于存储和操作其自身的数据。然而，最近我明白这HashMap's可能是一个更好的选择。谁能告诉我在Big O(n)两者中添加、访问和删除元素的算法成本（）究竟是什么，以及为了效率而进入代码并更改它们是否明智？

4

3 回答 3

8

对于数组列表：

size、isEmpty、get、set、iterator 和 listIterator 操作在恒定时间内运行。添加操作在摊销常数时间内运行，即添加 n 个元素需要 O(n) 时间。所有其他操作都以线性时间运行（粗略地说）。与 LinkedList 实现相比，常数因子较低。

从文档： http ://docs.oracle.com/javase/6/docs/api/java/util/ArrayList.html

对于哈希映射：

此实现为基本操作（get 和 put）提供恒定时间性能，假设哈希函数将元素正确地分散在桶中。集合视图的迭代需要的时间与 HashMap 实例的“容量”（桶的数量）加上它的大小（键值映射的数量）成正比。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低），这一点非常重要。

从文档： http ://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html

于 2012-07-02T10:57:58.187 回答
1

请查看http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2.pdf

  • O(1) 获取/添加
  • O(n) 包含
  • O(1) 下一个
于 2012-07-02T17:00:00.333 回答
1

ArrayList的文档对这些操作的性能进行了讨论。至于HashMap，这将是O(1)所有三个。但是，这确实假设您的hashCode方法实现良好，并且也是O(1).

于 2012-07-02T10:58:50.887 回答