爲什麼在數組O（1）中查找？

Question

我相信在除Ruby之外的其他語言中，數組查找是O（1），因爲您知道數據的起始位置，並且將索引乘以數組所保存的數據的大小，然後訪問該內存位置。

但是，在Ruby中，一個數組可以包含來自不同類的對象，那麼它如何設法查找O（1）的複雜性呢？

Answer 1

什麼@Neil斯萊特說，更詳細一點...

基本上有兩種可能的方法來儲存不同大小的異類對象的數組：

1. 商店中的對象爲一單 - 或雙 - linked list，每個單獨對象的存儲空間前面有指向前一個和/或後一個對象的指針。這種結構的好處是可以很容易地在任意點插入新對象，而不會圍繞其餘的陣列移動，但是巨大的缺點是，通過位置查找對象通常是O(N)，因爲你必須從一個列表的結尾並逐個節點地跳轉，直到你到達第n個節點。

2. 將常量指針的表或數組存儲到單個對象中。由於此查找表包含連續排序佈局中的大小不等的項目，請查找各個對象的地址O(1);該表只是一種C型陣列，即使在RISC CPU架構上，查找也只需要幾個機器指令。

（用於存儲單個對象的分配策略也很有趣和複雜的，但沒有太大的意義，以你的問題。）

如Perl/Python的/ Ruby的動態語言幾乎都齊齊＃ 2爲他們的通用列表/數組類型。換句話說，它們使查找比在列表中隨機位置處插入對象更高效，這對於許多應用程序來說是更好的選擇。

我不熟悉的實現細節的Ruby，但他們很可能十分類似Python的list類型，其性能和設計在effbot.org在美妙的詳細解釋。

Answer 2

其實現可能包含一組內存地址，指向實際的對象。因此，它仍然可以查找而不循環數組。