PHP 배열 구현 원리

배열은 PHP에서 가장 일반적으로 사용되는 데이터 유형입니다. 동시에 PHP는 강력한 배열로 인해 사용하기 쉽지만 PHP에서 배열은 어떻게 구현됩니까? ?

추천 튜토리얼: PHP 비디오 튜토리얼

우선, 우리는 여전히 먼저 관련 데이터 구조를 이해하고 다음 콘텐츠에 대한 견고한 기반을 마련합니다

해시 테이블

#🎜🎜 # 해시 테이블은 이름에서 알 수 있듯이 서로 다른 키워드를 서로 다른 단위로 매핑하는 데이터 구조입니다. 서로 다른 키워드를 서로 다른 단위로 매핑하는 방법을 해시 함수라고 합니다

이상적으로는 해시 함수로 처리한 후 키워드와 단위가 일대일로 대응됩니다. 값이 충분하면 여러 키워드가 동일한 단위에 매핑되기 쉽습니다. 즉, 해시 충돌에 대한 해결책은 연결 방법을 사용하거나 주소 방법을 공개하는 것입니다

#🎜🎜. #

링크 방법

즉, 서로 다른 키워드가 동일한 단위에 매핑되는 경우 연결 리스트를 사용하여 이러한 키워드를 동일한 단위에 저장합니다#🎜🎜 #

#🎜 🎜#오픈 어드레싱 방식 즉, 데이터를 삽입할 때 해당 키워드가 매핑된 단위에 데이터가 있는 것으로 확인되면 충돌이 발생한 것을 의미하며 이후 계속해서 사용 가능한 단위를 찾을 때까지 다음 단위를 검색합니다

개방형 주소 지정 체계가 다른 키워드 매핑 단위의 위치를 ​​차지하므로 후속 키워드는 해시 충돌이 발생할 가능성이 더 높으므로 성능이 저하되기 쉽습니다. 저하# 🎜🎜#

Linked list

위에서 Linked list가 언급되었으므로 여기서는 의 기본 사항에 대해 간략하게 설명합니다. 연결된 목록. 연결 목록은 여러 유형으로 구분됩니다. 일반적으로 사용되는 데이터 구조에는 큐, 스택, 양방향 연결 목록 등이 있습니다.

연결 목록은 서로 다른 연결 목록 노드로 구성된 데이터 구조입니다. 연결된 목록 노드는 일반적으로 요소 + 다음 노드에 대한 포인터로 구성됩니다. 이중 연결 리스트는 이름에서 알 수 있듯이 이전 노드에 대한 포인터 + 요소 + 다음 노드에 대한 포인터로 구성됩니다. 데이터 구조의 내용을 너무 많이 확장하지는 않겠습니다. , 추후에 전용 포스팅을 준비하겠습니다. 컨텐츠에서 데이터 구조에 대해 자세히 소개하겠습니다

php array

#🎜🎜 # PHP에서 해시 충돌을 해결하는 방식은 Linking 방식을 사용하므로 PHP 배열은 해시 테이블 + 연결 리스트, 정확히 말하면 해시 테이블 + 이중 연결 리스트로 구현됩니다.

내부 구조-해시 테이블해시 테이블 구조는 주로 해시 테이블의 기본 정보를 저장하는 데 사용됩니다

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;

# 🎜 🎜#Bucket 구조는 데이터의 특정 내용을 저장하는 데 사용됩니다

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에서 가장 중요한 데이터 구조이며 다양한 용도로 사용됩니다. 변수 기호 테이블, 함수 목록 등은 모두 해시 테이블을 사용하여 저장됩니다

위 내용은 PHP 배열 구현 원리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!