PHP 배열의 기본 구현 원리는 무엇입니까?

PHP 배열의 기본 구현 원리는 다음과 같습니다. 1. 서로 다른 키워드를 서로 다른 단위에 매핑하는 데이터 구조인 해시 테이블 2. 서로 다른 연결 목록 노드로 구성된 데이터 구조인 연결 목록 해시 충돌을 해결하기 위한 체인 방법.

1. 해시 테이블

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

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

즉, 서로 다른 키워드가 같은 유닛에 매핑되어 있는 경우, 연결 리스트를 사용하여 이러한 키워드를 같은 유닛에 저장하세요

오픈 어드레싱 방식链接法

即当不同的关键字映射到同一单元时，在同一单元内使用链表来保存这些关键字

开放寻址法

즉, 데이터를 삽입할 때 키가 발견되면 데이터가 있습니다 그런 다음 사용 가능한 단위를 찾을 때까지 다음 단위를 계속 검색합니다

그리고 개방형 주소 지정 방식 방식은 다른 키워드 매핑 단위의 위치를 ​​차지하기 때문에 후속 키워드는 해시 충돌 가능성이 높기 때문에 성능 저하가 발생하기 쉽습니다

2. 연결 목록

위에서 연결 목록이 언급되었으므로 여기서는 연결 목록의 기본에 대해 간략하게 설명합니다. 연결 목록은 여러 유형으로 구분됩니다. 일반적으로 사용되는 데이터 구조에는 큐, 스택, 양방향 연결 목록 등이 있습니다. 연결 목록은 서로 다른 연결 목록 노드로 구성된 데이터 구조입니다. 연결된 목록 노드는 일반적으로 요소 + 다음 노드에 대한 포인터로 구성됩니다. 이중 연결 리스트는 이름에서 알 수 있듯이 이전 노드에 대한 포인터 + 요소 + 다음 노드에 대한 포인터로 구성됩니다. 데이터 구조의 내용은 특별히 확장하지 않습니다.

3. PHP 배열

PHP가 해시 충돌을 해결하는 방법은 연결 방식을 사용하므로 PHP 배열은 정확하게는 해시 테이블 + 연결 목록으로 구현됩니다. 해시 테이블 + 이중 연결 목록으로 구현됩니다

4. 내부 구조 - 해시 테이블

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;

관련 학습 권장 사항:

PHP 프로그래밍 입문부터 숙련까지

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