Как организовано физическое представление массивов в памяти?

Физически массив обычно хранится как непрерывный участок памяти, разделенный на ячейки одинакового размера. Каждая ячейка содержит один элемент массива.

Такое представление делает доступ по индексу очень быстрым.

Непрерывное размещение

Если массив состоит из элементов одного типа, размер каждого элемента известен заранее.

Например, если int занимает 4 байта, то массив из пяти int занимает примерно 20 байт подряд.

Индексы:    0    1    2    3    4
Значения:  10   20   30   40   50
Память:   [10] [20] [30] [40] [50]

Формула адреса элемента

Адрес элемента можно вычислить по формуле:

адрес элемента i = базовый адрес + i × размер элемента

Если индексация начинается не с нуля, формула учитывает нижнюю границу индекса.

адрес элемента i = базовый адрес + (i - нижняя_граница) × размер элемента

Именно поэтому доступ к элементу массива по индексу имеет сложность O(1): не нужно последовательно проходить предыдущие элементы.

Одномерные массивы

Одномерный массив — это линейная последовательность элементов. Он проще всего отображается на память.

Пример:

A[0], A[1], A[2], A[3]

Двумерные массивы

Двумерный массив логически выглядит как таблица, но память все равно линейна. Поэтому строки и столбцы раскладываются в одну последовательность.

Чаще всего используется хранение по строкам:

A[0][0], A[0][1], A[0][2], A[1][0], A[1][1], A[1][2]

В некоторых языках и системах может применяться хранение по столбцам.

Массивы ссылок

Если массив содержит объекты, строки или другие сложные структуры, в памяти массива могут лежать не сами объекты, а ссылки на них.

Например, массив строк часто хранит набор ссылок, а сами строки расположены в других местах памяти.

Статические и динамические массивы в памяти

Статический массив обычно имеет фиксированный размер и может размещаться в стеке или статической области памяти.

Динамический массив размещается в куче. Если ему не хватает места, создается новый более крупный участок памяти, элементы копируются, а старый участок освобождается сборщиком мусора или вручную.

Преимущества такого представления

• быстрый доступ по индексу;
• компактное хранение однотипных данных;
• хорошая работа с кэшем процессора;
• простая адресная арифметика.

Недостатки

• вставка в середину требует сдвига элементов;
• удаление из середины тоже требует сдвига;
• фиксированный массив нельзя просто расширить;
• для больших массивов нужен непрерывный свободный участок памяти.

Вывод

массив физически обычно представлен непрерывным блоком памяти. Это обеспечивает быстрый доступ по индексу, но делает вставку, удаление и изменение размера менее удобными, чем в динамических структурах данных.