찾다
백엔드 개발PHP 튜토리얼 详解PHP中Array构造HashTable

详解PHP中Array结构HashTable

我们知道PHP中的Array在内部是以Hash的结构进行存储的。本文主要重点也是对PHP中Array的静态结构和动态结构进行分析和记录。

这里的静态结构,是指存储PHP中Array数据时使用的数据结构,即所谓的HashTable。

动态结构,是指程序在运行过程中,Array数据的存储状态。

?

首先PHP中的hashTable的结构如下:

typedef struct bucket {
    ulong h;                        /* Used for numeric indexing */
    uint nKeyLength;
    void *pData;
    void *pDataPtr;
    struct bucket *pListNext;
    struct bucket *pListLast;
    struct bucket *pNext;
    struct bucket *pLast;
    char *arKey;
} Bucket;


typedef struct _hashtable {
    uint nTableSize;
    uint nTableMask;
    uint nNumOfElements;
    ulong nNextFreeElement;
    Bucket *pInternalPointer;   /* Used for element traversal */
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets; ? ? ? ? ?
    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount;
    zend_bool bApplyProtection;
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

?

一个PHP中的Array在内部对应一个HashTable,HashTable内部的四个Bucket类型的指针数据记录着数组实际存储的元素内容的地址。具体的内容,各字段名都可以自解释,不做多说明了。

?

?

如果只看这几行代码,可能无法理解PHP数组实际的工作原理,接下来,我们可以手工模拟一下PHP数组中的一些最简单的操作。

?

1. 从无到有

HashTable的初始化,首先需要给一个HashTable构造一个内存空间,具体代码如下:

?

//hash_func_t在函数内用不到,hash函数在PHP范围内都是固定的
int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
    uint i = 3;

    SET_INCONSISTENT(HT_OK);

    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        while ((1U nTableSize = 1 nTableMask = 0; /* 0 means that ht->arBuckets is uninitialized */
    ht->pDestructor = pDestructor;
    ht->arBuckets = (Bucket**)&uninitialized_bucket; ? //实际的数据存储空间还未创建
    ht->pListHead = NULL;
    ht->pListTail = NULL;
    ht->nNumOfElements = 0; ? ? ? ? ? ? ? ? ? //表示数组内还没有一个元素,
    ht->nNextFreeElement = 0;
    ht->pInternalPointer = NULL;
    ht->persistent = persistent;
    ht->nApplyCount = 0;
    ht->bApplyProtection = 1;
    return SUCCESS;
}
?

上述代码可以理解为,为数组构造了一个总的大门,数据都可以经由这个门进入到自己对应的内存块中。当然现在门里还没有“座位”呢。

?

2. 数据插入

对于一个一无所有的空间,怎么给它加点东西呢?这就是数据的插入,即数据是如何保存到这个HashTable中的。

PHP的数组索引可以是数值或字符串,我们首先看字符串的索引如何存储,代码如下:

int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
	ulong h;
	uint nIndex;
	Bucket *p;

	IS_CONSISTENT(ht);

	if (nKeyLength nTableMask;

	p = ht->arBuckets[nIndex];
	while (p != NULL) {
		if (p->arKey == arKey ||
			((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
				if (flag & HASH_ADD) {
					return FAILURE;
				}
				HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
				if (p->pData == pData) {
					ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
					HANDLE_UNBLOCK_INTERRUPTIONS();
					return FAILURE;
				}
#endif
				if (ht->pDestructor) {
					ht->pDestructor(p->pData);
				}
				UPDATE_DATA(ht, p, pData, nDataSize);
				if (pDest) {
					*pDest = p->pData;
				}
				HANDLE_UNBLOCK_INTERRUPTIONS();
				return SUCCESS; ?//更新之后直接退出
		}
		p = p->pNext;
	}
	
	if (IS_INTERNED(arKey)) {
		p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
		if (!p) {
			return FAILURE;
		}
		p->arKey = (char*)arKey;
	} else {
		p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
		if (!p) {
			return FAILURE;
		}
		p->arKey = (char*)(p + 1);
		memcpy(p->arKey, arKey, nKeyLength);
	}
	p->nKeyLength = nKeyLength;
	INIT_DATA(ht, p, pData, nDataSize);
	p->h = h;
	CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
	if (pDest) {
		*pDest = p->pData;
	}

	HANDLE_BLOCK_INTERRUPTIONS();
	CONNECT_TO_GLOBAL_DLLIST(p, ht);
	ht->arBuckets[nIndex] = p;
	HANDLE_UNBLOCK_INTERRUPTIONS();

	ht->nNumOfElements++;
	ZEND_HASH_IF_FULL_DO_RESIZE(ht);		/* If the Hash table is full, resize it */
	return SUCCESS;
}

首先,检查数组空间是否初始化,代码如下:

?

#define CHECK_INIT(ht) do {                                             \
    if (UNEXPECTED((ht)->nTableMask == 0)) {                                \
        (ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent);   \
        (ht)->nTableMask = (ht)->nTableSize - 1;                        \
    }                                                                   \
} while (0)
?

?

然后计算要插入的字符串索引的hash值,并与nTableMask做按位与,得到nindex,这个nIndex就是对应的bucket*在二维数组arBucket**中的偏移量。根据代码逻辑,如果nIndex位置不为空,则说明当前计算得到的hash值之前存在。如果连key也相同并且flag为HASH_ADD则失败,否则就是更新操作。如果是更新操作则不会对现有数组结构有任何影响,更新了对应的值之后直接退出即可。

?

在需要有新元素插入到HashTable时,构造好的新元素会经过两步来链入该HashTable

?

第一步代码如下:

?

#define CONNECT_TO_BUCKET_DLLIST(element, list_head)        \
    (element)->pNext = (list_head);                         \
    (element)->pLast = NULL;                                \
    if ((element)->pNext) {                                 \
        (element)->pNext->pLast = (element);                \
    }

?

在这一步中如果新元素的key的hash值之前存在过,则list_head为HashTable.arBucket[nIndex],nIndex怎么来的前面已经说过了。在这一步过后会将HashTable.arBucket[nIndex]赋值为当前的新元素,你懂得。

?

如果新元素的key对应的hash之前没有存在过,则list_head就为NULL,因为HashTable.arBucket[nIndex]为NULL。你也懂得。

?

第二步代码如下:

?

#define CONNECT_TO_GLOBAL_DLLIST(element, ht)               \
    (element)->pListLast = (ht)->pListTail;                 \
    (ht)->pListTail = (element);                            \
    (element)->pListNext = NULL;                            \
    if ((element)->pListLast != NULL) {                     \
        (element)->pListLast->pListNext = (element);        \
    }                                                       \
    if (!(ht)->pListHead) {                                 \
        (ht)->pListHead = (element);                        \
    }                                                       \
    if ((ht)->pInternalPointer == NULL) {                   \
        (ht)->pInternalPointer = (element);                 \
    }
?

关于这一步会对HashTable的内容有什么样的影响,请参看下面的动态示例。相信你也懂得。

?

?

?

动态示例:

现在我们假设数组中没有任何元素,则进行插入操作。现在我们按照代码的逻辑,手动模拟一下数据插入的过程:

?

1.

插入第一个元素A,假设其key对应的hash值为1

则插入之后,内存中的状态如下:

?

HashTable.arBucket[1]=A;

HashTable.pListHead = A

HashTable.pListTail = A

HashTable.pInternalPointer = A

A.pNext = null

A.pLast = null

A.pListLast = null

A.pListNext = null

?

2.

插入第二个元素B,假设其key对应的hash值为2

则插入之后内存的状态如下:

HashTable.arBucket[2] = B;

HashTable.pListHead = A

HashTable.pListTail = B

HashTable.pInternalPointer = A?????? //这个只在第一次的时候设置

A.pNext=null

A.pLast = null

A.pListNext = B

A.pListLast = null

B.pListLast = A

B.pListNext = null

B.pNext = null

B.pLast = null

?

3.

插入第三个元素C,假设其key的hash值为1,和A相同

则插入之后内存状态如下:

HashTable.arBucket[1] = C;

HashTable.pListHead = A

HashTable.pListTail =C

HashTable.pInternalPointer = A?????? //这个只在第一次的时候设置

A.pNext=null

A.pLast = C

A.pListNext = B

A.pListLast = null

?

B.pNext = null

B.pLast = null

B.pListLast = A

B.pListNext = C

C.pNext = A

C.pLast = null

C.pListNext = null

C.pListLast = B

?

插入A,B,C三个值之后的内存中状态即为:

HashTable.arBucket[1] = C;

HashTable.pListHead = A

HashTable.pListTail =C

HashTable.pInternalPointer = A

A.pNext=null

A.pLast = C

A.pListNext = B

A.pListLast = null

?

B.pNext = null

B.pLast = null

B.pListLast = A

B.pListNext = C

C.pNext = A

C.pLast = null

C.pListNext = null

C.pListLast = B

?

OK,A、B、C三个元素都已插入了,现在我们要实现两个任务:

?

1.

查找某key的元素值(value):

如果我们要访问A元素,则提供A的key:key_a,得到对应的hash值为1

然后找HastTable.arBucket[1]。这时HastTable.arBucket[1]其实为C不是A,但由于C的key不等于A的key,因此,要沿着pNext的指针找下去,直到NULL,而此时C.pNext就是A,即找到了key_a对应的值A。

总之由key查找一个元素时,首先要hash,然后顺着hash后的索引位置的pNext指针一直找下去,直到NULL,如果遇到了和要查找的key相同的值,则找到,否则找不到。

?

2.

遍历数组:

由于我们的例子中的key是字符串类型的,全部循环遍历不能用for。只能用foreach,那foreach的遍历是如何实现的呢?

?

简单,根据最后的HashTable的状态,我们从HastTable.pListHead开始沿着pListNext指针顺序找下去即可了。以本文例子为例,则结果为:

?

?

HashTable.pListHead====>A

A.pListNext?????????????????? ====>B

B.pListNext?????????????????? ====>C

?

则最后的遍历顺序就是A,B,C,发现foreach的遍历顺序是和元素插入到数组的顺序相关的。

?

?

如果插入的元素的key不是字符串,而是数值。则可以省去做计算hash值这一步,直接拿数值的key做为hash值使用。

这样就不存在hash冲突的问题,这样也就不会用到每个元素的pNext、pLast两个指针了,这两个指针都只会是NULL。

?

这样我们可以通过使用for循环来遍历数组了,因为不存在hash冲突。

?

同样,如果我们使用foreach来遍历数组的话,遍历顺序还是元素的插入顺序,这个你当然懂得。

?

?

ps:

本文并未对zend中的hash结够做全面的记录,只是对本文主题涉及到的逻辑的重点代码进行了分析和演示。同时也为了能抓住重点。有些代码并未列出,如:再hash的逻辑,和索引为数值类型数据的代码等。这些可在代码文件Zend/zend_hash.c中找到详细内容。

?

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
세션과 관련된 크로스 사이트 스크립팅 (XSS) 공격으로부터 어떻게 보호 할 수 있습니까?세션과 관련된 크로스 사이트 스크립팅 (XSS) 공격으로부터 어떻게 보호 할 수 있습니까?Apr 23, 2025 am 12:16 AM

세션 관련 XSS 공격으로부터 응용 프로그램을 보호하려면 다음 조치가 필요합니다. 1. 세션 쿠키를 보호하기 위해 Httponly 및 Secure 플래그를 설정하십시오. 2. 모든 사용자 입력에 대한 내보내기 코드. 3. 스크립트 소스를 제한하기 위해 컨텐츠 보안 정책 (CSP)을 구현하십시오. 이러한 정책을 통해 세션 관련 XSS 공격을 효과적으로 보호 할 수 있으며 사용자 데이터가 보장 될 수 있습니다.

PHP 세션 성능을 어떻게 최적화 할 수 있습니까?PHP 세션 성능을 어떻게 최적화 할 수 있습니까?Apr 23, 2025 am 12:13 AM

PHP 세션 성능을 최적화하는 방법 : 1. 지연 세션 시작, 2. 데이터베이스를 사용하여 세션을 저장, 3. 세션 데이터 압축, 4. 세션 수명주기 관리 및 5. 세션 공유 구현. 이러한 전략은 높은 동시성 환경에서 응용의 효율성을 크게 향상시킬 수 있습니다.

SESSION.GC_MAXLIFETIME 구성 설정은 무엇입니까?SESSION.GC_MAXLIFETIME 구성 설정은 무엇입니까?Apr 23, 2025 am 12:10 AM

THESESSION.GC_MAXLIFETIMESETTINGINSTTINGTINGSTINGTERMINESTERMINESTERSTINGSESSIONDATA, SETINSECONDS.1) IT'SCONFIGUDEDINPHP.INIORVIAINI_SET ()

PHP에서 세션 이름을 어떻게 구성합니까?PHP에서 세션 이름을 어떻게 구성합니까?Apr 23, 2025 am 12:08 AM

PHP에서는 Session_Name () 함수를 사용하여 세션 이름을 구성 할 수 있습니다. 특정 단계는 다음과 같습니다. 1. Session_Name () 함수를 사용하여 Session_Name ( "my_session")과 같은 세션 이름을 설정하십시오. 2. 세션 이름을 설정 한 후 세션을 시작하여 세션을 시작하십시오. 세션 이름을 구성하면 여러 응용 프로그램 간의 세션 데이터 충돌을 피하고 보안을 향상시킬 수 있지만 세션 이름의 독창성, 보안, 길이 및 설정 타이밍에주의를 기울일 수 있습니다.

세션 ID를 얼마나 자주 재생해야합니까?세션 ID를 얼마나 자주 재생해야합니까?Apr 23, 2025 am 12:03 AM

세션 ID는 로그인시, 민감한 작업 전에 및 30 분마다 정기적으로 재생되어야합니다. 1. 세션 고정 공격을 방지하기 위해 로그인 할 때 세션 ID를 재생합니다. 2. 안전성을 향상시키기 위해 민감한 작업 전에 재생성. 3. 정기적 인 재생은 장기 활용 위험을 줄이지 만 사용자 경험을 평가해야합니다.

PHP에서 세션 쿠키 매개 변수를 어떻게 설정합니까?PHP에서 세션 쿠키 매개 변수를 어떻게 설정합니까?Apr 22, 2025 pm 05:33 PM

Session_SET_COOKIE_PARAMS () 함수를 통해 PHP에서 세션 쿠키 매개 변수 설정을 달성 할 수 있습니다. 1)이 기능을 사용하여 만료 시간, 경로, 도메인 이름, 보안 플래그 등과 같은 매개 변수를 설정하십시오. 2) call session_start ()를 호출하려면 매개 변수를 발효시킵니다. 3) 사용자 로그인 상태와 같은 요구에 따라 매개 변수를 동적으로 조정합니다. 4) 보안을 향상시키기 위해 안전하고 httponly 플래그 설정에주의를 기울이십시오.

