해시테이블 PHP 소스코드 분석 Zend HashTable 상세 설명 페이지 1/3

HashTable은 일반적인 자료 구조 교과서에서는 해시 테이블(Hash Table) 또는 해시 테이블(Hash Table)이라고도 합니다. 기본 원리는 비교적 간단하지만(익숙하지 않은 경우 데이터 구조 교과서를 참조하거나 온라인으로 검색하세요), PHP 구현에는 고유한 기능이 있습니다. HashTable의 데이터 저장 구조를 이해하는 것은 PHP 소스 코드, 특히 Zend 엔진의 가상 머신 구현을 분석할 때 매우 도움이 됩니다. 이는 우리 두뇌에서 완전한 가상 머신의 이미지를 시뮬레이션하는 데 도움이 됩니다. 이는 또한 배열과 같은 PHP의 다른 데이터 구조 구현을 위한 기초이기도 합니다.
Zend HashTable의 구현은 이중 연결 목록과 벡터(배열)라는 두 가지 데이터 구조의 장점을 결합하고 PHP에 매우 효율적인 데이터 저장 및 쿼리 메커니즘을 제공합니다.
시작해봅시다!
1. HashTable의 데이터 구조
Zend Engine의 HashTable 구현 코드는 주로 zend_hash.h와 zend_hash.c 두 파일로 구성됩니다. Zend HashTable에는 두 가지 주요 데이터 구조가 포함되어 있습니다. 하나는 Bucket 구조이고 다른 하나는 HashTable 구조입니다. Bucket 구조는 데이터를 저장하는 데 사용되는 컨테이너이며 HashTable 구조는 이러한 모든 Bucket(또는 버킷 열)을 관리하는 메커니즘을 제공합니다.

코드 복사 코드는 다음과 같습니다.

typedef struct bucket {
ulong h /* 숫자에 사용됩니다. 인덱싱 */
uint nKeyLength; /* 키 길이*/
void *pData; /* 버킷에 저장된 데이터에 대한 포인터*/
void *pDataPtr; struct bucket * pListNext /* HashTable 버킷 열의 다음 요소를 가리킵니다*/
struct bucket *pListLast /* HashTable 버킷 열의 이전 요소를 가리킵니다*/
struct bucket *pNext; * 동일한 해시 값을 가리킴 버킷 열의 다음 요소*/
struct bucket *pLast /* 동일한 해시 값을 가진 버킷 열의 이전 요소를 가리킴*/
char arKey[1] ; /* 마지막 멤버여야 함, 키 이름*/
} Bucket;

Zend HashTable에서 각 데이터 요소(Bucket)는 고유한 키 이름(key)을 갖습니다. 전체 HashTable을 포함하며 반복할 수 없습니다. HashTable의 데이터 요소는 키 이름을 기반으로 고유하게 결정될 수 있습니다. 키 이름을 나타내는 방법에는 두 가지가 있습니다. 첫 번째 방법은 arKey 문자열을 키 이름으로 사용하고 문자열 길이는 nKeyLength입니다. 위의 데이터 구조에서 arKey는 길이가 1인 문자 배열이지만 키가 한 문자만 될 수 있다는 의미는 아닙니다. 실제로 Bucket은 가변 길이 구조이기 때문에 arKey와 nKeyLength를 결합하면 nKeyLength 길이의 키를 결정할 수 있습니다. 이는 C 언어 프로그래밍의 일반적인 기술입니다. 키 이름을 나타내는 또 다른 방법은 인덱스 메서드입니다. 이 경우 nKeyLength는 항상 0이고 긴 정수 필드 h는 데이터 요소의 키 이름을 나타냅니다. 간단히 말하면 nKeyLength=0이면 키 이름은 h이고, 그렇지 않으면 키 이름은 arKey이고 키 이름의 길이는 nKeyLength입니다.
nKeyLength > 0이라고 해서 이때의 h값이 의미가 없다는 뜻은 아닙니다. 실제로 이때 저장되는 것은 arKey에 해당하는 해시값이다. 해시 함수가 어떻게 설계되든 충돌은 불가피합니다. 즉, 서로 다른 arKeys가 동일한 해시 값을 가질 수 있음을 의미합니다. 동일한 해시 값을 갖는 버킷은 HashTable의 arBuckets 배열에서 동일한 인덱스에 해당하는 버킷 컬럼에 저장됩니다(아래 설명 참조). 이 버킷 컬럼은 이중 연결 리스트이며, 순방향 요소와 역방향 요소는 각각 pLast와 pNext로 표시됩니다. 새로 삽입된 Bucket은 버킷 컬럼의 앞쪽에 배치됩니다.
버킷에서는 pData 포인터가 가리키는 메모리 블록에 실제 데이터가 저장됩니다. 일반적으로 이 메모리 블록은 시스템에 의해 별도로 할당됩니다. 그러나 예외가 있습니다. 즉, Bucket에 저장된 데이터가 포인터인 경우 HashTable은 시스템에 포인터를 저장하기 위한 공간 할당을 요청하지 않고 포인터를 pDataPtr에 직접 저장한 다음 pData가 해당 멤버를 가리킵니다. 이 구조의. 이는 효율성을 향상시키고 메모리 조각화를 줄입니다. 이것으로부터 우리는 PHP HashTable 디자인의 미묘함을 볼 수 있습니다. 버킷의 데이터가 포인터가 아닌 경우 pDataPtr은 NULL입니다.
HashTable의 모든 버킷은 pListNext와 pListLast를 통해 이중 연결 목록을 구성합니다. 가장 최근에 삽입된 버킷은 이 이중 연결 목록의 끝에 배치됩니다.
일반적으로 Bucket은 저장하는 데이터의 크기에 대한 정보를 제공할 수 없습니다. 따라서 PHP 구현 시 Bucket에 저장된 데이터는 자체 크기를 관리할 수 있는 기능을 가지고 있어야 합니다.

코드 복사 코드는 다음과 같습니다.

typedef struct _hashtable {
uint nTableSize
uint nTableMask; ;
uint nNumOfElements;
Bucket *pListHead;
unsigned char nApplyCount; >#if ZEND_DEBUG
int inconsistency;
#endif
} HashTable



현재 페이지 1/3 123다음 페이지

위 내용은 해시테이블 내용을 포함하여 Zend HashTable 상세 설명 페이지 1/3에 해시테이블 PHP 소스코드 분석을 소개하고 있으니, PHP 튜토리얼에 관심 있는 친구들에게 도움이 되었으면 좋겠습니다.