Я пытаюсь подумать, есть ли какая-либо другая структура данных, поддерживающая произвольный доступ (т.е. постоянная временная сложность). Мне кажется, что таким образом строится только массив.
Примечание: вы не можете построить структуру данных поверх массива.
Хэш-таблицы также допускают произвольный доступ по ключу. Таким образом, в отличие от массивов, они основаны на ключах, а не на индексах, но все же допускают доступ O (1) к данному элементу.
В конце концов, это зависит от того, что вы подразумеваете под «массивом». Я скажу вам, что ОЗУ представляет собой большой массив байтов (технически большой массив байтов плюс некоторые перегруженные методы для их чтения блоками по 1, 2, (почти всегда) 4 и (иногда) 8 байт, которые не всегда работают. ну (или не работает точка), если вы попытаетесь прочитать, начиная с байта, «не выровненного» с этим номером). Итак, все построено поверх массива.
Если под «массивом» вы имеете в виду только «структура языка, который я использую, вызывает массив и все структуры этого языка, основанные на этом массиве», тогда я мог бы просто (в коде C) malloc блок памяти и использовать его в способ, похожий на массив (и, возможно, построить поверх него хеш-таблицу). Ключевое слово "похожие".
При наличии достаточного виртуального адресного пространства вы можете использовать VirtualAlloc (в Windows, mmap в Linux) для эмуляции хеш-таблицы с использованием MMU вашего компьютера. Это было бы довольно дорого и бесполезно :-) И я бы все равно считал, что это массив с другим именем («разреженный» массив).
Я могу думать о списках и словарях. Поскольку словари представляют собой пары ключ-значение, они более удобны для произвольного доступа.
