支持除了數組之外的隨機訪問的其他數據結構是什麼？

Question

我想如果有任何其他支持隨機訪問的數據結構（例如：恆定的時間複雜度） 在我看來，只有數組是以這種方式構建的。

注意：你不能建立在陣列之上的數據結構

Answer 1

哈希表還允許給出一個關鍵隨機訪問。因此與數組相反，它們是基於關鍵字的，而不是基於索引的，但仍允許對給定元素進行O（1）訪問。

Answer 2

我能想到列表和詞典。由於字典是鍵值對，因此它們更「隨機訪問」友好。

Answer 3

最終它取決於你對「數組」的含義。我會告訴你，RAM是一個很大的字節數組（技術上說是一個大字節數組加上一些重載的方法來讀取他們在1，2，（幾乎總是）4和（有時）8個字節塊並不總是工作如果你嘗試從一個字節「unaligned」開始讀取那個數字，那麼就是（或者不能完全停止）。所以一切都建立在一個數組之上。

如果通過「數組」你只是指「我使用的語言的結構調用數組和基於該數組的語言的所有結構」，那麼我可以簡單地（在C代碼中）一塊內存並以類似於數組的方式使用它（並且可能在其上構建一個哈希表）。關鍵詞是「相似」。

給定足夠的虛擬地址空間，您可以使用VirtualAlloc（在Windows下，在Linux下爲mmap）使用計算機的MMU模擬哈希表。這將是相當昂貴和無用的:-)我仍然認爲它是一個數組的另一個名稱（一個「稀疏」數組）。