ArrayList 如何提供随机访问行为? [英] How ArrayList provides random access behaviour?

问题描述

ArrayList 被简单地实现为一个 Object[].我知道它实现了 RandomAccess 接口，但它只是一个标记接口...

ArrayList is simply implemented as an Object[]. I know it implements the RandomAccess interface, but it is only a marker interface...

所以，我的问题是:ArrayList 为什么/如何提供随机访问功能?

So, my question is: Why/How ArrayList provides the random access feature?

编辑 1:也许我应该更清楚地说明这一点......我想了解的是为什么当它是一个对象 [] 时访问元素是恒定的时间?

EDIT 1: perhaps I should make this clearer...what I want to understand is why it is constant time to access the element while it is an Object[]?

推荐答案

通过比较 LinkedList、ArrayList 和 Array 在视觉上应该使事情变得简单:

By comparing a LinkedList, an ArrayList and an Array visually should makes things easy:

链接列表:

+----+      +----+      +----+      +----+
|Head| ---> | e1 | ---> | e2 | ---> | e3 | ---> null
+----+      +----+      +----+      +----+

现在，假设我想获取元素 e2，但是链表本身持有 headNode 的引用.要到达 e2，我必须从 HeadNode 一路遍历到 e2.显然，这不提供恒定时间操作，因为您不能在不遍历列表的情况下直接访问任何元素.

Now, let say I want to get element e2, however the linkedlist itself holds the reference of the headNode. To get to e2, I have to traverse all the way to e2 from the HeadNode. Clearly, this does not provides constant time operation as you can't access any of the elements directly without traversing through the list.

数组:

+----++----++----++----+
| e1 || e2 || e3 || e4 |  (value)
+----++----++----++----+
| 01 || 02 || 03 || 04 |  (address)
+----++----++----++----+

想象一下，当你有一个保存数组的变量时，变量中只保存了第一个元素(e1)的地址.以下数组元素将存储在下一个可用内存块中.数组元素在内存中按顺序排列在一起.当您需要访问特定元素时，这使其成为恒定时间操作.例如，当您要访问 e3 并且每个内存块为 4 个字节时.从第一个元素开始，从数组引用中移动 2 个内存块(8 字节).恒定时间操作的关键是:无需遍历.它只需要根据每个块的大小和要移动的块数(由数组索引表示)计算从当前位置移动多少字节.在 Java 中，当您尝试超出为数组分配的内存范围时，它会给您一个 ArrayIndexOutOfBoundsException.

Imagine this, when you have a variable holding an array, only the address of the first element (e1) is held in the variable. The following array elements will be stored in the next available memory block. The array elements sit next to each other in a sequential sequence in memory. This makes it a constant time operation when you need to access a specific element. For example, when you want to access e3 and each memory block is 4 bytes. From the first element, move 2 blocks of memory (8 bytes) from the array reference. The key to constant time operation is: No traversing needed. It just has to calculate how many bytes to shift from current location according to size of each block and number of blocks to move (indicated by array index). In Java, when you try to shift beyond the bounds of the allocated memory for the array, it gives you an ArrayIndexOutOfBoundsException.

ArrayList:

Arraylist 使用与数组相同的思想.它将最初分配的大小为 10.当它需要增长时(例如添加更多元素)，它会创建一个新的数组，增加存储长度.由于数据是按数组存储的，所以操作时间和数组一样(即常数时间).

Arraylist uses the same idea of an array. It will allocate a size of 10 initially. When it needs to grow (more elements added for instance), it creates a new array with added length for storage. Since the storage of the data is by array, the operation time will be same as array (i.e. constant time).

这篇关于ArrayList 如何提供随机访问行为?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！