Pha*_*nce 1 java arrays arraylist
我一直在阅读,ArrayList与其他一些数据结构相比,搜索更快,因为它是基于索引的LinkedList.我明白ArrayList内部使用的是Java array.这是来自Java的代码ArrayList,它将数据保存在array.
private transient Object[] elementData;
什么是' 基于索引的数据结构 ',为什么它更快？
此外,什么是数组的内存模型(数组在堆栈/堆组合中的结构),以便我能理解为什么访问数组中的元素更快？
ArrayList由数组支持.通常,假设通过索引寻址某些内容O(1),即在恒定时间内.在汇编中,您可以在固定时间内索引到内存位置,因为LOAD除了基址之外,还有某些指令采用可选索引.数组通常在内存中分配给一个连续的块.例如,假设您有一个基址0x1000(在数组开始的地方)并且您提供索引0x08.这意味着从您开始的阵列开始,0x1000您想要访问位置上的元素0x1008.处理器只需要添加基地址和索引,并在内存中查找该位置*.这可以在恒定的时间内发生.所以假设你在Java中有以下内容:
int a = myArray[9];
在内部,JVM将知道地址myArray.就像我们的例子一样,让我们假设它在位置0x1000.然后它知道它需要找到9下标.所以基本上它需要找到的位置很简单:
0x1000 + 0x09
这给了我们:
0x1009
所以机器可以简单地从那里加载它.
在C中,这实际上更加明显.如果您有一个数组,则可以像在Java中一样访问该i位置myArray[i].但是您也可以通过指针算法访问它(指针包含指针指向的实际值的地址)!因此,如果您有一个指针*ptrMyArray,您可以i通过执行来访问该下标*(ptrMyArray + i),这与我所描述的完全相同:基地址加下标!
相反,访问a中的位置的最坏情况LinkedList是O(n).如果你回想起你的数据结构,链表通常有一个head和一个tail指针,每个节点都有一个next指向下一个节点的指针.因此,要查找节点,您必须先开始,head然后依次检查每个节点,直到找到正确的节点.你不能简单地索引到一个位置,因为不能保证链表的节点在内存中彼此相邻; 他们可以在任何地方.
*索引还必须考虑元素的大小,因为您必须考虑每个元素占用多少空间.我提供的基本示例假定每个元素只占用一个字节.但如果你有更大的元素,那么公式基本上就是BASE_ADDRESS + (ELEMENT_SIZE_IN_BYTES * INDEX).在我们的例子中,假设1字节大小,公式减少到BASE_ADDRESS + INDEX.