Подробно объясните базовую реализацию массивов PHP: HashTable

предисловие

Массивы в PHP — это мощный и гибкий тип данных. Прежде чем объяснять его базовую реализацию, давайте взглянем на его важные функции в реальном использовании:

// 可以使用数字下标的形式定义数组
$arr= ['Mike', 2 => 'JoJo'];
echo $arr[0], $arr[2];

// 也可以使用字符串下标定义数组
$arr = ['name' => 'Mike', 'age' => 22];

// 可以顺序读取数组中的数据
foreach ($arr as $key => $value) {
    // Do Something
}
echo current($arr);
echo next($arr);

// 也可以随机读取数组中的数据
$arr = ['name' => 'Mike', 'age' => 22];
echo $arr['name'];

// 数组的长度是可变的
$arr = [1, 2, 3];
$arr[] = 4;
array_push($arr, 5);

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

структура данных

Стренд в PHP на самом деле является упорядоченным отображением. Отображение - это тип, связанный со значениями к ключам. ——Руководство по PHP

В PHP это сопоставление выполняется с помощью散列表（HashTable）Реализовано, на языке C доступ к элементам массива возможен только через числовые индексы, а через HashTable мы можем использоватьString KeyДоступ к элементам массива в виде индексов. Проще говоря, HashTable проходит映射函数Преобразуйте строковый ключ в обычный числовой индекс и сохраните соответствующее значение Value в элементе массива, соответствующем индексу.

HashTable в PHP предоставляетсяzend_arrayОпределено, его структура данных выглядит следующим образом:

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    reserve)
        } v;
        uint32_t flags;           /* 通过 32 个可用标识，设置散列表的属性 */
    } u;
    uint32_t     nTableMask;       /* 值为 nTableSize 的负数 */
    Bucket      *arData;           /* 用来储存数据 */
    uint32_t     nNumUsed;         /* arData 中的已用空间大小 */
    uint32_t     nNumOfElements;   /* 数组中的元素个数 */
    uint32_t     nTableSize;       /* 数组大小，总是 2 幂次方 */
    uint32_t     nInternalPointer; /* 下一个数据元素的指针，用于迭代（foreach） */
    zend_long    nNextFreeElement; /* 下一个可用的数值索引 */
    dtor_func_t  pDestructor;      /* 数据析构函数（句柄） */
};

в этой структуреBucketТо есть массив, хранящий элементы,arDataЧтобы указать на начало массива, используйте映射函数После сопоставления значения ключа вы можете получитьзначение смещения,пройти черезНачальная позиция памяти + значение смещенияЗатем вы можете выполнять операции адресации в хеш-таблице. Структура данных Bucket выглядит следующим образом:

typedef struct _Bucket {
    zval              val; /* 值 */
    zend_ulong        h;   /* 使用 time 33 算法对 key 进行计算后得到的哈希值（或为数字索引）   */
    zend_string      *key; /* 当 key 值为字符串时，指向该字符串对应的 zend_string（使用数字索引时该值为 NULL） */
} Bucket;

Базовая реализация

Хеш-таблица в основном состоит измассив для хранения элементов(ковш) ихэш-функцияСостоит из двух частей.

случайное чтение

при указанииKey-ValueПри отображении отношения, если ключ имеет тип String, первый проходTime 33Алгоритм преобразует его в целое число типа Int, а затем сопоставляет Int с индексом в массиве Bucket с помощью специального алгоритма хэширования в PHP и, наконец, сохраняет значение в элементе, соответствующем индексу. При доступе к массиву через ключ вам нужно только использовать тот же алгоритм для вычисления соответствующего индекса, а затем вынуть значение Value в соответствующем элементе для достиженияслучайное чтение.

последовательное чтение

Как видно из вышеперечисленного, элементы, хранящиеся в Hashtable, неупорядочены, а массив в PHP заказан. Как PHP решает эту проблему?

Чтобы добиться упорядочения HashTable, PHP добавляетПромежуточная таблица сопоставления, таблица представляет собой массив того же размера, что и Bucket.Массив хранит целочисленные данные, которые используются для хранения нижнего индекса значения, фактически сохраненного элементом в Bucekt. Обратите внимание, что после добавления промежуточной таблицы сопоставленияДанные в Bucekt упорядочены, а данные в промежуточной таблице отображения неупорядочены.. Таким образом, при последовательном чтении требуется доступ только к данным в Bucket.

