Базовая структура

Базовые концепции

Массивы в C это всего лишь области памяти, доступ к элементам котрых осуществляется по смещению (offset). Это означает, что ключами массива должны быть целые числа и последовательность ключей должна быть непрерывной. Например, если у вас есть ключи 0, 1 и 2, то следующим ключом должен быть 3 и не может быть 214678462. Массивы в PHP сильно отличаются от сишных. Они поддерживают и строковые ключи, и не непрерывные числовые ключи, и смесь разных ключей.

Реализовать такую структуру на языке C можно двумя способами: первый способ — это binary search tree, в этом алгоритме и поиск, и вставка значений имеют сложность O(log n) (где n это число элементов в таблице). Второй способ — хеш-таблица, этот алгоритм в среднем имеет сложность поиска/вставки равную O(1), то есть элементы могут быть вставлены и извлечены за постоянное время. Таким образом, хеш-таблицы предпочтительны в большинстве случаев и именно эта техника использована в PHP.

Идея лежащая в основе хеш-таблиц проста: сложный ключ (такой как строка) преобразуется в число с помощью хеш-функции. Это число может быть использовано как смещение в обычном C-массиве. Проблема в том, что максимальное число ключей (2^32 или 2^64) гораздо меньше чем число строк (их множество бесконечно). По этому неизбежно хеш-функция будет иметь коллизии, то есть случаи, в которых две разных строки будут иметь одинаковые значения хеш-функции.

По этой причине должен быть реализован механизм разрешения коллизий. Есть два основных алгоритма решения этой проблемы, первый — открытая адресация (он не рассмотрен здесь). Второй алгоритм — метод цепочек (chaining), он и реализован в PHP. Этот метод просто хранит все элементы имеющие один и тот же хеш в связанном списке (linked list). Когда ищется ключ, PHP вычисляет его хеш, а затем проходит по связанному списку "возможных" значений до тех пор пока не найдет нужное. Ниже приведена иллюстрация разрешения коллизий методом цепочек:

Элементы этого связанного списка назыветюся Бакетами (Bucket), массив C содержащий заголовки связанных списков называется arBuckets.

Предположим, вы хотите удалить элемент из такой структуры. Например, у вас есть указатель на бакет "c" и вы хотите удалить этот элемент. Чтобы сделать это вам нужно в бакете "a" установить указатель следующего элемента на NULL. Поэтому вам нужно извлечь бакет "a", вы можете сделать это либо обходом связанного списка для заданного значения хеша, либо используя дополнительное хранилище указателей в обратном направлении. Второй вариант реализован в PHP: каждый бакет содержит указатель на следующий (pNext) и предыдущий (pLast) бакеты. Это проиллюстрировано на картинке:

Кроме того, хеш-таблицы в PHP упорядочены. Если вы обходите массив, то вы будете получать элементы в том порядке, в котором они были вставлены. Для реализации этого бакеты должны быть частью другого связанного списка, который определяет их порядок. То есть мы имеем двойной связанный список, существующей с той же целью, что описана выше. Указатель на следующий элемент хранится в pListNext, на предыдущий в pListLast. Дополнительно хеш-таблица содержит указатели на начало списка (pListHead) и его конец (pListLast). Ниже приведен пример того как связанный список может выглядеть для элементов "a", "b", "c" (в таком порядке):

Другими словами, pNext и pLast это указатели на следующий и предыдущий бакеты в пределах одного значения хеша (в примере выше a ссылается на c и наоборот). pListNext и pListLast — указатели не следующий и предыдущий бакеты в пределах всей хеш-таблицы, в том порядке, в котором элементы были добавлены (в примере выше, a ссылается на b, b на c и наоборот). Таким образом, доступны операции обхода связанного списка в обе стороны как среди элементов с одинаковым хешем, так и среди всей хеш-таблицы.

Структура хеш-таблиц и бакетов

Для реализации хеш-таблиц PHP использует 2 структуры, которые могут быть найдены в файле zend_hash.h. Рассмотрим сначала структуру Bucket:

typedef struct bucket {
    ulong h;
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    char *arKey;
} Bucket;

Вы уже знаете для чего нужны указатели pNext, pLast, pListNext и pListLast. Давайте быстро пройдемся по другим членам-данных:

h хранит хеш ключа. Если ключ это целое число, то h будет равен этому числу (для целочисленных ключей хеш-функция не делает ничего) и nKeyLength будет равен 0. Для строковых ключей h будет содержать результат работы функции zend_hash_func(), arKey будет содержать ключ и nKeyLength его длину.

