java - ArrayList 如何提供随机访问行为？

Question

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

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

编辑 1:也许我应该更清楚地说明这一点……我想了解的是，为什么在元素是 Object[] 时访问元素的时间是恒定的？

Answer 1

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

链表:

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

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

数组:

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

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

数组列表:

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