PHP 소스 코드의 HashTable 분석에 대해
这篇文章主要介绍了关于PHP源码中HashTable的解析，有着一定的参考价值，现在分享给大家，有需要的朋友可以参考一下
PHP源码中HashTable的简单示例 前些日子看了那篇对hasttable的介绍，于是也想自己运行一下，可是对于源码的调试不是太在行。 所以想了个办法：自己把PHP源码中的一些简单操作提取出来，自己运行一下，查看输出或调试。 于是花费了三天的空闲时间把一些相关的东西提取出来，主要是Zend目录下的zend_alloc.c,zend_alloc.h,zend_hash.c,zend_hash.h四个文件。 将与PHP相关的内存分配去掉，默认使用系统自带的内存分配方式。 另外：一些注释是http://www.phppan.com/2009/12/zend-hashtable/中所引用文章中的相关信息。 作者地址：http://www.phpinternals.com 下面的代码是一个可以运行的C程序，它初始化一个容量为50的hashtable（实际上分配了64个），然后将30到68，写入hash table，并将这个hash table 打印出来。 相信这会给一些想学习源码的童鞋一些帮助。 源代码如下：
<!-- #include <stdio.h-->#include #include typedef unsigned long ulong;typedef unsigned int uint;typedef unsigned char zend_bool;typedef unsigned int size_t;typedef void (*dtor_func_t)(void *pDest);typedef ulong (*hash_func_t)(char *arKey, uint nKeyLength);#define SUCCESS 0#define FAILURE -1 /* this MUST stay a negative number, or it may affect functions! */ #define HASH_UPDATE (1<<0)#define HASH_ADD (1<<1)#define HASH_NEXT_INSERT(1<<2) #define HASH_DEL_KEY 0 #define perealloc_recoverable(ptr, size, persistent) (__zend_realloc((ptr), (size)))#define pefree_rel(ptr, persistent)(free(ptr))//此处省略了使用PHP的内存分配函数#define pemalloc_rel(size, persistent) (__zend_malloc(size))#define perealloc_rel(ptr, size, persistent) (__zend_realloc((ptr), (size)))#define pemalloc(size, persistent) (__zend_malloc(size))#define pefree(ptr, persistent) (free(ptr)) inline static void * __zend_malloc(size_t len) {
void *tmp = malloc(len);
if (tmp) {
return tmp;
}
fprintf(stderr, "Out of memory\n");
exit(1);}
inline static void * __zend_realloc(void *p, size_t len) {
p = realloc(p, len);
if (p) {
return p;
}
fprintf(stderr, "Out of memory\n");
exit(1);}
typedef struct bucket {
ulong h; /* Used for numeric indexing */
uint nKeyLength; /* key 长度 */
void *pData; /* 指向Bucket中保存的数据的指针 */
void *pDataPtr; /* 指针数据 */
struct bucket *pListNext; /* 指向HashTable桶列中下一个元素 */
struct bucket *pListLast; /* 指向HashTable桶列中前一个元素 */
struct bucket *pNext; /* 指向具有同一个hash值的桶列的后一个元素 */
struct bucket *pLast; /* 指向具有同一个hash值的桶列的前一个元素 */
char arKey[1]; /* 必须是最后一个成员，key名称*/} Bucket;
typedef struct _hashtable {
uint nTableSize;/*指定了HashTable的大小，同时它限定了HashTable中能保存Bucket的最大数量
此 数越大，系统为HashTable分配的内存就越多。为了提高计算效率，
系统自动会将nTableSize调整到最小一个不小于nTableSize的2 的整数次方*/
uint nTableMask;/*nTableMask的值永远是nTableSize – 1，引入这个字段的主要目的是为了提高计算效率*/
uint nNumOfElements;/*记录HashTable当前保存的数据元素的个数*/
ulong nNextFreeElement;/*记录HashTable中下一个可用于插入数据元素的arBuckets的索引*/
Bucket *pInternalPointer;/* Used for element traversal */
Bucket *pListHead;/*Bucket双向链表的第一个元素*/
Bucket *pListTail;/*Bucket双向链表的最后一元素*/
Bucket **arBuckets;/*存储Bucket双向链表*/
dtor_func_t pDestructor;/*函数指针，在HashTable的增加、修改、删除Bucket时自动调用，用于处理相关数据的清理工作*/
zend_bool persistent;/*指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。*/
unsigned char nApplyCount;/*nApplyCount与bApplyProtection结合提供了一个防止在遍历HashTable时进入递归循环时的一种机制*/
zend_bool bApplyProtection;} HashTable;
typedef struct _zend_hash_key {
char *arKey;
uint nKeyLength;
ulong h;} zend_hash_key; typedef zend_bool (*merge_checker_func_t)(HashTable *target_ht, void *source_data, zend_hash_key *hash_key, void *pParam);
#define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
(element)->pNext = (list_head); \
(element)->pLast = NULL; \
if ((element)->pNext) { \
(element)->pNext->pLast = (element); \
} #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); \
} #define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
if ((ht)->nNumOfElements > (ht)->nTableSize) {\
zend_hash_do_resize(ht); \
} int zend_hash_rehash(HashTable *ht) {
Bucket *p;
uint nIndex;
memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
p = ht->pListHead;
while (p != NULL) {
nIndex = p->h & ht->nTableMask;
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
ht->arBuckets[nIndex] = p;
p = p->pListNext;
}
return SUCCESS;} static int zend_hash_do_resize(HashTable *ht) {
Bucket **t; if ((ht->nTableSize << 1) > 0) {/* Let's double the table size */
t = (Bucket **) perealloc_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
if (t) {
ht->arBuckets = t;
ht->nTableSize = (ht->nTableSize << 1);
ht->nTableMask = ht->nTableSize - 1;
zend_hash_rehash(ht);
return SUCCESS;
}
return FAILURE;
}
return SUCCESS;}
#define UPDATE_DATA(ht, p, pData, nDataSize) \
if (nDataSize == sizeof(void*)) { \
if ((p)->pData != &(p)->pDataPtr) { \
pefree_rel((p)->pData, (ht)->persistent); \
} \
memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \
(p)->pData = &(p)->pDataPtr; \
} else { \
if ((p)->pData == &(p)->pDataPtr) { \
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent); \
(p)->pDataPtr=NULL; \
} else { \
(p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);\
/* (p)->pDataPtr is already NULL so no need to initialize it */ \
} \
memcpy((p)->pData, pData, nDataSize); \
} #define INIT_DATA(ht, p, pData, nDataSize); \
if (nDataSize == sizeof(void*)) { \
memcpy(&(p)->pDataPtr, pData, sizeof(void *)); \
(p)->pData = &(p)->pDataPtr; \
} else { \
(p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\
if (!(p)->pData) { \
pefree_rel(p, (ht)->persistent); \
return FAILURE; \
} \
memcpy((p)->pData, pData, nDataSize); \
(p)->pDataPtr=NULL; \
}
static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength) {
register ulong hash = 5381; /* variant with the hash unrolled eight times */
for (; nKeyLength >= 8; nKeyLength -= 8) {
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
}
switch (nKeyLength) {
case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 1: hash = ((hash << 5) + hash) + *arKey++; break;
case 0: break;
}
return hash;}ulong zend_hash_func(char *arKey, uint nKeyLength) {
return zend_inline_hash_func(arKey, nKeyLength);} //省略了int zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor) {
uint i = 3;
Bucket **tmp;
zend_bool persistent = 1;
if (nSize >= 0x80000000) {/* prevent overflow */
ht->nTableSize = 0x80000000;
} else {
while ((1U << i) < nSize) {
i++;
}
ht->nTableSize = 1 << i;
}
ht->nTableMask = ht->nTableSize - 1;
ht->pDestructor = pDestructor;
ht->arBuckets = NULL;
ht->pListHead = NULL;
ht->pListTail = NULL;
ht->nNumOfElements = 0;
ht->nNextFreeElement = 0;
ht->pInternalPointer = NULL;
ht->persistent = persistent;
ht->nApplyCount = 0;
ht->bApplyProtection = 1;
tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
if (!tmp) {
return FAILURE;
}
ht->arBuckets = tmp;
return SUCCESS;} int zend_hash_add_or_update(HashTable *ht, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag) {
ulong h;
uint nIndex;
Bucket *p;
if (nKeyLength <= 0) {
return FAILURE;
}
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex]; while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
if (!memcmp(p->arKey, arKey, nKeyLength)) {
if (flag & HASH_ADD) {
return FAILURE;
} if (ht->pDestructor) {
ht->pDestructor(p->pData);
}
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {
*pDest = p->pData;
}
return SUCCESS;
}
}
p = p->pNext;}
p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);if (!p) {
return FAILURE;}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;}
CONNECT_TO_GLOBAL_DLLIST(p, ht);ht->arBuckets[nIndex] = p;
ht->nNumOfElements++;ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */return SUCCESS;} void zend_hash_destroy(HashTable *ht) {
Bucket *p, *q;
p = ht->pListHead;
while (p != NULL) {
q = p;
p = p->pListNext;
if (ht->pDestructor) {
ht->pDestructor(q->pData);
}
if (q->pData != &q->pDataPtr) {
pefree(q->pData, ht->persistent);
}
pefree(q, ht->persistent);
}
pefree(ht->arBuckets, ht->persistent); }
int zend_hash_find(HashTable *ht, char *arKey, uint nKeyLength, void **pData) {
ulong h;
uint nIndex;
Bucket *p;
h = zend_inline_hash_func(arKey, nKeyLength);
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
if (!memcmp(p->arKey, arKey, nKeyLength)) {
*pData = p->pData;
return SUCCESS;
}
}
p = p->pNext;}return FAILURE;}
void zend_hash_display(HashTable *ht) {
Bucket *p;
uint i;
int flag = 0 ; for (i = 0; i < ht->nTableSize; i++) {
p = ht->arBuckets[i];
flag = 0;
while (p != NULL) {
printf("(%d %s <==> 0x%lX %d) ", i, p->arKey, p->h, p->pNext);
p = p->pNext;
flag = 1;
}
if (flag == 1) {
printf("\n");
} }
p = ht->pListTail;
while (p != NULL) {
printf("%s <==> 0x%lX\n", p->arKey, p->h);
p = p->pListLast;
}}int main() {
int i;
char ch[20];
HashTable ht;
zend_hash_init(&ht, 50, NULL, NULL);
for (i = 30; i < 68; i++) {
sprintf(ch, "%d", i);
ch[strlen(ch) + 1] = '\0';
zend_hash_add_or_update(&ht, ch, strlen(ch) + 1, NULL, 0, NULL, 0);
}
zend_hash_display(&ht);
zend_hash_destroy(&ht);
return 0;}?>以上就是本文的全部内容，希望对大家的学习有所帮助，更多相关内容请关注PHP中文网！
相关推荐：
위 내용은 PHP 소스 코드의 HashTable 분석에 대해의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
핫 AI 도구
Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱
AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.
Undress AI Tool
무료로 이미지를 벗다
Clothoff.io
AI 옷 제거제
AI Hentai Generator
AI Hentai를 무료로 생성하십시오.
인기 기사
뜨거운 도구
메모장++7.3.1
사용하기 쉬운 무료 코드 편집기
SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.
스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경
드림위버 CS6
시각적 웹 개발 도구
SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)
뜨거운 주제
7433
15
1359
52
76
11
29
19
Java에서 Hashtable 클래스의 isEmpty() 메서드를 사용하여 해시 테이블이 비어 있는지 확인
Jul 24, 2023 pm 02:21 PM
Java에서는 Hashtable 클래스의 isEmpty() 메서드를 사용하여 해시 테이블이 비어 있는지 확인합니다. 해시 테이블은 Java 컬렉션 프레임워크에서 일반적으로 사용되는 데이터 구조 중 하나이며 키-값의 저장 및 검색을 구현합니다. 한 쌍. Hashtable 클래스에서는 isEmpty() 메서드를 사용하여 해시 테이블이 비어 있는지 확인합니다. 이 기사에서는 Hashtable 클래스의 isEmpty() 메서드를 사용하는 방법을 소개하고 해당 코드 예제를 제공합니다. 먼저 Hashtable 클래스를 이해해야 합니다. 해시시
PHP 소스 코드 란 무엇입니까?
Oct 11, 2019 am 09:35 AM
PHP 소스 코드는 PHP 소스 코드를 의미하며, 소스 코드는 프로그램과 웹 사이트의 기초이며, "하이퍼텍스트 전처리기"인 PHP는 일반적인 오픈 소스 스크립팅 언어입니다.
Jul 25, 2023 pm 12:00 PM
Java에서는 Hashtable 클래스의 ContainsKey() 메서드를 사용하여 해당 키가 해시 테이블에 있는지 확인합니다. Java 프로그래밍에서는 Hashtable 클래스를 사용하여 해시 테이블을 사용하여 데이터를 저장하고 관리할 수 있습니다. 해시 테이블은 키-값 쌍을 저장하는 데 사용되는 데이터 구조로, 키를 값에 매핑하여 빠른 데이터 액세스를 가능하게 합니다. 실제 프로그래밍 과정에서 해시 테이블에 특정 키가 존재하는지 확인해야 하는 경우가 종종 있습니다. 이 기능을 달성하기 위해 Hashtable 클래스를 사용하여 다음을 제공할 수 있습니다.
PHP 소스 코드 실행 문제: 인덱스 오류 해결 방법
Mar 09, 2024 pm 09:24 PM
PHP 소스 코드 실행 문제: 인덱스 오류 해결에는 특정 코드 예제가 필요합니다. PHP는 동적 웹 사이트 및 웹 애플리케이션을 개발하는 데 자주 사용되는 널리 사용되는 서버 측 스크립팅 언어입니다. 그러나 때로는 PHP 소스 코드를 실행할 때 다양한 문제에 직면할 수 있으며, 그 중 "인덱스 오류"가 일반적인 상황입니다. 이 문서에서는 몇 가지 일반적인 인덱스 오류 원인과 해결 방법을 소개하고 독자가 이러한 문제를 더 잘 처리하는 데 도움이 되는 특정 코드 예제를 제공합니다. 문제 설명: PHP 프로그램을 실행할 때
Jul 25, 2023 am 09:29 AM
Hashtable은 키-값 쌍을 저장하는 데 사용되는 Java의 데이터 구조 클래스입니다. 해시 테이블 구현을 기반으로 하며 요소의 삽입, 검색, 삭제 작업을 효율적으로 수행할 수 있습니다. Hashtable 클래스에서 키-값 쌍을 삽입하는 방법은 put() 메서드입니다. put() 메소드는 지정된 키-값 쌍을 Hashtable에 삽입하는 데 사용됩니다. 두 개의 매개변수를 허용합니다. 첫 번째 매개변수는 값을 고유하게 식별하는 데 사용되는 키이고, 두 번째 매개변수는 저장할 데이터인 값입니다.
Jul 24, 2023 pm 09:05 PM
Java에서는 Hashtable 클래스의 size() 메서드를 사용하여 해시 테이블의 키-값 쌍 수를 얻습니다. 해시 테이블(Hashtable)은 해시 함수를 사용하여 키를 매핑하는 키-값 쌍 저장 구조입니다. 효율적인 데이터를 얻기 위한 저장 위치 찾기. Java에서 Hashtable은 풍부한 작업 방법과 속성을 제공하는 스레드로부터 안전한 해시 테이블 구현 클래스입니다. Hashtable 클래스의 size() 메서드를 사용하면 해시 테이블의 키-값 쌍 수를 얻을 수 있습니다. 아래에서 코드를 전달하겠습니다.
Jul 25, 2023 am 11:05 AM
Java에서는 Hashtable 클래스의 ContainsValue() 메서드를 사용하여 해시 테이블에 값이 있는지 확인합니다. 해시 테이블은 데이터를 키-값 쌍의 형태로 저장하는 데이터 구조입니다. 데이터에 액세스합니다. Java의 Hashtable 클래스는 해시 테이블을 구현하는 데이터 구조로, 해시 테이블의 데이터를 조작하는 다양한 방법을 제공합니다. 실제 개발을 하다 보면 해시 테이블에 특정 값이 존재하는지 확인해야 하는 경우가 종종 있습니다. 자바의 해시
열거형을 사용하여 Java에서 Hashtable의 요소를 표시하는 방법은 무엇입니까?
Sep 16, 2023 pm 12:41 PM
해시테이블은 프로그래머가 키-값 쌍의 형태로 데이터를 저장하고 구성할 수 있도록 하는 Java의 강력한 데이터 구조입니다. 많은 애플리케이션에서는 해시테이블에서 항목을 검색하고 표시해야 합니다. Hashtable에서는 null이 아닌 모든 개체를 키나 값으로 사용할 수 있습니다. 그러나 Hashtable에 항목을 성공적으로 저장하고 검색하려면 키로 사용되는 객체에 equals() 메서드와 hashCode() 메서드를 구현해야 합니다. 이러한 구현을 통해 키 비교 및 해싱의 정확성이 보장되므로 해시테이블에서 데이터를 효율적으로 관리하고 검색할 수 있습니다. 키()와 요소의 활용을 통해