PHP에서 세션을 사용하는 주요 목적은 무엇입니까?PHP에서 세션을 사용하는 주요 목적은 무엇입니까?Apr 22, 2025 pm 05:25 PM

PHP에서 세션을 사용하는 주요 목적은 다른 페이지간에 사용자의 상태를 유지하는 것입니다. 1) 세션은 Session_Start () 함수를 통해 시작되어 고유 한 세션 ID를 생성하고 사용자 쿠키에 저장합니다. 2) 세션 데이터는 서버에 저장되므로 로그인 상태 및 쇼핑 카트 컨텐츠와 같은 다른 요청간에 데이터를 전달할 수 있습니다.

하위 도메인에서 세션을 어떻게 공유 할 수 있습니까?하위 도메인에서 세션을 어떻게 공유 할 수 있습니까?Apr 22, 2025 pm 05:21 PM

하위 도메인 간의 세션을 공유하는 방법? 공통 도메인 이름에 대한 세션 쿠키를 설정하여 구현. 1. 세션 쿠키 도메인을 서버 측에서 .example.com으로 설정하십시오. 2. 메모리, 데이터베이스 또는 분산 캐시와 같은 적절한 세션 저장 방법을 선택하십시오. 3. 쿠키를 통해 세션 ID를 전달하면 서버는 ID를 기반으로 세션 데이터를 검색하고 업데이트합니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

안전한 시험 브라우저

안전한 시험 브라우저

안전한 시험 브라우저는 온라인 시험을 안전하게 치르기 위한 보안 브라우저 환경입니다. 이 소프트웨어는 모든 컴퓨터를 안전한 워크스테이션으로 바꿔줍니다. 이는 모든 유틸리티에 대한 액세스를 제어하고 학생들이 승인되지 않은 리소스를 사용하는 것을 방지합니다.

맨티스BT

맨티스BT

Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.

SublimeText3 영어 버전

SublimeText3 영어 버전

권장 사항: Win 버전, 코드 프롬프트 지원!