PHPにおけるArray構造HashTableの詳細
詳細
PHP中のArrayは内部にHashの構造で格納されていることを知っている.本論文の主な重点はPHPにおけるArrayの静的構造と動的構造の解析と記録である.
ここでの静的構造とは、PHPにおけるArrayデータを格納する際に用いられるデータ構造、いわゆるHashTableである.
動的構造とは、プログラムの実行中にArrayデータが格納された状態をいう.
まずPHPにおけるhashTableの構成は以下の通りである.
1つのPHP中のArrayは内部で1つのHashTableに対応し,HashTable内部の4つのBucketタイプのポインタデータは配列が実際に記憶している要素コンテンツのアドレスを記録している.具体的な内容は、各フィールド名が自己解釈可能で、あまり説明しません.
これらの行のコードだけを見ると、PHP配列の実際の動作原理が理解できない可能性があります.次に、PHP配列の中で最も簡単な操作を手動でシミュレートすることができます.
1.無から有へ
HashTableの初期化には、まずHashTableにメモリ領域を構築する必要があります.具体的なコードは以下の通りです.
上記のコードは,配列に総ゲートを構築し,データはいずれもこのゲートを介して自分の対応するメモリブロックに入ることができると理解できる.もちろん今はドアに「席」はありません.
2.データ挿入
何もない空間に対して、どうやって何かを追加しますか?これがデータの挿入です.つまり、データがこのHashTableにどのように保存されているかです.
PHPの配列インデックスは数値または文字列であり、まず文字列のインデックスがどのように格納されているかを見てみましょう.コードは以下の通りです.
まず、配列空間が初期化されているかどうかを確認します.コードは次のとおりです.
次に、挿入する文字列インデックスのhash値を計算し、2 D配列arBucket**における対応するbucket*のオフセット量であるnTable Maskとビット順にnindexを得る.コードロジックによれば、nIndex位置が空でない場合、現在計算されたhash値の前に存在することを示す.キーも同じでflagがHASH_ならADDは失敗し、そうでなければ更新操作です.更新操作の場合、既存の配列構造には影響しません.対応する値を更新した後、直接終了すればいいです.
新しい要素をHashTableに挿入する必要がある場合、構築された新しい要素は2つのステップを経てHashTableにチェーンされます.
手順1のコードは次のとおりです.
このステップで、新しい要素のkeyのhash値が前に存在する場合、list_HeadはHashTableです.ArBucket[nIndex],nIndexがどうやって来たかは前述しています.そのあとはArBucket[nIndex]は現在の新しい要素に割り当てられています.
新しい要素のkeyに対応するhashが以前に存在しなかった場合、list_ヘッドはNULLだArBucket［nIndex］はNULLである.あなたも知っています.
ステップ2のコードは次のとおりです.
このステップが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.
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.
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の3つの値を挿入した後のメモリのステータスは次のとおりです.
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の3つの要素が挿入されました.今、2つのタスクを実現します.
1.
キーの要素値(value)を検索します.
A要素にアクセスする場合は、Aのkey:key_を指定します.a,得られた対応hash値は1
そしてハンスタブを探します.arBucket[1].この時ArBucket[1]実はCはAではないが、CのkeyはAのkeyに等しくないため、pNextのポインタに沿ってNULLまで探し続けるが、このときC.pNextはAであり、key_が見つかったa対応する値A.
要するにkeyによって1つの要素を検索する時、まず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の2つのポインタは使用されません.この2つのポインタはNULLのみです.
これにより、hash競合が存在しないため、forループを使用して配列を巡回することができます.
同様にforeachを使用して配列を遍歴すると、遍歴順序か要素の挿入順序かはもちろんわかります.
ps:
本文はzend中のhash接合を全面的に記録するのに十分ではなく,本論文のテーマに関連する論理の重点コードを分析し,実証しただけである.同時にポイントをつかむためにも.再hashの論理や、インデックスが数値型データのコードなど、一部のコードはリストされていません.これらはコードファイルZend/zend_hash.cで詳細を見つけます.
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;
1つのPHP中のArrayは内部で1つのHashTableに対応し,HashTable内部の4つの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 << i) < nSize) {
i++;
}
ht->nTableSize = 1 << i;
}
ht->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 <= 0) {
#if ZEND_DEBUG
ZEND_PUTS("zend_hash_update: Can't put in empty key
");
#endif
return FAILURE;
}
CHECK_INIT(ht); //
h = zend_inline_hash_func(arKey, nKeyLength); // hash
nIndex = h & ht->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
");
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値を計算し、2 D配列arBucket**における対応するbucket*のオフセット量であるnTable Maskとビット順にnindexを得る.コードロジックによれば、nIndex位置が空でない場合、現在計算されたhash値の前に存在することを示す.キーも同じでflagがHASH_ならADDは失敗し、そうでなければ更新操作です.更新操作の場合、既存の配列構造には影響しません.対応する値を更新した後、直接終了すればいいです.
新しい要素をHashTableに挿入する必要がある場合、構築された新しい要素は2つのステップを経てHashTableにチェーンされます.
手順1のコードは次のとおりです.
#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がどうやって来たかは前述しています.そのあとはArBucket[nIndex]は現在の新しい要素に割り当てられています.
新しい要素のkeyに対応するhashが以前に存在しなかった場合、list_ヘッドはNULLだArBucket［nIndex］はNULLである.あなたも知っています.
ステップ2のコードは次のとおりです.
#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.
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.
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の3つの値を挿入した後のメモリのステータスは次のとおりです.
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の3つの要素が挿入されました.今、2つのタスクを実現します.
1.
キーの要素値(value)を検索します.
A要素にアクセスする場合は、Aのkey:key_を指定します.a,得られた対応hash値は1
そしてハンスタブを探します.arBucket[1].この時ArBucket[1]実はCはAではないが、CのkeyはAのkeyに等しくないため、pNextのポインタに沿ってNULLまで探し続けるが、このときC.pNextはAであり、key_が見つかったa対応する値A.
要するにkeyによって1つの要素を検索する時、まず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の2つのポインタは使用されません.この2つのポインタはNULLのみです.
これにより、hash競合が存在しないため、forループを使用して配列を巡回することができます.
同様にforeachを使用して配列を遍歴すると、遍歴順序か要素の挿入順序かはもちろんわかります.
ps:
本文はzend中のhash接合を全面的に記録するのに十分ではなく,本論文のテーマに関連する論理の重点コードを分析し,実証しただけである.同時にポイントをつかむためにも.再hashの論理や、インデックスが数値型データのコードなど、一部のコードはリストされていません.これらはコードファイルZend/zend_hash.cで詳細を見つけます.