PHP 배열의 기본 구조 소개

이 글은 그룹의 기본 구조에 대한 소개입니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

다음은 PHP 배열의 기본 구조, 삽입, 검색, 재해시 과정입니다.

기본구조 :

struct _zend_array {
    zend_refcounted_h gc;
    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; // 哈希值计算掩码，等于nTableSize的负值(nTableMask = -nTableSize)
    Bucket            *arData;     // 存储元素数组，指向第一个Bucket
    uint32_t          nNumUsed;   // 已用Bucket数
    uint32_t          nNumOfElements; // 哈希表有效元素数 = nNumUsed - num(is_undef)
    uint32_t          nTableSize;   // 哈希表总大小，为2的n次方, 最小为8
    uint32_t          nInternalPointer;  // 怀疑是内部指针
    zend_long         nNextFreeElement; // 下一个可用的数值索引 arr[] = 1;arr["a"] = 2;arr[] = 3;  则nNextFreeElement = 2;
    dtor_func_t       pDestructor;
};

typedef struct _Bucket {
    zval              val;  // 存储的具体value
    zend_ulong        h;    // hash value (or numeric index)  
    zend_string      *key;  // string key or NULL for numerics
} Bucket;

설명 :

배열이 저장되면 순서대로 값을 먼저 저장하세요 , 값의 위치를 ​​저장합니다.

기록을 저장하는 배열을 해시 테이블이라고 합니다. 이 배열은 값을 저장하는 데 사용되며, 해당 값은 해시를 계산하여 얻은 idx에 저장됩니다. 키 모듈로 nTableMask의 것입니다.

배열이 초기화될 때 최소 크기는 8, 즉 16, 32, 64입니다. . .

배열 초기화 시 생성된 idx 영역은 모두 -1로 초기화되며, 재해시 시에도 -1로 초기화됩니다.

배열에서 요소가 삭제되면 삭제된 요소의 유형은 is_undef로 표시되고 nNumOfEmelment - 1. 해당 요소가 마지막 요소인 경우 nNumUsed - 1입니다.

Insert:

$arr = ['a'=>1, 'b'=>2]를 예로 들어 보겠습니다. :

먼저 1을 배열에 넣고(val.u2.next = -1), 아래 첨자 a에 따라 해시를 계산한 다음, 해시 모듈로 nTableMask를 가져와서 idx를 얻고 앞부분을 저장합니다. idx 위치에 인덱스 nindex 1을 저장합니다.

2를 다시 저장하면 val.u2.next = -1입니다. b 모듈로 nTableMask를 기반으로 계산된 해시에 이미 idx에 값이 있는 경우 해시 충돌이 발생했음을 의미합니다. 이때 현재 idx에 있는 값을 꺼내서 현재 val.u2.next에 저장하고, index nindex 2를 현재 idx에 저장하는 식이다.

Find:

아래 첨자 a를 기반으로 해시를 계산하고, 모듈로 nTableMask를 사용하여 idx를 얻고, idx에서 nindex 값을 얻은 다음 이동합니다. arData 검색에서 찾은 위치의 키가 != a이면 찾을 수 없습니다. 찾은 위치의 키가 == a이면 해당 u2.next를 확인하고 -1이면 찾은 것입니다. 삽입 프로세스 중에 해시 충돌이 발생했음을 나타내는 -1이 아닌 경우 찾을 때까지 u2.next에 따라 arData에서 계속 검색합니다.

rehash:

rehash일 때 먼저 nindex 영역의 모든 레코드를 -1로 재설정한 다음 첫 번째 요소부터 시작합니다. 포인터 *p. 요소가 is_undef로 표시되지 않은 경우 요소의 키 해시를 다시 계산하여 nindex에 넣은 다음 p++를 반복합니다. 요소가 is_undef로 표시되면 계속해서 포인터 p++를 이동하고 새 포인터 j가 해당 위치를 가리키도록 설정합니다. 루프를 계속하면서 p가 이동할 때마다 is_undef가 아닌 요소를 하나씩 앞으로 이동합니다. , j는 is_undef를 발견합니다. 값이 할당될 때까지 이동하지 않습니다. 마지막 nNunUsed까지 끝까지 이동한 후 nNunUsed에 j를 할당하고 이 위치부터 요소를 삽입하면 이전 요소를 직접 덮어쓰게 됩니다.

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