Массив является наиболее часто используемым типом данных в PHPer, а PHP прост в использовании и обладает преимуществами мощного массива, но как массив реализован в PHP?
Прежде всего, давайте сначала разберемся с соответствующей структурой данных и заложим основу для следующего контента.
хеш-таблица
哈希表, как следует из названия, представляет собой структуру данных, которая сопоставляет разные ключевые слова с разными единицами измерения. Метод сопоставления разных ключевых слов с разными единицами называется哈希函数
В идеале после обработки хэш-функции ключевые слова и единицы будут находиться во взаимно однозначном соответствии, но если значений ключевых слов достаточно, можно легко сопоставить несколько ключевых слов с одной и той же единицей, т. е.哈希冲突
решение для хэш-коллизий, либо используйте链接法или используйте开放寻址法
метод ссылки
То есть, когда разные ключевые слова сопоставляются с одним и тем же блоком, используйте связанный список для хранения этих ключевых слов в одном блоке.
открытая адресация
То есть при вставке данных, если обнаруживается, что в блоке, с которым сопоставлено ключевое слово, есть данные, это означает, что произошел конфликт, и поиск следующего блока продолжается до тех пор, пока не будет найден доступный блок.
Однако, поскольку открытая схема адресации относится к местоположению, которое занимает другие единицы сопоставления ключей, последующие ключи более подвержены конфликтам хэшей и, следовательно, склонны к снижению производительности.
связанный список
Поскольку связанный список упоминался выше, здесь мы кратко поговорим об основах связанного списка. Существует много типов связанных списков.Обычные структуры данных включают в себя: очереди, стеки, двусвязные списки и т. д.
Связанный список — это структура данных, состоящая из различных узлов связанного списка. Узлы связанного списка обычно состоят из元素+指向下一节点的指针сочинение. Двусвязный список, как следует из названия, состоит из指向上一节点的指针+元素+指向下一节点的指针сочинение
Что касается содержания структуры данных, мы не будем слишком расширять его, у нас будет специальный контент, чтобы подробно представить структуру данных позже.
php-массив
Способ, которым php решает коллизии хешей, заключается в использовании метода цепочки, поэтому массив php состоит из哈希表+链表понял, если быть точным,哈希表+双向链表выполнить
Внутренняя структура - хеш-таблица
Структура HashTable в основном используется для хранения основной информации хеш-таблицы.
typedef struct _hashtable {
uint nTableSize; // hash Bucket的大小，即哈希表的容量，最小为8，以2x增长。
uint nTableMask; // nTableSize-1 ， 索引取值的优化
uint nNumOfElements; // hash Bucket中当前存在的元素个数，count()函数会直接返回此值
ulong nNextFreeElement; // 下一个可使用的数字键值
Bucket *pInternalPointer; // 当前遍历的指针（foreach比for快的原因之一）
Bucket *pListHead; // 存储整个哈希表的头元素指针
Bucket *pListTail; // 存储整个哈希表的尾元素指针
Bucket **arBuckets; // 存储hash数组
dtor_func_t pDestructor; // 在删除元素时执行的回调函数，用于资源的释放
zend_bool persistent; //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
Структура сегмента используется для сохранения определенного содержимого данных.
typedef struct bucket {
ulong h; // 对char *key进行hash后的值，或者是用户指定的数字索引值
uint nKeyLength; // hash关键字的长度，如果数组索引为数字，此值为0
void *pData; // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
void *pDataPtr; // 如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
struct bucket *pListNext; // 指向整个哈希表的该单元的下一个元素
struct bucket *pListLast; // 指向整个哈希表的该单元的上一个元素
struct bucket *pNext; // 指向由于哈希冲突导致存放在同一个单元的链表中的下一个元素
struct bucket *pLast; // 指向由于哈希冲突导致存放在同一个单元的链表中的上一个元素
// 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
char arKey[1];
} Bucket;
Структура Bucket имеет элемент pData, указывающий на пользовательские данные, который на самом деле указывает на переменную структуру zval, которую мы представили ранее, поэтому при создании массива появляется переменный контейнер с элементом массива + 1. Если вы не понимаете основных знаний о переменных, ознакомьтесь с моей предыдущей статьей:
Переменные базового принципа php (1)
Переменные базового принципа php (2)
Схема внутренней структуры хеш-таблицы
Из приведенного выше рисунка видно, что когда Bucket сохраняет данные, в случае конфликта хэшей он сопоставляет несколько ключевых слов со связанным списком, таким образом формируя двусвязный список.
Суммировать
Сегодня мы возьмем массив в качестве точки входа и кратко разберемся с основными структурами данных: хеш-таблицей и связанным списком, а также разберемся с базовой реализацией массива, а именно哈希表+双向链表. На самом деле, как самая важная структура данных в php, хеш-таблица очень полезна. В хеш-таблицах хранится таблица символов переменных, списки функций и т. д. Заинтересованные студенты могут прочитать мои предыдущие статьи, чтобы получить соответствующие знания.