我必须在内存中保留数千个字符串,以便在Java中串行访问。我应该把它们存储在数组中还是应该使用某种列表?
由于数组将所有数据保存在一个连续的内存块中(与list不同),使用数组存储数千个字符串会导致问题吗?
我必须在内存中保留数千个字符串,以便在Java中串行访问。我应该把它们存储在数组中还是应该使用某种列表?
由于数组将所有数据保存在一个连续的内存块中(与list不同),使用数组存储数千个字符串会导致问题吗?
当前回答
我猜最初的海报来自c++ /STL背景,这引起了一些混乱。在c++中std::list是一个双链表。
在Java中[Java .util]。List是一个不需要实现的接口(c++术语中的纯抽象类)。List可以是一个双重链表——提供了java.util.LinkedList。然而,100次中有99次,当你想要创建一个新的List时,你想要使用java.util.ArrayList来代替,这是c++ std::vector的大致等价。还有其他标准实现,比如java.util.Collections.emptyList()和java.util.Arrays.asList()返回的那些。
从性能的角度来看,不得不通过一个接口和一个额外的对象会有很小的影响,但是运行时内联意味着这很少有任何意义。还要记住String通常是一个对象加数组。所以对于每个元素,你可能有两个其他的对象。在c++ std::vector<std::string>中,虽然按值复制而不使用指针,但字符数组将形成一个string对象(通常不会共享这些对象)。
如果这段代码对性能非常敏感,那么可以为所有字符串的所有字符创建一个char[]数组(甚至byte[]),然后创建一个偏移量数组。IIRC,这是javac的实现方式。
其他回答
不,因为从技术上讲,数组只存储对字符串的引用。字符串本身被分配到不同的位置。对于上千个项目,我会说列表会更好,它更慢,但它提供了更多的灵活性,更容易使用,特别是如果你要调整它们的大小。
这取决于你如何访问它。
存储后,如果你主要想做搜索操作,很少或不需要插入/删除,那么就去数组(因为在数组中搜索是在O(1)中完成的,而添加/删除可能需要重新排序元素)。
存储之后,如果你的主要目的是添加/删除字符串,很少或没有搜索操作,那么就去List。
既然这里已经有了很多好的答案,我想给你一些其他的实际观点的信息,这是插入和迭代性能的比较:Java中的基元数组与链表。
这是实际的简单性能检查。因此,结果将取决于机器的性能。
用于此的源代码如下:
import java.util.Iterator;
import java.util.LinkedList;
public class Array_vs_LinkedList {
private final static int MAX_SIZE = 40000000;
public static void main(String[] args) {
LinkedList lList = new LinkedList();
/* insertion performance check */
long startTime = System.currentTimeMillis();
for (int i=0; i<MAX_SIZE; i++) {
lList.add(i);
}
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
int[] arr = new int[MAX_SIZE];
startTime = System.currentTimeMillis();
for(int i=0; i<MAX_SIZE; i++){
arr[i] = i;
}
stopTime = System.currentTimeMillis();
elapsedTime = stopTime - startTime;
System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
/* iteration performance check */
startTime = System.currentTimeMillis();
Iterator itr = lList.iterator();
while(itr.hasNext()) {
itr.next();
// System.out.println("Linked list running : " + itr.next());
}
stopTime = System.currentTimeMillis();
elapsedTime = stopTime - startTime;
System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
startTime = System.currentTimeMillis();
int t = 0;
for (int i=0; i < MAX_SIZE; i++) {
t = arr[i];
// System.out.println("array running : " + i);
}
stopTime = System.currentTimeMillis();
elapsedTime = stopTime - startTime;
System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
}
}
表现结果如下:
数组列表在内部使用数组对象来添加(或存储)对象 元素。换句话说,ArrayList由Array数据支持 结构。ArrayList的数组是可调整大小的(或动态的)。
Array比ArrayList快,因为ArrayList内部使用数组。如果我们可以直接在数组中添加元素,而间接地在数组中添加元素 数组通过数组列表总是直接机制比间接机制快。
在ArrayList类中有两个重载的add()方法:
add(Object):将一个对象添加到列表末尾。 add(int index, Object):将指定对象插入到列表的指定位置。
数组列表的大小如何动态增长?
public boolean add(E e)
{
ensureCapacity(size+1);
elementData[size++] = e;
return true;
}
An important point to note from the above code is that we are checking the capacity of the ArrayList, before adding the element. ensureCapacity() determines what is the current size of occupied elements and what is the maximum size of the array. If the size of the filled elements (including the new element to be added to the ArrayList class) is greater than the maximum size of the array then increase the size of the array. But the size of the array can not be increased dynamically. So what happens internally is new Array is created with the capacity
到 Java 6
int newCapacity = (oldCapacity * 3)/2 + 1;
(更新)来自Java 7
int newCapacity = oldCapacity + (oldCapacity >> 1);
此外,旧数组中的数据被复制到新数组中。
数组列表中有开销方法这就是为什么数组比数组列表快。
如果提前知道数据有多大,那么使用数组会更快。
List更加灵活。你可以使用由数组支持的数组列表。