在Java中添加,访问或从ArrayList中删除元素的算法成本是多少？

Question

我有一个Web应用程序,它ArrayList's广泛用于存储和操作自身内部的数据.然而,最近我明白这HashMap's可能是一个更好的选择.任何人都可以告诉我Big O(n)从两者中添加,访问和删除元素的算法成本()到底是什么以及为了提高效率而进入代码并更改它们是否明智？

Answer 1

对于ArrayList:

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

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

对于HashMap:

假设散列函数在桶之间正确地分散元素,该实现为基本操作(get和put)提供了恒定时间性能.对集合视图的迭代需要与HashMap实例的"容量"(桶的数量)加上其大小(键 - 值映射的数量)成比例的时间.因此,如果迭代性能很重要,则不要将初始容量设置得太高(或负载因子太低)非常重要.

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