Как стать автором
Обновить

Как устроены массивы в PHP

PHP *
В прошлой статье я рассказывал о переменных, теперь пойдет речь о массивах.

Что такое массивы на уровне PHP?


На уровне PHP, массив — это упорядоченный список скрещенный с мэпом. Грубо говоря, PHP смешивает эти два понятия, в итоге получается, с одной стороны, очень гибкая структура данных, с другой стороны, возможно, не самая оптимальная, точнее, как выразился Anthony Ferrara:
PHP arrays are a great one-size-fits-all data structure. But like all one-size-fits-all <anything>, jack-of-all-trades usually means master of none.

Ссылка на письмо



(на картине изображен HashTable с Bucket-ами, В. Васнецов)

А начнем вот с чего — попробуем замерить память и время, съедаемое на каждое вставляемое значение. Сделаем это с помощью таких скриптов:

// time.php
$ar = array();
$t = 0;

for ($i = 0; $i < 9000; ++$i) {
    $t = microtime(1);
    $ar[] = 1;
    echo $i . ":" . (int)((microtime(1) - $t) * 100000000) . "\n";
}

// memory.php
$ar = array();
$m = 0;

for ($i = 0; $i < 9000; ++$i) {
    $m = memory_get_usage();
    $ar[] = 1;
    echo $i . ":" . (memory_get_usage() - $m) . "\n";
}


Запускаем эти скрипты php time.php > time и php memory.php > memory, и нарисуем графики по ним, ибо данных много и смотреть на цифры долго (данные по времени были собраны много раз и выровнены, чтобы избежать лишних скачков на графике).


(по оси X — кол-во эл-тов в массиве)

Как видно, на обоих графиках есть скачки и по потребляемой памяти и по использованному времени, и эти скачки происходят в одни и те же моменты.
Дело в том, что на уровне C (да и вообще на системном уровне), не бывает массивов, с нефиксированным размером. Каждый раз, когда вы создаете массив в C, вы должны указать его размер, чтобы система знала, сколько нужно памяти на него выделить.
Тогда как это реализовано в PHP и как объянить те скачки на графике?
Когда вы создаете пустой массив, PHP создает его с определенным размером. Если вы заполняете массив и в какой-то момент достигаете и превышаете этот размер, то создается новый массив с вдвое большим размером, все элементы копируются в него и старый массив уничтожается. Вообще, это стандартный подход.

И как это реализовано?


На самом деле, для реализации массивов в PHP, используется вполне себе стандартная структура данных Hash Table, о деталях реализации которой мы и поговорим.

Hash Table хранит в себе указатель на самое первое и последнее значения (нужно для упорядочивания массивов), указатель на текущее значение (используется для итерации по массиву, это то, что возвращает current()), кол-во элементов, представленых в массиве, массив указателей на Bucket-ы (о них далее), и еще кое-что.

Зачем
    нам
        ведра нужны
и куда
    нам
        их ложить


В Hash Table есть две главные сущности, первая — это собственно сам Hash Table, и вторая — это Bucket (далее ведро, чтобы не заскучали).

В ведрах хранятся сами значения, то есть на каждое значение — свое ведро. Но помимо этого в ведре хранится оригинал ключа, указатели на следующее и предыдущее ведра (они нужны для упорядочивания массива, ведь в PHP ключи могут идти в любом порядке, в каком вы захотите), и, опять же, еще кое-что.

Таким образом, когда вы добавляете новый элемент в массив, если такого ключа там еще нет, то под него создается новое ведро и добавляется в Hash Table.

Но что самое интересное — это как в Hash Table хранятся эти ведра.

Как было сказано выше, у HT есть некий массив указателей на ведра, при этом ведра доступны в этом массиве по некоему индексу, а этот индекс можно вычислить зная ключ ведра. Звучит немного сложно, но на самом деле, все гораздо проще чем кажется. Попробуем разобрать, как происходит получение элемента по ключу из HT:

  • Если ключ строковый — то происходит хеширование строки до integer-a (используется алгоритм хеширования DJBX33A):
    • Первоначальное значение хеша взято за магические 5381
    • На каждый символ ключа умножаем хеш на 33 и прибавляем номер символа по ASCII
  • На полученый числовой ключ накладывается маска (bitwise and), которая всегда равна размеру массива (который с ведрами) минус 1
  • В итоге этот ключ можно использовать как индекс, чтобы вытащить нужный указатель на Bucket из массива

Про маску: допустим массив указателей содержит 4 элемента, таким образом маска равна трем, то есть 11 в двоичной системе.
Теперь если в качестве ключа у нас получится число вроде 123 (1111011), то после наложения маски мы получим 3 (3 & 123), это число уже можно будет использовать как индекс.

После этого попробуем добавить в Hash Table, с маской 3, элементы с ключами 54 и 90. А оба этих ключа после наложения маски будут равны двойки.

Что делать с коллизиями?


У ведер оказывается есть еще пара карт в рукаве. Каждое ведро имеет также указатель на предыдущее и следующее ведро, у которых индексы (хеши от ключей) равны.
Таким образом, помимо основного двусвязного списка, который проходит между всеми ведрами, есть еще и мелкие двусвязные списки между теми ведрами, индексы которых равны. То есть получается примерно следующая картина:



Вернемся к нашему кейсу с ключами 54 и 90, и маской 3. После того, как вы добавите 54, структура HT будет выглядеть примерно так:

{
    nTableSize: 4,        // размер массива указателей на ведра
    nTableMask: 3,        // маска
    nNumOfElements: 1,    // число элементов в HT
    nNextFreeElement: 55, // это будет использовано тогда, когда вы захотите добавить элемент в конец массива (без ключа)
    ...,
    arBuckets: [
        NULL,
        NULL,
        0xff0, // представим, что это указатель на Bucket, а сам он описан ниже
        NULL
    ]
}

0xff0: {
    h: 54,         // числовой ключ
    nKeyLength: 0, // это длина ключа, в случае когда он строковый
    pData: 0xff1,  // указатель на значение, в данном случае на структуру zval
    ...
}


Теперь добавим элемент с ключом 90, теперь все будет выглядеть примерно так:

{
    nTableSize: 4,
    nTableMask: 3,
    nNumOfElements: 2,
    nNextFreeElement: 91,
    ...,
    arBuckets: [
        NULL,
        NULL,
        0xff0, // здесь все так же всего один Bucket
        NULL
    ]
}

0xff0: {
    h: 54,
    pListNext: 0xff2, // здесь хранится указатель на следующий Bucket по порядку (для итерирования)
    pNext: 0xff2,     // а сюда попал новый Bucket с таким же хешем
    ...
}

0xff2: {
    h: 90,
    pListLast: 0xff0, // это предыдущий элемент
    pLast: 0xff0,     // а это тот же предыдущий элемент
    ...
}


Теперь давайте добавим несколько элементов до переполнения nTableSize (напомню, что переполнение будет только тогда, когда nNumOfElements > nTableSize).
Добавим элементы с ключами 0, 1, 3 (такие, которых еще не было, и после наложения масок они останутся теми же), вот что будет:

{
    nTableSize: 8,         // теперь размер вдвое больше (прям как в той рекламе)
    nTableMask: 7,
    nNumOfElements: 5,
    nNextFreeElement: 91,  // это число осталось неизменным
    ...,
    arBuckets: [ // теперь некоторые ведра переместились на новые места, с учетом новой маски и следовательного нового индекса
        0xff3, // key = 0
        0xff4, // key = 1
        0xff2, // key = 90 - теперь здесь сидит ключ 90 (его индекс 90 & 7 = 2), а его бывший сосед съехал на 6-й индекс
        0xff5, // key = 3
        NULL,
        NULL,
        0xff0, // key = 54
        NULL
    ]
}

0xff0: {
    h: 54,
    pListNext: 0xff2, // порядок остался тот же, поэтому это значение неизменно
    pNext: NULL,     // а здесь теперь ничего
    ...
}

0xff2: {
    h: 90,
    pListNext: 0xff3,
    pListLast: 0xff0,
    pLast: NULL,
    ...
}

0xff3: {
    h: 0,
    pListNext: 0xff4,
    pListLast: 0xff2,
    ...
}

0xff4: {
    h: 1,
    pListNext: 0xff5,
    pListLast: 0xff3,
    ...
}

0xff5: {
    h: 3,
    pListNext: NULL, // он был добавлен последним
    pListLast: 0xff4,
    ...
}


То, что происходит после переполнения массива, называется rehash. По сути это итерирование по всем существующим ведрам (через pListNext), назначение их соседей (коллизий) и добавление ссылок на них в arBuckets.

А как же на самом деле происходит получение элемента по ключу? К предыдущему алгоритму добавится еще кое что:
  • Если ключ строковый — то происходит хеширование строки до integer-a (используется алгоритм хеширования DJBX33A):
    • Первоначальное значение хеша взято за магические 5381
    • На каждый символ ключа умножаем хеш на 33 и прибавляем номер символа по ASCII
  • На полученый числовой ключ накладывается маска (bitwise and), которая всегда равна размеру массива (который с ведрами) минус 1
  • Вытаскиваем ведро по индексу
  • Если ключ этого ведра равен искомому — поиск завершен, иначе:
  • В цикле берем ведро из pNext (если существует) и смотрим равен ли ключ

Так до тех пор, пока либо не закончатся ведра в pNext (тогда будет выкинут Notice), либо пока не будет найдено совпадение.

Стоит отметить, что в PHP почти все посторено на одной этой структуре HashTable: все переменные, лежащие в каком-либо scope-е, на самом деле лежат в HT, все методы классов, все поля классов, даже сами дефинишины классов лежат в HT, это на самом деле очень гибкая структура. Помимо прочего, HT обеспечивает практически одинаковую скорость выборки/вставки/удаления и сложность всех троих является O(1), но с оговоркой на небольшой оверхед при коллизиях.

Кстати, здесь я реализовал Hash Table в самом PHP. Ну, то есть, имплементировал PHP-шные массивы в PHP =)
Теги: phparrayinternalshash table
Хабы: PHP
Всего голосов 90: ↑77 и ↓13 +64
Комментарии 40
Комментарии Комментарии 40

Похожие публикации

Лучшие публикации за сутки