Базовый CS с нуля
Коллекции в памяти
У тебя есть чистая картина массива чисел: один непрерывный блок ячеек одинакового размера. Но реальные программы редко хранят простые числа. Они хранят список пользователей, список заказов, объект, чьи поля сами объекты. Как это выглядит в памяти?
Здесь модель массива, кажется, ломается. Объект может быть большим и может расти; его нельзя плоско упаковать в 4-байтовую ячейку массива. Так как же массив хранит сотню объектов, каждый разного размера, и при этом сохраняет свою аккуратную сетку одинакового размера?
Ответ — важнейшая идея этого блока, и она приходит прямо из Блока 06: ячейки массива не хранят объекты. Они хранят ссылки — адреса, указывающие на объекты, которые живут в другом месте. Этот урок доводит эту идею до конца: любая вложенная структура данных — это на деле граф маленьких ячеек, связанных ссылками.
После этого урока ты сможешь объяснить, почему массив или объект из объектов хранит ссылки, а не сами объекты, описать, что на самом деле хранит каждая ячейка такой коллекции, и объяснить, почему вложенные данные образуют граф ячеек, связанных ссылками.
Вспомни: ячейки-значения и ячейки-ссылки. Из Блока 06, урок 04, в ячейке может лежать два вида вещей. Маленькое значение фиксированного размера — вроде числа — помещается прямо в ячейку. Большая структура — объект или массив — не помещается; вместо этого ячейка хранит ссылку: число, которое является адресом того, где эта структура на самом деле живёт. Ссылка — это ячейка, указывающая на другое место в памяти.
Поэтому ячейка никогда буквально не содержит большой объект. Она либо содержит маленькое значение целиком, либо содержит адрес большой вещи, хранимой в другом месте. Держи оба случая в уме до конца этого урока.
Массив чисел: значения, непрерывно. Когда массив хранит числа, каждая ячейка хранит
само число — маленькое значение фиксированного размера. Картина из уроков 01 и 02
держится точно: один непрерывный блок ячеек одинакового размера, каждая ячейка содержит
реальное значение, и base + i × element_size попадает в него.
Это простейший и самый плотный случай: данные и есть непрерывный блок. Ничто не указывает куда-то ещё.
Массив объектов: ссылки, непрерывно. Теперь предположим, что массив хранит объекты — скажем, список пользователей. Объект не помещается в одну маленькую ячейку. Поэтому массив не может хранить объекты внутри своего блока.
Вместо этого каждая ячейка массива хранит ссылку — адрес одного объекта, который живёт где-то ещё в памяти. Блок массива остаётся точно как раньше: непрерывные ячейки одинакового размера, потому что каждая ссылка одного фиксированного размера (адрес — просто число). Изменилось то, что ячейки содержат: не значения, а адреса.
Поэтому «массив объектов» — это два слоя. Слой первый: непрерывный блок массива из ячеек
одинакового размера со ссылками — arr[i] всё ещё достигает своей ячейки за константное
время. Слой второй: сами объекты, разбросанные по памяти там, где было место, каждый
указан одной ссылкой в массиве. Чтение users[2].name — это два прыжка: вычислить адрес
users[2], прочитать ссылку там, последовать по ней к объекту, затем найти поле name
внутри этого объекта.
Объект из объектов: то же самое, с именованными ячейками. То же происходит с
вложенным объектом. Если значение поля само объект, слот поля не хранит этот целый объект —
он хранит ссылку на него. company.address — это поле, чей слот хранит адрес отдельного
объекта address. Будь контейнер массивом (позиционные ячейки) или объектом (именованные
ячейки), правило одинаково: ячейка хранит маленькое значение прямо или хранит ссылку на
бо́льшую вещь.
Вложенные данные — это граф ячеек. Доведи это до конца. У объекта может быть поле, ссылающееся на другой объект, у которого есть поле, ссылающееся на третий объект, который ссылается на первый. Массив может хранить ссылки на объекты, хранящие ссылки на массивы.
Результат — не плоский блок и не простой список. Это граф: набор ячеек, где одни ячейки хранят простые значения, а другие хранят ссылки, указывающие на другие ячейки. «Иметь» большую вложенную структуру данных — значит держать одну ссылку — точку входа — и оттуда программа идёт от ссылки к ссылке, от ячейки к ячейке, достигая остального. Каждый список записей, каждое дерево, каждый вложенный объект, который ты когда-либо построишь, под капотом — это: маленькие ячейки, одни хранят значения, другие хранят адреса, соединённые ссылками.
Почему это работает
Почему не хранить объекты просто внутри блока массива? Потому что объекты не все
одного размера и могут расти после создания. Блок массива зависит от того, что каждая
ячейка одного фиксированного размера, — именно это делает base + i × element_size
работающим. Если бы ячейкам пришлось хранить целые объекты переменного размера, формула
индексации за константное время рухнула бы. Ссылки решают это в точности: ссылка всегда
одного и того же маленького фиксированного размера, насколько бы большим ни был объект, на
который она указывает. Массив сохраняет свою однородную сетку; объекты переменного размера
живут в другом месте. Косвенность — указывать вместо содержать — это то, что позволяет
контейнеру фиксированной формы хранить содержимое переменной формы.
Чтение users[1].age в массиве объектов.
users — массив из 3 объектов-пользователей. У блока массива базовый адрес 1000; каждая
ячейка хранит ссылку, а ссылка 4 байта. Объекты живут в другом месте: объект-пользователь
0 по адресу 7000, объект 1 по адресу 7100, объект 2 по адресу 7200. Нам нужен
users[1].age.
Шаг 1 — Достичь ячейки массива. Используй формулу индекса из урока 02:
адрес = база + индекс × размер_элемента = 1000 + 1 × 4 = 1004. Ячейка users[1] по
адресу 1004.
Шаг 2 — Прочитать ссылку. Программа читает ячейку по адресу 1004. Она не находит там объект-пользователь — она находит ссылку: значение 7100, адрес объекта-пользователя 1.
Шаг 3 — Последовать по ссылке. Программа идёт по адресу 7100, где объект-пользователь 1 на самом деле живёт. Это второй прыжок — действие «последовать по ссылке к вещи, на которую она указывает».
Шаг 4 — Найти поле. Теперь у объекта программа использует ключ age (урок 03), чтобы
найти слот поля age внутри объекта, и читает его значение.
Два слоя, два прыжка: арифметический прыжок в непрерывный массив, затем прыжок по ссылке наружу к объекту. Каждый доступ к «массиву объектов» работает так.
Частая ошибка
Распространённая ошибка — представлять массив объектов как один гигантский непрерывный блок с целыми объектами, упакованными встык внутри него. Это не та раскладка. Блок массива хранит только ссылки — маленькие адреса одинакового размера. Сами объекты отдельны, разбросаны там, где в памяти было место. Массив непрерывен; объекты, на которые он ссылается, — нет. Путать «массив непрерывен» с «объекты непрерывны» ведёт к неверным рассуждениям о том, как вложенные данные лежат в памяти.
Массив хранит 5 чисел. Каждая ячейка хранит само число (значение), а не ссылку. Введи 1 за да, 0 за нет.
Массив хранит 5 объектов. Что хранит каждая ячейка блока массива: введи 0 за целый объект, введи 1 за ссылку (адрес), указывающую на объект.
У массива объектов базовый адрес 1000, и каждая ячейка-ссылка 4 байта. Используя база + индекс x размер_элемента, по какому адресу ячейка-ссылка для элемента 2?
Чтение users[1].name в массиве объектов занимает сколько прыжков: один арифметический прыжок в массив, затем один прыжок по ссылке наружу к объекту. Всего прыжков?
Ссылка всегда одного фиксированного размера, насколько бы большим ни был объект, на который она указывает. Благодаря этому массив ссылок может сохранить свою непрерывную сетку одинакового размера. Введи 1 за да, 0 за нет.
Как массив объектов на самом деле лежит в памяти?
Ячейка хранит либо маленькое значение фиксированного размера прямо, либо ссылку — адрес большей структуры, хранимой в другом месте. Массив чисел — простой случай: каждая ячейка хранит значение, и данные и есть непрерывный блок. Но массив объектов — или объект из объектов — не может упаковать объекты переменного размера в свою сетку одинакового размера. Вместо этого каждая ячейка хранит ссылку, а объекты живут разбросаны в другом месте; контейнер остаётся непрерывной сеткой одинакового размера, потому что каждая ссылка одного фиксированного размера. Достижение значения в такой коллекции занимает два прыжка: один в непрерывный контейнер, затем один по ссылке наружу к объекту. Доведённые до конца, вложенные данные — это граф ячеек: маленькие ячейки, одни хранят значения, другие хранят ссылки, соединённые вместе, — и держать вложенную структуру — это просто держать одну ссылку в этот граф.