问Java中的数组或列表。哪个更快？

EN

我猜最初的海报来自于C++/STL背景，这造成了一些混乱。在C++中，std::list是一个双向链表。

在Java语言中，[java.util.]List是一个无需实现的接口( C++术语中的纯抽象类)。List可以是一个双向链表-提供了java.util.LinkedList。然而，当你想创建一个新的List时，有99次你想要改用java.util.ArrayList，这大致相当于C++ std::vector。还有其他的标准实现，比如由java.util.Collections.emptyList()和java.util.Arrays.asList()返回的那些。

从性能的角度来看，必须通过一个接口和一个额外的对象会有很小的影响，然而运行时内联意味着这几乎没有任何意义。还要记住，String通常是一个对象加数组。因此，对于每个条目，您可能有另外两个对象。在C++ std::vector<std::string>中，尽管按值复制时没有这样的指针，但字符数组将形成字符串的对象(这些对象通常不会共享)。

如果这段代码对性能非常敏感，那么可以为所有字符串的所有字符创建一个char[]数组(甚至是byte[])，然后创建一个偏移量数组。IIRC，这就是javac的实现方式。

不，因为从技术上讲，数组只存储对字符串的引用。字符串本身被分配到不同的位置。对于一千个项目，我会说列表会更好，它更慢，但它提供了更多的灵活性，更容易使用，特别是如果你要调整它们的大小。

如果你有数千个，考虑使用trie。trie是一种树状结构，它合并了存储字符串的公共前缀。

例如，如果字符串是

intern
international
internationalize
internet
internets

trie将存储：

intern
 -> \0
 international
 -> \0
 -> ize\0
 net
 ->\0
 ->s\0

字符串需要57个字符(包括空终止符'\0')进行存储，外加保存它们的String对象的大小。(事实上，我们可能应该将所有大小四舍五入到16的倍数，但是...)粗略地称其为57 +5= 62字节。

trie需要29个(包括空终止符'\0')用于存储，加上trie节点的大小，这是对一个数组和一个子trie节点列表的引用。

对于这个例子，这可能是相同的；对于数千人来说，只要你有共同的前缀，它可能就会变得更少。

现在，当在其他代码中使用trie时，您必须转换为字符串，可能需要使用StringBuffer作为中介。如果许多字符串同时作为字符串在trie之外使用，这是一种损失。

但是，如果您当时只使用了几个--比方说，在字典中查找单词-- trie可以为您节省大量空间。绝对比在HashSet中存储它们的空间要小。

你说你“连续”地访问它们--如果这意味着按字母顺序，那么trie显然也会免费给你字母顺序，如果你先深度迭代它的话。