Промежуточная таблица отображения не определяется отдельно в zend_array, а ставится вместе с arData.При инициализации массива выделяется не только память размера ведра, но и данные того же размера пространства, что и промежуточная таблица отображения. Метод реализации выглядит следующим образом:

хэш-функция

Как видно из предыдущего раздела, хэш-функция на самом деле является первойhash codeСопоставьте с промежуточной таблицей сопоставления, а затем промежуточная таблица сопоставления указывает на элемент, в котором фактически хранится значение.

Хэш-код хешируется в PHP следующим образом:

nIndex = key->h | nTableMask;

Поскольку размер хеш-таблицы всегда равен степени 2, хешированное значение будет располагаться между [nTableMask, -1], то есть в промежуточной таблице сопоставления.

Хэш-конфликт

Любая хэш-функция появится проблемы с хэшей, общие решения для хэш-столкновений являются следующие:

открытая адресация
метод цепного адреса
Перефразирование

PHP использует один из链地址法, Строка конфликтующих сегментов в связанный список, чтобы промежуточная таблица сопоставления отображала не элемент, а связанный список сегментов.При нахождении соответствующего связанного списка сегментов с помощью хеш-функции необходимо пройти по связанному списку, сравнить значения ключа одно за другим, а затем найти целевой элемент.

Вставка нового элемента Конфликт хешей делится на следующие два шага:

Храните индекс старого элемента в новый элементnextсередина
Сохраните индекс нового элемента в промежуточной таблице сопоставления.

Видно, что PHP реализует исходную структуру массива Bucket.静态链表, тем самым решая проблему коллизий хэшей.

найти

Процесс поиска в HashTable фактически был описан выше:

использоватьtime 33Ключевой алгоритм для получения значенияhash code
Используйте хэш-функцию для вычисления хеш-кода, чтобы получить значение хеш-функции.nIndex, то есть индекс элемента в промежуточной таблице отображения
Получить индекс элемента в Bucket из промежуточной таблицы сопоставления через nIndexidx
Доступ к соответствующему элементу массива в Bucket через idx, который также является静态链表головной узел
Пройдите по связанному списку, чтобы определить, совпадает ли значение ключа в каждом элементе со значением ключа, которое мы ищем.
Если то же самое, завершить обход

Расширение

В языке C длина массива фиксирована, так что же нам делать, если пространство заполнено и нам нужно продолжить его вставку? Массив PHP реализует механизм автоматического расширения внизу, когда элемент вставлен и нет свободного места, он сработаетАвтоматическое расширениемеханизм, а затем выполнить вставку после расширения.

Следует отметить, что при удалении элемента массива бит флага будет использоваться дляНадгробие, но не удаляет элемент Bucket, который находится сразу, потому что когда-то последние расположены при каждом удалении операции, что приводит к ненужным накладным расходам.

Процесс расширения выглядит следующим образом:

Если доля удаленных элементов достигает порогового значения, удаленные элементы будут удалены.НадгробиеЗатем следующие корзины заполняются вперед свободными корзинами.Поскольку индексы корзин изменились, необходимо изменить фактические значения индексов, хранящиеся в промежуточной таблице сопоставления для каждого элемента.
Если не достигнут阈值, PHP применит новый массив, в два раза превышающий размер исходного массива, и скопирует данные из старого массива в новый массив.Поскольку длина массива изменилась, отношение сопоставления ключ-значение необходимо пересчитать. шаг:перестроить индекс.

Примечание. Поскольку при перестроении индекса необходимо пересчитать отношение сопоставления, при копировании старого массива в новый массив данные в промежуточной таблице сопоставления копировать не нужно.

Суммировать

Массивы в PHP создаются с помощьюHashTableосуществленный
След HashTableмощность 2
Hashtable реализует случайное чтение через отношение сопоставления ключ-значение
HashTable черезПромежуточная таблица сопоставленияРеализовать последовательное чтение, промежуточную таблицу сопоставления и массив элементов (Bucket) использовать непрерывное пространство памяти.
PHP разрешает коллизии хэшей в HashTable с помощью метода адресной цепочки
Когда пространство заполнено, сработает механизм автоматического расширения, в результате чегоперестроить индекс

использованная литература

"Анализ ядра PHP7"
PHP 7 Arrays : HashTables