Теория: Реализация массивов

Когда мы говорим про примитивные типы данных, такие как int или double, то, на интуитивном уровне, все довольно понятно. Под каждое значение выделяется некоторое количество памяти в соответствие с типом, в которой и хранится само значение. А как должна выделиться память под хранение массива? И что такое массив в памяти? На уровне хранения понятия «массив» не существует. Массив представляется цельным куском памяти, размер которого вычисляется по формуле «количество элементов» * «количество памяти под каждый элемент». Из этого утверждения есть два интересных вывода:

• Размер массива — это фиксированная величина. Те динамические массивы, с которыми мы имеем дело, во многих языках реализованы уже внутри языка, а не на уровне железа
• Все элементы массива имеют один тип и занимают одно и то же количество памяти. Благодаря этому появляется возможность простым умножением (по формуле, описанной ниже) получить адрес той ячейки, в которой лежит нужный нам элемент. Именно это происходит под капотом, при обращении к элементу массива под определенным индексом

Фактически, индекс в массиве — смещение относительно начала куска памяти, содержащего данные массива. Адрес, по которому расположен элемент под конкретным индексом, рассчитывается так: начальный адрес + индекс * количество памяти, занимаемое одним элементом:

// Инициализация массива из пяти элементов типа int
// int занимает 4 байта
// Общее количество памяти выделенное под массив int * 5 = 4 * 5 = 20 байт
int[] numbers = {19, 10, 8, 17, 9};
numbers[3]; // 17

Адрес элемента, соответствующего индексу 3, вычисляется так: начальный адрес + 3 * 4 (размер типа данных int). Начальный адрес — это адрес ячейки памяти, начиная с которой располагается массив. Он формируется во время выделения памяти под массив. Ниже пример расчета адресов памяти под разные элементы массива numbers:

Рассмотрим еще раз определение массива:

// Первый элемент
// Начальный адрес + 4 * 0 = начальный адрес
numbers[0]; // 19

// Начальный адрес + 4 * 1 = начальный адрес + 4
// То есть сместились на 4 байта
numbers[1]; // 10

// Начальный адрес + 4 * 2 = начальный адрес + 8
// То есть сместились на 8 байт
numbers[2]; // 8

// Последний элемент
// Начальный адрес + 4 * 4 = начальный адрес + 16
// То есть сместились на 16 байт
// И сам элемент занимает 4 байта. В сумме как раз 20
numbers[4]; // 9

Теперь должно быть понятно, почему индексы в массиве начинаются с нуля. 0 — означает отсутствие смещения.