PHPにおける配列構築HashTableの詳細説明

PHPの配列構造HashTable
の詳しい説明

PHP の配列は内部的にハッシュ構造に格納されることがわかっています。この記事の主な焦点は、PHP における配列の静的構造と動的構造を分析して記録することです。

ここでの静的構造とは、PHP で配列データを格納するときに使用されるデータ構造、いわゆる HashTable を指します。

動的構造とは、プログラムの実行プロセス中の配列データの格納状態を指します。

?

まず、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 の配列は、内部的には 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\n");
#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\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)

?

次に、挿入する文字列インデックスのハッシュ値を計算し、nTableMask とビットごとの AND を実行して、nindex を取得します。この nIndex は、2 次元配列 arBucket** 内の対応するバケット* のオフセットです。コードロジックによれば、nIndex の位置が空でない場合は、現在計算されているハッシュ値が以前に存在することを意味します。キーが同じでフラグが HASH_ADD の場合は失敗し、それ以外の場合は更新操作になります。更新操作の場合、既存の配列構造には影響しません。対応する値を更新した後、直接終了できます。

?

新しい要素をハッシュテーブルに挿入する必要がある場合、構築された新しい要素は 2 つのステップでハッシュテーブルにリンクされます

?

最初のステップのコードは次のとおりです:

?

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

?

このステップでは、新しい要素のキーのハッシュ値が以前に存在していた場合、list_head は HashTable.arBucket[nIndex] になります。nIndex の取得方法は前述しました。このステップの後、HashTable.arBucket[nIndex] には現在の新しい要素の値が割り当てられます。

?

新しい要素のキーに対応するハッシュが以前に存在しなかった場合、HashTable.arBucket[nIndex] が NULL であるため、list_head は 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.

そのキーに対応するハッシュ値が 1 であると仮定して、最初の要素 A を挿入します

挿入後のメモリ内のステータスは次のとおりです:

?

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 であると仮定して、2 番目の要素 B を挿入します

挿入後のメモリの状態は次のようになります。

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.

そのキーのハッシュ値が A と同じ 1 であると仮定して、3 番目の要素 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

?

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、3 つの要素 A、B、C が挿入されました。次に、2 つのタスクを実装する必要があります。

?

1.

キーの要素値 (値) を検索します:

A 要素にアクセスしたい場合は、A のキー key_a を指定し、対応するハッシュ値 1 を取得します

次に、HstTable.arBucket[1] を見つけます。このとき、HstTable.arBucket[1]は実際にはAではなくCですが、CのキーはAのキーと等しくないため、pNextポインタに沿ってNULLになるまで検索する必要があり、この時点ではCです。 pNext は A、つまり、key_a に対応する値 A を取得します。

つまり、キーで要素を検索する場合は、まず要素をハッシュし、ハッシュ後のインデックス位置で pNext ポインタに沿って、探しているキーと同じ値が見つかるまで検索を続ける必要があります。 、それを見つけます、それ以外の場合はそれ未満を見つけます。

?

2.

配列を走査します:

この例のキーは文字列型であるため、すべてのループ走査で for を使用できるわけではありません。 foreach しか使用できないのですが、foreach トラバーサルはどのように実装されるのでしょうか?

?

簡単に言うと、最後の HashTable のステータスに従って、HstTable.pListHead から開始して、pListNext ポインタに沿って順番に検索します。この記事の例を例にとると、結果は次のようになります:

?

?

HashTable.pListHead====>A

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

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

?

最終的な走査順序は A、B、C になります。 foreach の走査順序は、要素が配列に挿入される順序に関連していることがわかります。

?

?

挿入された要素のキーが文字列ではなく数値の場合。これにより、ハッシュ値を計算する手順を省略し、数値キーを直接ハッシュ値として使用できます。

この方法では、ハッシュの競合の問題は発生せず、各要素の pNext ポインターと pLast ポインターは両方とも NULL のみになります。

?

この方法では、ハッシュの競合がないため、for ループを使用して配列を走査できます。

?

同様に、foreach を使用して配列を走査する場合、走査順序は依然として要素の挿入順序であることは理解されています。

?

?

追記：

この記事は、zend のハッシュ構造を完全に記録しているわけではありません。この記事のトピックに関係するロジックの主要なコードを分析して説明するだけです。同時に要点を把握するため。再ハッシュ ロジックや数値データのインデックスを作成するコードなど、一部のコードはリストされていません。これらの詳細は、コード ファイル Zend/zend_hash.c にあります。

?