gpt4 book ai didi

Java:什么是基于索引的数组访问,为什么它们很快?

转载 作者:行者123 更新时间:2023-11-29 06:36:13 25 4
gpt4 key购买 nike

我一直在读到,与 LinkedList 等其他数据结构相比,ArrayList 中的搜索速度更快,因为它是基于索引的。我知道 ArrayList 在内部使用 Java 数组。下面是来自 Java 的 ArrayList 的代码,它将数据保存在 array 中。

private transient Object[] elementData;

什么是“基于索引的数据结构”,为什么它更快?

此外,什么是数组的内存模型(数组在堆栈/堆组合中的结构)以便我可以理解为什么访问数组中的元素更快?

最佳答案

ArrayList 由数组支持。通常,假定按索引寻址某物是 O(1),即,在恒定时间内。在汇编中,您可以在恒定时间内索引到内存位置,因为某些 LOAD 指令除了基地址外还采用可选索引。数组通常以连续 block 的形式分配在内存中。例如,假设您的基地址为 0x1000(数组开始的位置)并且您提供的索引为 0x08。这意味着对于从 0x1000 开始的数组,您想要访问位置 0x1008 的元素。处理器只需要添加基地址和索引,并在内存中查找该位置*。这可以在恒定时间内发生。因此,假设您在 Java 中具有以下内容:

int a = myArray[9];

在内部,JVM 会知道 myArray 的地址。与我们的示例一样,让我们​​假设它位于位置 0x1000。然后它知道它需要找到第 9 个下标。所以基本上它需要找到的位置很简单:

0x1000 + 0x09

这给了我们:

0x1009

所以机器可以简单地从那里加载它。

在 C 中,这实际上更加明显。如果您有一个数组,您可以像在 Java 中一样访问第 i 位置作为 myArray[i]。但是您也可以通过指针算法访问它(指针包含指针指向的实际值的地址)!因此,如果您有一个指针 *ptrMyArray,您可以通过 *(ptrMyArray + i) 访问第 i 下标,这与我描述的是:基址加下标!

相比之下,访问 LinkedList 中的位置的最坏情况是 O(n)。如果你还记得你的数据结构,链表通常有一个 head 和一个 tail 指针,每个节点都有一个指向下一个节点的 next 指针节点。所以要找到一个节点,你必须从 head 开始,然后依次检查每个节点,直到找到正确的节点。您也不能简单地索引到一个位置,因为不能保证链表的节点在内存中彼此相邻;他们可能在任何地方。

*索引还必须考虑元素的大小,因为您必须考虑每个元素占用多少空间。我提供的基本示例假设每个元素只占用一个字节。但是如果你有更大的元素,公式基本上是 BASE_ADDRESS + (ELEMENT_SIZE_IN_BYTES * INDEX)。在我们的例子中,假设大小为 1 字节,公式简化为 BASE_ADDRESS + INDEX

关于Java:什么是基于索引的数组访问,为什么它们很快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20198844/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com