我相信在除Ruby之外的某些语言中,Array查找是O(1)因为您知道数据的起始位置,并且您将索引乘以数组所持有的数据的大小,然后访问该内存位置.
但是,在Ruby中,Array可以包含来自不同类的对象,那么它如何设法查找O(1)复杂度？
什么@尼尔斯莱特说,更详细一点......
基本上有两种合理的方法来存储不同大小的异构对象数组:
将对象存储为单链接或双链接列表,每个单独对象的存储空间前面都有指向前一个和/或后一个对象的指针.这种结构的优点是可以很容易地在任意点插入新对象,而不会在阵列的其余部分周围移动,但是巨大的缺点是通常按位置查找对象O(N),因为你必须从一端开始列表中的每个节点逐个跳转,直到到达第n个节点.
将一个常量大小的表或数组存储到各个对象中.由于此查找表包含连续有序布局中的常量项,因此查找单个对象的地址O(1); 该表只是一个C风格的数组,其中查询只需要1到1的机器指令,即使在RISC CPU架构上也是如此.
(用于存储单个对象的分配策略也很有趣且复杂,但与您的问题无关.)
像Perl/Python/Ruby这样的动态语言几乎都选择#2作为通用列表/数组类型.换句话说,它们使查找比在列表中的随机位置插入对象更有效,这对于许多应用程序来说是更好的选择.
我不熟悉Ruby的实现细节,但它们可能与Python的list类型非常相似,其性能和设计在effbot.org上有详细的解释.