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

В PHP массивы реализованы как упорядоченные хеш-таблицы (ordered hash maps). Индексы (ключи) хранятся в специальной структуре данных - Bucket, которая содержит:

• хеш ключа (для строковых ключей) или сам ключ (для целочисленных)
• значение (через zval - контейнер для данных PHP)
• указатель на предыдущий и следующий элемент (для поддержания порядка вставки)

Внутренняя структура массива - это два связанных списка:

1. Хеш-таблица (для быстрого доступа по ключу) - массив корзин (arBuckets), где каждый элемент - это связный список Bucket с одинаковым хешем.
2. Двусвязный список (для сохранения порядка) - каждый Bucket хранит ссылки на предыдущий и следующий добавленный элемент.

При добавлении элемента:

• Для целочисленного ключа он используется как хеш (если не превышает размер таблицы).
• Для строкового - вычисляется хеш-функцией (DJBX33A).
• Элемент помещается в соответствующую корзину хеш-таблицы и добавляется в конец двусвязного списка.

Таким образом, PHP-массивы поддерживают:

• O(1) доступ по ключу (в среднем)
• O(n) доступ по числовому индексу (если ключи не последовательные)
• Сохранение порядка вставки (благодаря двусвязному списку)