pData это указатель на хранимое значение. Хранимое значение будет не тем же самым значением, что передано в функцию вставки, а его копией (память под эту копию будет выделана отдельно от бакета). Такой подход неэффективен если хранимым значением является указатель, по этому PHP в такой ситуации применяет небольшой трюк: вместо того чтобы сохранить указатель в отдельной области памяти PHP кладет его в член-данных pDataPtr. А pData в такой ситуации указывает на pDataPtr (pData = &pDataPtr).

Другими словами, если в массив добавляется новое значение, то это значение копируется и указатель на скопированное значение кладется в pData. Если в массив добавляется не значение, а указатель на значение, то нет смысла копировать этот указатель в отдельную область памяти (у нас получится два разных указателя на одно и то же значение), вместо этого указатель кладется в pDataPtr, а pData указывает на pDataPtr.

Теперь давайте взглянем на структуру хеш-таблицы:

typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets;
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

Вы уже знаете, что arBuckets это массив C, содержащий связанные списки бакетов. Этот массив упорядочен по хешу ключей массива. Массивы PHP имеют нефиксированный размер, поэтому размер arBuckets должен быть динамически изменен когда число элементов в таблице (nNumOfElements) достигнет предела выделенной под arBucket памяти (nTableSize). Мы могли бы хранить в хеш-таблице больше значений, чем nTableSize, но это увеличило бы число коллизий и сказалось бы отрицательно на производительности.

nTableSize всегда имеет значение кратное степеням 2, то есть, например, если в вашей хеш-таблице находится 12 элементов, то её реальный размер будет равен 16. Учтите, что несмотря на то что массив arBuckets при необходимости автоматически увеличивается, он не будет уменьшен при удалении элементов. То есть если вы вставите в хеш-таблицу 1000000 элементов, а потом удалите их все, то nTableSize будет иметь значение 1048576.

Результат работы хеш-функции имеет тип ulong, но размер nTableSize обычно намного меньше этого значения. По этому хеш не может быть напрямую использован в качестве ключей массива arBuckets. Вместо хеша в качестве индекса используется значение nIndex = h % nTableSize. Так как размер таблицы всегда кратен степеням двойки, то это выражение эквивалентно nIndex = h & (nTableSize - 1). Для того чтобы понять почему это так давайте посмотрим как nTableSize - 1 меняет значение:

nTableSize     = 128 = 0b00000000.00000000.00000000.10000000
nTableSize - 1 = 127 = 0b00000000.00000000.00000000.01111111

В TableSize - 1 все биты ниже размера таблицы установлены в 1. Это позволяет с помощью h & (nTableSize - 1) оставить только те биты хеша, что ниже чем nTableSize, что аналогично операции h % nTableSize.

Значение nTableSize - 1 называется маской таблицы и хранится в члене-данных nTableMask. Маски используются вместо операций с делением по модулю только для оптимизации производительности.

Член-данных nNextFreeElement определяет следующий целочисленный ключ, который будет использован когда вы вставите в массив новый элемент с помощью $array[] = $value. Он будет на единицу больше чем предыдущий ключ перед этим использованный в хеш-таблице.

Вы уже знаете для чего используются указатели pListHead и pListTail (они указывают на начало и конец двойного связанного списка определяющего порядок элементов в хеш-таблице). Указатель pInternalPointer нужен для итерирования и указывает на "текущий" бакет.

Когда элемент удаляется из хеш-таблицы, может быть вызван деструктор для этого элемента, этот деструктор хранится в члене-данных pDestructor. Например, если вы храните в хеш-таблице элементы zval *, то, вероятно, вы захотите вызвать zval_ptr_dtor при удалении этих элементов.

Флаг persistent определяет должны ли бакеты (и их значения) использовать persistent allocation. Для большинства случаев флаг должен иметь значение 0 так как хеш-таблица не должна иметь время жизни большее чем один запрос. Флаг bApplyProtection определяет должна ли хеш-таблица иметь защиту от рекурсии (по умолчанию 1). Защита от рекурсии выдаст ошибку если будет достигнута максимальная глубина рекурсии (хранится в nApplyCount). Защита используется для сравнения хеш-таблиц и для функций zend_hash_apply.

И последний член-данных inconsistent используется только для дебага и хранит информацию о текущем состоянии хеш-таблицы. Он используется для выдачи ошибок при некорректном использовании хеш-таблицы, наример если вы обращаетесь к хеш-таблице, находящейся в процессе уничтожения.