0x00 Предисловие
Недавно я читал "Анализ ядра PHP" и кое-что узнал о массивах PHP, поэтому написал сводную запись (∩_∩). Поскольку массив PHP является очень мощным и важным типом данных, он поддерживает как простой массив, так и массив пар ключ-значение, где массив пар ключ-значение аналогичен массиву в языке Go.mapНо это также гарантирует, что его можно пройти по порядку, а поскольку используется реализация хэш-таблицы, базовая сложность времени поиска может быть гарантирована равной O (1). Итак, давайте взглянем на базовую реализацию массивов PHP~
0x01 Структура массива
Как выглядит массив в ядре PHP? Из исходного кода PHP мы видим, что его структура выглядит следующим образом:
// 定义结构体别名为 HashTable
typedef struct _zend_array HashTable;
struct _zend_array {
// gc 保存引用计数，内存管理相关；本文不涉及
zend_refcounted_h gc;
// u 储存辅助信息；本文不涉及
union {
struct {
ZEND_ENDIAN_LOHI_4(
zend_uchar flags,
zend_uchar nApplyCount,
zend_uchar nIteratorsCount,
zend_uchar consistency)
} v;
uint32_t flags;
} u;
// 用于散列函数
uint32_t nTableMask;
// arData 指向储存元素的数组第一个 Bucket，Bucket 为统一的数组元素类型
Bucket *arData;
// 已使用 Bucket 数
uint32_t nNumUsed;
// 数组内有效元素个数
uint32_t nNumOfElements;
// 数组总容量
uint32_t nTableSize;
// 内部指针，用于遍历
uint32_t nInternalPointer;
// 下一个可用数字索引
zend_long nNextFreeElement;
// 析构函数
dtor_func_t pDestructor;
};
-
nNumUsedиnNumOfElementsРазница:nNumUsedОтноситсяarDataиспользуется в массивеBucketчисло, потому что массив просто удаляет элементBucketТип соответствующего значения установлен наIS_UNDEF(потому что перемещение и переиндексация массива каждый раз при удалении элемента заняло бы слишком много времени), в то время какnNumOfElementsСоответствует фактическому количеству элементов в массиве. -
nTableSizeЕмкость массива как степень числа 2. Массивы PHP имеют неограниченную длину, но массивы языка C имеют фиксированную длину. Чтобы реализовать функцию массивов неопределенной длины в PHP, принят механизм «расширения», который оценивает каждый раз, когда вставляется элемент.nTableSizeдостаточно для хранения. Если недостаточно, повторно нанесите 2 разаnTableSizeразмер нового массива и скопируйте исходный массив (в настоящее время необходимо очистить тип исходного массива какIS_UNDEFвремя элемента) и переиндексировать. -
nNextFreeElementСохраните следующий доступный числовой индекс, например, в PHP$a[] = 1;Это использование вставит индекс какnNextFreeElementэлементы, тоnNextFreeElementУвеличить на 1.
_zend_arrayЭта структура упоминается здесь первой, функции некоторых членов структуры будут объяснены ниже, так что не нервничайте O(∩_∩)O ха-ха~. Давайте посмотрим на элементы массиваBucketструктура:
typedef struct _Bucket {
// 数组元素的值
zval val;
// key 通过 Time 33 算法计算得到的哈希值或数字索引
zend_ulong h;
// 字符键名，数字索引则为 NULL
zend_string *key;
} Bucket;
0x01 Доступ к массиву
Мы знаем, что массивы PHP реализованы на основе хеш-таблиц, и, в отличие от обычных хэш-таблиц, массивы PHP также реализуют упорядочение элементов, то есть вставляемые элементы являются непрерывными, а не неупорядоченными с точки зрения памяти. упорядочивание PHP использует технологию "таблицы сопоставления". Вот иллюстрация того, как мы получаем доступ к элементам массива PHP :-D.
Примечание. Поскольку имя ключа нижнего индекса таблицы сопоставления было подвергнуто двум хеш-операциям, чтобы отличить хеш от первого хэша, хэш является вторым хэшем.
Как видно из рисунка, таблица отображения и элементы массива находятся в одном и том же фрагменте непрерывной памяти. Таблица отображения представляет собой целочисленный массив той же длины, что и элемент хранения. Ее значение по умолчанию равно -1, а эффективное значениеBucketНижний индекс массива. иHashTable->arDataуказывает на это воспоминаниеBucketПервый элемент массива.
Например$a['key']массив доступа$aимя среднего ключаkeyЧлен , введение процесса: сначала рассчитано по алгоритму Time 33keyХэш-значение, а затем вычислите индекс таблицы сопоставления, соответствующий хэш-значению, с помощью алгоритма хеширования, поскольку значение, хранящееся в таблице сопоставления,BucketЗначение нижнего индекса в массиве, поэтому вы можете получитьBucketсоответствующий элемент массива.
Теперь давайте поговорим об алгоритме хеширования, который представляет собой алгоритм, который сопоставляет хеш-значение имени ключа с индексом «таблицы сопоставления». На самом деле это очень просто с помощью одной строки кода:
nIndex = h | ht->nTableMask;
хэш-значение иnTableMaskВыполните операцию ИЛИ, чтобы получить индекс таблицы сопоставления, гдеnTableMaskЗначениеnTableSizeотрицательное число. и из-заnTableSizeявляется степенью числа 2, поэтомуh | ht->nTableMaskДиапазон значений находится в[-nTableSize, -1]между, только в пределах диапазона нижнего индекса таблицы сопоставления. Что касается того, почему бы не использовать простую операцию «остаток», но пойти на многое, чтобы использовать операцию «побитовое ИЛИ»? Поскольку операция «побитовое ИЛИ» намного быстрее, чем операция «остаток», я думаю, что для такой часто используемой операции оптимизация времени, вызванная более сложной реализацией, того стоит.
хэш-коллизия
Нижние индексы «таблицы сопоставления» хеш-значений разных имен ключей, полученных путем хеширования, могут быть одинаковыми, и в это время происходит коллизия хэшей. В этом случае PHP использует для решения «метод цепочки адресов». На следующем рисунке показан случай доступа к элементу с коллизией хэшей:
Это вроде бы похоже на первую картинку, но мы тоже посещаем$a['key']Процесс имеет еще несколько шагов. Сначала нижний индекс таблицы отображения получается с помощью операции хеширования -2 , а затем осуществляется доступ к таблице отображения, чтобы обнаружить, что ее содержимое указывает наarDataЭлемент с индексом 1 массива. На этом этапе мы устанавливаем элементkeyПо сравнению с именем ключа, к которому нужно получить доступ, обнаруживается, что они не равны, тогда элемент не тот элемент, к которому мы хотим получить доступ, и элементval.u2.nextСохраненное значение — это точно следующий элемент с таким же значением хеш-функции, соответствующимarDataиндекс массива, поэтому мы можем продолжать передаватьnextЗначение проходит до тех пор, пока не будет найден элемент с тем же именем ключа или поиск не завершится неудачно.
0x02 вставить элемент
функция для вставки элементов_zend_hash_add_or_update_i, код на основе PHP 7.2.9 выглядит следующим образом:
static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag ZEND_FILE_LINE_DC)
{
zend_ulong h;
uint32_t nIndex;
uint32_t idx;
Bucket *p;
IS_CONSISTENT(ht);
HT_ASSERT_RC1(ht);
if (UNEXPECTED(!(ht->u.flags & HASH_FLAG_INITIALIZED))) { // 数组未初始化
// 初始化数组
CHECK_INIT(ht, 0);
// 跳转至插入元素段
goto add_to_hash;
} else if (ht->u.flags & HASH_FLAG_PACKED) { // 数组为连续数字索引数组
// 转换为关联数组
zend_hash_packed_to_hash(ht);
} else if ((flag & HASH_ADD_NEW) == 0) { // 添加新元素
// 查找键名对应的元素
p = zend_hash_find_bucket(ht, key);
if (p) { // 若相同键名元素存在
zval *data;
/* 内部 _zend_hash_add API 的逻辑，可以忽略 */
if (flag & HASH_ADD) { // 指定 add 操作
if (!(flag & HASH_UPDATE_INDIRECT)) { // 若不允许更新间接类型变量则直接返回
return NULL;
}
// 确定当前值和新值不同
ZEND_ASSERT(&p->val != pData);
// data 指向原数组成员值
data = &p->val;
if (Z_TYPE_P(data) == IS_INDIRECT) { // 原数组元素变量类型为间接类型
// 取间接变量对应的变量
data = Z_INDIRECT_P(data);
if (Z_TYPE_P(data) != IS_UNDEF) { // 该对应变量存在则直接返回
return NULL;
}
} else { // 非间接类型直接返回
return NULL;
}
/* 一般 PHP 数组更新逻辑 */
} else { // 没有指定 add 操作
// 确定当前值和新值不同
ZEND_ASSERT(&p->val != pData);
// data 指向原数组元素值
data = &p->val;
// 允许更新间接类型变量则 data 指向对应的变量
if ((flag & HASH_UPDATE_INDIRECT) && Z_TYPE_P(data) == IS_INDIRECT) {
data = Z_INDIRECT_P(data);
}
}
if (ht->pDestructor) { // 析构函数存在
// 执行析构函数
ht->pDestructor(data);
}
// 将 pData 的值复制给 data
ZVAL_COPY_VALUE(data, pData);
return data;
}
}
// 如果哈希表已满，则进行扩容
ZEND_HASH_IF_FULL_DO_RESIZE(ht);
add_to_hash:
// 数组已使用 Bucket 数 +1
idx = ht->nNumUsed++;
// 数组有效元素数目 +1
ht->nNumOfElements++;
// 若内部指针无效则指向当前下标
if (ht->nInternalPointer == HT_INVALID_IDX) {
ht->nInternalPointer = idx;
}
zend_hash_iterators_update(ht, HT_INVALID_IDX, idx);
// p 为新元素对应的 Bucket
p = ht->arData + idx;
// 设置键名
p->key = key;
if (!ZSTR_IS_INTERNED(key)) {
zend_string_addref(key);
ht->u.flags &= ~HASH_FLAG_STATIC_KEYS;
zend_string_hash_val(key);
}
// 计算键名的哈希值并赋值给 p
p->h = h = ZSTR_H(key);
// 将 pData 赋值该 Bucket 的 val
ZVAL_COPY_VALUE(&p->val, pData);
// 计算映射表下标
nIndex = h | ht->nTableMask;
// 解决冲突，将原映射表中的内容赋值给新元素变量值的 u2.next 成员
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
// 将映射表中的值设为 idx
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);
return &p->val;
}
0x03 Расширение
Мы упоминали о расширении, когда структурировали массив ранее, и в коде есть такой макрос для вставки элементовZEND_HASH_IF_FULL_DO_RESIZE, этот макрос на самом деле вызываетzend_hash_do_resizeфункция для расширения и переиндексации массива. Примечание: не каждый разBucketКогда массив заполнен, его необходимо расширить.Bucketв массивеIS_UNDEFКоличество элементов составляет большую долю, непосредственноIS_UNDEFЭлементы удаляются и повторно индексируются для экономии памяти. Посмотримzend_hash_do_resizeфункция:
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
IS_CONSISTENT(ht);
HT_ASSERT_RC1(ht);
if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { // IS_UNDEF 元素超过 Bucket 数组的 1/33
// 直接重新索引
zend_hash_rehash(ht);
} else if (ht->nTableSize < HT_MAX_SIZE) { // 数组大小 < 最大限制
void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
// 新的内存大小为原来的两倍，采用加法是因为加法快于乘法
uint32_t nSize = ht->nTableSize + ht->nTableSize;
Bucket *old_buckets = ht->arData;
// 申请新数组内存
new_data = pemalloc(HT_SIZE_EX(nSize, -nSize), ht->u.flags & HASH_FLAG_PERSISTENT);
// 更新数组结构体成员值
ht->nTableSize = nSize;
ht->nTableMask = -ht->nTableSize;
HT_SET_DATA_ADDR(ht, new_data);
// 复制原数组到新数组
memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
// 释放原数组内存
pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT);
// 重新索引
zend_hash_rehash(ht);
} else { // 数组大小超出内存限制
zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%u * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
}
}
Логика переиндексации находится вzend_hash_rehashВ функции код такой:
ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
Bucket *p;
uint32_t nIndex, i;
IS_CONSISTENT(ht);
if (UNEXPECTED(ht->nNumOfElements == 0)) { // 数组为空
if (ht->u.flags & HASH_FLAG_INITIALIZED) { // 已初始化
// 已使用 Bucket 数置 0
ht->nNumUsed = 0;
// 映射表重置
HT_HASH_RESET(ht);
}
// 返回成功
return SUCCESS;
}
// 映射表重置
HT_HASH_RESET(ht);
i = 0;
p = ht->arData;
if (HT_IS_WITHOUT_HOLES(ht)) { // Bucket 数组全部为有效值，没有 IS_UNDEF
// ----------------------------
// 遍历数组，重新设置映射表的值
do {
nIndex = p->h | ht->nTableMask;
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
p++;
} while (++i < ht->nNumUsed);
// ----------------------------
} else {
do {
if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) { // 当前 Bucket 类型为 IS_UNDEF
uint32_t j = i;
Bucket *q = p;
if (EXPECTED(ht->u.v.nIteratorsCount == 0)) {
// 移动数组覆盖 IS_UNDEF 元素
while (++i < ht->nNumUsed) {
p++;
if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
ZVAL_COPY_VALUE(&q->val, &p->val);
q->h = p->h;
nIndex = q->h | ht->nTableMask;
q->key = p->key;
Z_NEXT(q->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
if (UNEXPECTED(ht->nInternalPointer == i)) {
ht->nInternalPointer = j;
}
q++;
j++;
}
}
} else {
uint32_t iter_pos = zend_hash_iterators_lower_pos(ht, 0);
// 移动数组覆盖 IS_UNDEF 元素
while (++i < ht->nNumUsed) {
p++;
if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
ZVAL_COPY_VALUE(&q->val, &p->val);
q->h = p->h;
nIndex = q->h | ht->nTableMask;
q->key = p->key;
Z_NEXT(q->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
if (UNEXPECTED(ht->nInternalPointer == i)) {
ht->nInternalPointer = j;
}
if (UNEXPECTED(i == iter_pos)) {
zend_hash_iterators_update(ht, i, j);
iter_pos = zend_hash_iterators_lower_pos(ht, iter_pos + 1);
}
q++;
j++;
}
}
}
ht->nNumUsed = j;
break;
}
nIndex = p->h | ht->nTableMask;
Z_NEXT(p->val) = HT_HASH(ht, nIndex);
HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
p++;
} while (++i < ht->nNumUsed);
}
return SUCCESS;
}
0x04 Сводка
Ну вот и конец этой статьи, потому что подробно и понятно не объяснить из-за своего уровня. Это самый сложный контент, который я когда-либо писал. После его написания кажется, что я могу понять эту статью сам/(ㄒoㄒ)/~~Потому что написание слишком острое. Я думаю о предложении "Если вы не можете объяснить что-то простым языком, вы на самом деле этого не понимаете". В исходном коде PHP есть много деталей и реализаций, с которыми я не знаком. Эта статья - только начало моего пути. базовое изучение PHP.Я надеюсь, что в будущем я смогу написать хорошую статью, которая будет действительно глубокой, на простом языке.
Также вот хорошая статьяGSM сегодня.GitHub.IO/2018/03/21/…