假设我们有一个未排序的数组和链表。 搜索两个数据结构的元素时最糟糕的情况是O（n），但我的问题是：
由于在缓存中使用空间局部性，阵列是否仍然会更快，或者缓存是否会使用分支局部性，允许链表与任何阵列一样快？
我对数组的理解是，如果访问了一个元素，那么该存储器块和许多周围的块将被带入高速缓存，从而允许更快的存储器访问。
我对链表的理解是，由于遍历列表的路径是可预测的，因此缓存将利用它并仍然存储适当的内存块，即使列表中的节点在堆内可能相距很远。
假设我们有一个未排序的数组和链表。 搜索两个数据结构的元素时最糟糕的情况是O（n），但我的问题是：
由于在缓存中使用空间局部性，阵列是否仍然会更快，或者缓存是否会使用分支局部性，允许链表与任何阵列一样快？
我对数组的理解是，如果访问了一个元素，那么该存储器块和许多周围的块将被带入高速缓存，从而允许更快的存储器访问。
我对链表的理解是，由于遍历列表的路径是可预测的，因此缓存将利用它并仍然存储适当的内存块，即使列表中的节点在堆内可能相距很远。
您对阵列案例的理解大多是正确的。如果按顺序访问数组，许多处理器不仅会获取包含该元素的块，还会预取后续块以最大限度地减少等待缓存未命中所花费的周期。如果您使用的是Intel x86处理器，则可以在Intel x86优化中找到有关此内容的详细信息 手册。此外，如果数组元素足够小，则加载包含元素的块意味着下一个元素可能位于同一个块中。
不幸的是，对于链表，从处理器的角度来看，负载模式是不可预测的。在地址X处加载元素时，不知道下一个地址是（X + 8）的内容。
作为一个具体示例，顺序数组访问的加载地址序列很好且可预测。 例如，1000,1016,1032,1064等。
对于链表，它看起来像： 1000,3048,5040,7888等很难预测下一个地址。