Какие другие структуры данных, кроме массива, поддерживают произвольный доступ?

Question

Я пытаюсь подумать, существует ли какая-либо другая структура данных, поддерживающая произвольный доступ (т. Е. Постоянная сложность по времени). Мне кажется, таким образом строится только массив.

Примечание: вы можете 'построить структуру данных поверх массива

Answer 1

В конце концов, это зависит от того, что вы имеете в виду под «массивом».Я скажу вам, что RAM - это большой массив байтов (технически это большой массив байтов плюс некоторые перегруженные методы для чтения их в блоках по 1, 2, (почти всегда) 4 и (иногда) 8 байтов, которые не всегда работаютхорошо (или не работает полная остановка), если вы пытаетесь читать, начиная с байта, "не выровненного" с этим числом).Так что все построено поверх массива.

Если под «Массивом» вы имеете в виду только «структуру, которую язык, который я использую, называет Массив, и все структуры этого языка, основанные на этом массиве», то я мог бы просто (в коде C) mallocкусок памяти и использовать его аналогично массиву (и, возможно, построить поверх него хэш-таблицу).Ключевое слово «аналог».

При наличии достаточного пространства виртуального адреса вы можете использовать VirtualAlloc (в Windows, mmap в Linux) для эмуляции хэш-таблицы с использованием MMU вашего компьютера.Это было бы довольно дорого и бесполезно :-) И я все равно считаю, что это Массив под другим именем («редкий» Массив).

Answer 2

Хеш-таблицы также допускают произвольный доступ по заданному ключу. Таким образом, в отличие от массивов, они основаны на ключах, а не на индексах, но все же допускают O (1) доступ к данному элементу.

Answer 3

Я могу думать о списках и словарях.Поскольку словари являются парами ключ-значение, они «более» удобны для произвольного доступа.