> Как хранятся индексы в массивах PHP (PHP)

Короткий ответ

В PHP массивы - это упорядоченные hash-таблицы (ordered hash maps). Индексы не хранятся отдельно как в C-массивах: каждый элемент - это bucket с ключом (int или string), значением и указателями на предыдущий и следующий bucket для сохранения порядка вставки. Числовые ключи хэшируются так же, как строковые, но сравнение идёт по целочисленному значению. Память под buckets выделяется динамически через zend_hash, поэтому массив не требует непрерывного блока памяти.

Подробное объяснение

Внутренняя структура массива в PHP (Zend Engine 3+) - это zend_array (HashTable):

• arData - указатель на массив buckets (не на первый элемент, а на сдвиг, чтобы упростить доступ по индексу).
• nNumOfElements - количество элементов.
• nTableSize - текущая ёмкость (степень двойки, минимум 8).
• nTableMask - маска для вычисления хэш-слота (hash & nTableMask).
• nNextFreeElement - следующий автоинкрементный числовой ключ.

Каждый bucket (Bucket) содержит:

• h - хэш ключа (uint64). Для int-ключей это само значение, для строк - хэш-функция (DJBX33A).
• key - указатель на строку (если ключ строковый), для int - NULL.
• val - zval (значение).
• next - индекс следующего bucket в цепочке коллизий (в пределах одного слота).
• prev и next для двусвязного списка, поддерживающего порядок вставки.

Ключевые моменты:

1. Порядок вставки сохраняется через двусвязный список buckets, независимо от хэш-слотов. Это отличает PHP от обычных hash-таблиц.
2. Числовые индексы не хранятся как отдельные сущности - они участвуют в хэшировании. Для int-ключа h = key, слот = h & nTableMask.
3. Автоинкремент: при добавлении без ключа используется nNextFreeElement, который увеличивается, но при удалении элементов не уменьшается (дырки в числовой последовательности возможны).
4. Перестройка (rehash): при заполнении таблицы (когда nNumOfElements >= nTableSize * 0.7) размер удваивается, все buckets пересчитываются. Это O(n), но амортизированно O(1).
5. Компактизация: после удаления элементов таблица может быть сжата (при nNumOfElements < nTableSize / 2), чтобы уменьшить потребление памяти.
6. Строковые ключи хранятся с интернированием (interned strings) для экономии памяти, если строка используется в нескольких местах.

На практике

• array_values() переиндексирует массив с нуля - фактически создаёт новый HashTable с новыми ключами.
• unset($arr[1]) не сдвигает остальные элементы - порядок сохраняется, но ключ 1 исчезает. Индекс 2 остаётся на своём месте.
• array_splice() переиндексирует, потому что физически перестраивает список.
• Итерация через foreach идёт по двусвязному списку, а не по слотам - поэтому порядок вставки сохраняется.
• Доступ по ключу - O(1) в среднем, но при коллизиях (редко) - O(n) в худшем случае.
• Память: каждый bucket - это ~32 байта на 64-битной системе плюс zval (16 байт). Для больших массивов это заметно.

Пример кода

PHP
$arr = [];
$arr[5] = 'a';      // ключ int 5, h = 5
$arr['foo'] = 'b';  // строковый ключ, h = hash('foo')
$arr[] = 'c';       // ключ 6 (nNextFreeElement = 6)

unset($arr[5]);     // bucket удаляется, порядок: 'foo', 'c'
$arr[] = 'd';       // ключ 7 (не 5!), nNextFreeElement продолжает расти

// foreach идёт по списку: foo, c, d
foreach ($arr as $k => $v) {
    echo "$k => $v\n";
}
// foo => b
// 6 => c
// 7 => d

// array_values переиндексирует
$reindexed = array_values($arr); // [0 => 'b', 1 => 'c', 2 => 'd']

Как отвечать на собеседовании

Начни с того, что PHP-массив - это упорядоченная hash-таблица. Подчеркни два ключевых отличия от классических hash-таблиц: сохранение порядка вставки через двусвязный список и отсутствие отдельного хранения индексов (ключ участвует в хэшировании). Упомяни, что числовые и строковые ключи обрабатываются единообразно, но int-ключи хэшируются быстрее. Расскажи про автоинкремент и его поведение после удаления элементов. Если спросят про сложность - скажи O(1) для доступа и вставки в среднем, O(n) для перестройки при rehash. Для senior-уровня добавь детали про nTableMask, nNextFreeElement и компактизацию.

Что проверяет интервьюер

• Понимание внутреннего устройства, а не только синтаксиса.
• Знание trade-off: почему PHP-массивы удобны, но тяжелее по памяти, чем C-массивы.
• Умение объяснить поведение unset и array_values с точки зрения структуры данных.
• Понимание амортизированной сложности и механизма rehash.
• Способность связать теорию с практикой: например, почему foreach по большому массиву быстрее, чем for с count() (в for каждый вызов $arr[$i] - это хэш-поиск, а foreach идёт по списку).

Типичные ошибки

• Утверждение, что индексы хранятся как в C-массивах (непрерывный блок памяти).
• Ожидание, что после unset($arr[1]) следующий $arr[] получит ключ 1 - это не так, nNextFreeElement не уменьшается.
• Смешение порядка вставки и порядка сортировки по ключу - PHP сохраняет порядок вставки, а не сортирует.
• Игнорирование того, что строковые ключи тоже хэшируются и могут давать коллизии.
• Утверждение, что доступ по ключу всегда O(1) - в худшем случае при коллизиях O(n), хотя на практике это редкость.