这篇文章分为两个主要部分。第一部分介绍了原始测试用例和结果，以及我对此的看法。第二部分详细介绍了修改后的测试用例及其结果。
该主题的原标题是“对数组的完全迭代明显快于链表”。由于更新的测试结果（在第二部分中介绍），标题已更改。
第一节：原始测试用例
对于完整的单向顺序遍历，已知链表和数组具有相似的性能，但是由于连续数组的缓存友好性（引用局部性），它可能会（稍微）更好地执行。为了了解它在实践中是如何工作的（Android、Java），我检查了上述声明，并进行了一些测量。
首先，我的幼稚假设。让我们看一下下面的类：
private static class Message {
public int value1;
public Message next;
public Message(java.util.Random r, Message nextmsg) {
value1 = r.nextInt();
next = nextmsg;
}
}
在第一个测量场景中，它的next字段根本不会被使用。下面的代码创建一个包含 1,000,000 个Message实例的数组，然后循环遍历该数组。它测量迭代需要多少时间。
Log.i("TEST", "Preparing...");
final int cnt = 1000000;
int val = 0;
java.util.Random r = new java.util.Random();
Message[] messages = new Message[cnt];
for (int i = 0; i < cnt; i++) {
messages[i] = new Message(r, null);
}
Log.i("TEST", "Starting iterating...");
long start = SystemClock.uptimeMillis();
for (int i = 0; i < cnt; i++) {
Message msg = messages[i];
if (msg.value1 > 564645) {
val++;
}
}
Log.w("TEST", "Time: " + (SystemClock.uptimeMillis() - start) + ", result: " + val);
第二个测量构建并测量Message对象的链接列表：
Log.i("TEST", "Preparing...");
final int cnt = 1000000;
int val = 0;
java.util.Random r = new java.util.Random();
Message current = null;
Message previous = null;
for (int i = 0; i < cnt; i++) {
current = new Message(r, previous);
previous = current;
}
previous = null;
Log.i("TEST", "Starting iterating...");
long start = SystemClock.uptimeMillis();
while (current != null) {
if (current.value1 > 564645) {
val++;
}
current = current.next;
}
Log.w("TEST","Time: " + (SystemClock.uptimeMillis() - start) + ", result: " + val);
第一个测试持续产生41-44毫秒，而第二个测试产生80-85毫秒。链表迭代似乎慢了 100%。
我的（可能有缺陷的）思路和问题如下。我会欢迎（事实上，鼓励）任何更正。
好的，我们经常可以读到一个数组是一个连续的内存块，因此顺序访问它的元素比链表的缓存更友好。但是在我们的例子中，数组的元素只是对象引用，而不是Message对象本身（在 Java 中，我们没有值类型，即 C# 中的结构，我们可以将其存储在数组中）。因此，“引用的局部性”只适用于数组元素本身，而这些只指定了对象的地址。因此，Message实例（通常）仍然可以在内存中的“任何地方”，因此“引用位置”不适用于实例本身。从这一点来看，看起来我们与链表的情况相同：实例本身可能驻留在内存中的“任何地方”：数组只保证它们的引用存储在一个连续的块中......
...这里是用例：完整的顺序遍历（迭代）。首先，让我们检查一下我们如何在每种情况下获取对实例的引用。在数组的情况下，它非常有效，因为它们位于一个连续的块中。但是在链表的情况下，我们也很好，因为一旦我们访问了一个Message实例（这就是我们迭代的原因！），我们立即拥有对下一个实例的引用。并且由于我们已经访问了一个字段，Message因此缓存应该支持访问另一个字段（“下一个”）（同一对象的字段也具有引用的局部性 AFAIK，它们也在一个连续的块中）。总而言之，它似乎分解为：
- 该数组提供了对引用的缓存友好迭代。
Message实例本身可能在内存中的“任何地方”，我们也需要访问它们。 - 链表提供在访问当前
Message实例时获取对下一个元素的引用。这是“免费的”，因为Message无论如何都必须访问每个实例（就像在数组的情况下一样）。
因此，基于上述情况，看起来数组并不比链表好。唯一的例外是当数组是原始类型时（但在这种情况下，将它与链表进行比较是没有意义的）。所以我希望它们的表现相似，但事实并非如此，因为存在巨大差异。事实上，如果我们假设数组索引在每次访问元素时都需要进行范围检查，那么链表（理论上）甚至可以更快。（数组访问的范围检查可能被 JIT 优化掉了，所以我知道这不是一个有效的点。）
我的猜测如下：
造成 100% 差异的原因可能不是阵列的缓存友好性。相反，JIT 执行在链表遍历的情况下无法完成的优化。如果消除了范围检查和（VM 级别）空值检查，那么我猜“array-get”字节码指令可能比我在链表案例中的“field-get”（或其他任何名称）指令更快（？ ）。
即使这些
Message实例可能在内存中的“任何地方”，它们也可能彼此非常接近，因为它们是“同时”分配的。但是无法缓存 1,000,000 个实例，只能缓存其中的一部分。在这种情况下，顺序访问在数组和链表情况下都是缓存友好的，所以这并不能解释差异。Message我将访问的实例的一些智能“预测”（预取） ？Message即不知何故，实例本身仍然存在缓存友好性，但仅在数组访问的情况下。
更新：由于收到了几条评论，我想在下面对它们做出反应。
@不可靠：
从高地址到低地址访问链表。如果它是相反的方式，即 next 指向一个较新的对象，而不是以前的对象怎么办
非常好的地方！我没想到这个小细节布局可能会影响测试。我今天将对其进行测试，并将返回结果。（编辑：结果在这里，我用“第 2 节”更新了这篇文章）。
@Torben 评论：
我还要说，这整个练习似乎毫无用处。您说的是 100000 次迭代的 4ms 改进。似乎是过早的优化。如果您遇到这是一个瓶颈的情况，那么请描述它，我们可以调查它（因为它肯定会比这更有趣的问题）。
如果你不感兴趣，那么你可以忽略这个话题（而不是发 4 次）。关于您对“过早优化”的毫无根据的假设-恐怕您阅读了太多SO并且执行的工业级开发太少。具体情况是在与模拟相关的软件中，它可能必须每秒遍历这些列表数次。事实上，120 多毫秒的延迟可能会影响应用程序的响应能力。
我很欣赏你对此的想法，但我真的无法从你的帖子中找到问题。:) 编辑：数组迭代速度快 50%。快 100% 意味着零时间消耗。
我敢肯定，从我的帖子中可以很明显地看出，我想知道为什么存在非常显着的差异，而论点会暗示其他情况。感谢您的更正：确实，我想写的是链表案例慢了 100%。
第二部分：修改后的测试用例
对我来说， irreputable有一个非常有趣的观察：
从高地址到低地址访问链表。如果它是相反的方式，即 next 指向一个较新的对象，而不是以前的对象怎么办
我更改了链表结构，使其next指针的方向等于其节点的实例化顺序：
Message current = null;
Message previous = new Message(r, null);
Message first = previous;
for (int i = 0; i < cnt; i++) {
current = new Message(r, null);
previous.next = current;
previous = current;
}
previous = current = null;
（请注意，创建算法可能不是最紧凑的算法，我想我知道一种更好的方法。）遍历这个链表的代码：
while (first != null) {
if (first.value1 > 564645) {
val++;
}
first = first.next;
}
现在我得到的结果一直是37-39毫秒（好吧，我们可以说这正是阵列的性能，但实际上，它在每个测试用例中都稍微快一点，不断地。）而不是“反向”的80毫秒链表，快一倍！
然后我也对原始数组测试用例进行了类似的测试：我将数组遍历更改为相反的方向（倒计时循环）：
for (int i = cnt - 1; i >= 0; i--) {
Message msg = messages[i];
if (msg.value1 > 564645) {
val++;
}
}
结果一直是85-90毫秒！原始测试用例产生 40-41 毫秒。
现在似乎有两个新结论（和一个问题）：
最初的说法似乎是正确的，即当与链表进行比较时，数组的“引用位置”（由于连续的内存块）在“引用类型”（即对象）数组的情况下并没有提供优势. 这是因为对象数组只保存对对象实例的引用，而不是对象实例本身（理论上，它可以在内存中的“任何地方”，就像链表的情况一样）。
在我的测试用例中，结果似乎取决于traversal 的方向，即使在数组场景（！）的情况下也是如此。这怎么可能？
总结一下我的测试结果：
在“正向”方向遍历中，链表稍微优于数组遍历（正如预期的那样：我们在获得实例时立即具有下一个
Message引用，即即使不需要访问数组元素来获取其地址）。在“向后”方向遍历中，两者的性能都弱了大约 100%（并且链表的性能也略胜于数组）。
有任何想法吗？
更新 1： dlthorpe提出了非常有价值的意见。我会在这里复制它们，因为它们可能有助于找到这个“谜语”的答案。
是否有任何迹象表明硬件在内存缓存控制器中实现了先行页面预取？不是只加载内存引用所需的内存页面，还加载下一个更高的页面以预期向前渐进式读取？这将消除页面加载等待通过内存的正向进展，但不会消除页面加载等待通过内存的反向进展。
[..]
我建议在完全不同的硬件上进行测试。大多数移动设备都运行某种形式的 ARM SoC。查看测试用例是否在英特尔硬件（如 PC 或 Mac）上显示出类似的偏差。如果你能挖出一台旧的 PowerPC Mac，那就更好了。如果这些没有显示类似的结果，那么这将指向 ARM 平台或其 Java 实现上的独特之处。
[..]
是的，您的访问模式大多是顺序的，但方向不同。如果您下方的某些东西正在执行预取但仅在一个方向上（预取下一个更高地址块），那么这将使结果偏向于在该方向上运行的测试。
更新 2：我在 PC 上运行了测试（Core i7 Nehalem 架构从 2009 年 2 月开始，8 GB RAM，Windows 7）。我在 .NET 2.0 源代码项目中使用了 C#.NET（但机器上安装了 .NET 4）。我的结果，有 2500 万个Message实例：
- 链表：57-60 ms
- 阵列：60-63毫秒
阅读的方向似乎并没有影响结果。