存储多种数据类型的项目时访问数组元素的恒定时间

Question

相对现代的语言（例如 ruby/python/js 等）如何在数组中存储多种数据类型，并且仍然能够在 O(1) 时间内使用其索引访问数组中的任何元素？

据我了解，我们进行简单的数学计算来确定指向任何元素的内存地址，并通过索引乘以数组每个元素的大小来确定。

Answer 1

首先，Ruby 语言规范、Python 语言规范和 ECMAScript 语言规范都没有规定数组（或在 Python 中称为列表）的任何特定实现策略。每个实施者都可以自由地按照自己的意愿实施它们。其次，把它们放在一起没有多大意义。例如，在 ECMAScript 中，数组实际上只是具有数字属性的对象，而实际上，这些数字属性甚至不是真正的数字，它们是字符串。第三，它们并不真正存储多种数据类型。例如，Ruby 只有一种数据类型：对象。由于一切都是对象，一切都具有相同的类型，因此将对象存储在数组中没有问题。第四，至少 Ruby 语言规范实际上并没有保证数组访问的复杂度是 O(1)。不提供 O(1) 访问权限的 Ruby 实现很可能会被社区拒绝，但它不会违反任何规范。当然，现在任何实施者都可以随心所欲地发挥自己的聪明才智。例如，V8 检测数组的所有值何时都是数字，然后以不同的方式存储该数组。但这是 V8 的私有内部实现细节。

Answer 2

在内存中，异构数组是指针数组。每个数组元素都存储数组中该位置项的内存地址。由于内存地址的大小都相同，因此可以通过将数组索引乘以地址大小并将其与数组的基地址相加来找到每个地址的地址。