PHP ハッシュ テーブルと配列の概要 (コード付き)

この記事では、PHP のハッシュ テーブルと配列の概要 (コード付き) を紹介します。一定の参考値があります。困っている友人は参照してください。お役に立てれば幸いです。

配列は PHP で最も一般的に使用されるデータ型です。同時に、PHP は強力な配列のおかげで使いやすいですが、PHP では配列はどのように実装されるのでしょうか?

まず、関連するデータ構造を理解し、次の内容の強固な基盤を築く必要があります。

ハッシュ テーブル

##ハッシュ テーブル は、名前が示すように、さまざまなキーワードをさまざまなユニットにマッピングするデータ構造です。さまざまなキーワードをさまざまなユニットにマッピングする方法は、ハッシュ関数と呼ばれます

ハッシュ関数による処理後、理想的には、キーワードとユニットは 1 対 1 になります。ただし、十分なキーワード値がある場合、複数のキーワードを同じユニットにマッピングすることは簡単です。つまり、

ハッシュの競合

ハッシュ 競合の解決策は次のとおりです。

リンク方法 または オープン アドレッシング方法

##リンク方法

のいずれかを使用します。つまり、異なるキーの場合です。単語が同じ単位にマッピングされている場合、リンク リストを使用して、これらのキーワードを同じユニットに保存します。

オープン アドレッシング メソッド

つまり、データを挿入するときに、キーワードが次の場所にマッピングされていることが判明した場合、データが存在します。このユニットは、競合が発生したことを示し、使用可能なユニットが見つかるまで次のユニットの検索を続けます。
また、オープン アドレッシング方式スキームは他のキーワード マッピング ユニットの場所を占有するため、後続のキー単語はハッシュ競合が発生する可能性が高いため、パフォーマンスが低下する傾向があります。

リンク リスト

リンク リストについては上で説明したため、ここでは基本について簡単に説明します。リンクされたリストの。リンク リストはさまざまなタイプに分類されます。一般的に使用されるデータ構造には、キュー、スタック、双方向リンク リストなどが含まれます。

リンク リストは、さまざまなリンク リスト ノードで構成されるデータ構造です。リンク リスト ノードは通常、次のノードを指す

要素

ポインタ で構成されます。二重リンクリストは、その名前が示すように、前のノードを指す ポインタ elements 次のノードを指すポインタ で構成されます。データ構造について 内容については詳しく説明しません。後でデータ構造を詳しく紹介する特別なコンテンツを用意します。

php array

PHP がハッシュの競合を解決する方法Linkingメソッドを使用するため、phpの配列は

ハッシュテーブル

リンクリスト で実装されます。正確には ハッシュテーブル で二重に実装されます。リンク リスト

内部構造 - ハッシュ テーブル

HashTable 構造は、主にハッシュ テーブルの基本情報を格納するために使用されます

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，即哈希表的容量，最小为8，以2x增长。
    uint nTableMask;        // nTableSize-1 ， 索引取值的优化
    uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值 
    ulong nNextFreeElement; // 下一个可使用的数字键值
    Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
    Bucket *pListHead;          // 存储整个哈希表的头元素指针
    Bucket *pListTail;          // 存储整个哈希表的尾元素指针
    Bucket **arBuckets;         // 存储hash数组
    dtor_func_t pDestructor;    // 在删除元素时执行的回调函数，用于资源的释放
    zend_bool persistent;       //指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

Bucket 構造体は、保存されたデータの特定の内容のために使用されます

typedef struct bucket {
    ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值
    uint nKeyLength;    // hash关键字的长度，如果数组索引为数字，此值为0
    void *pData;        // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtr
    void *pDataPtr;     // 如果是指针数据，此值会指向真正的value，同时上面pData会指向此值
    struct bucket *pListNext;   // 指向整个哈希表的该单元的下一个元素
    struct bucket *pListLast;   // 指向整个哈希表的该单元的上一个元素
    struct bucket *pNext;       // 指向由于哈希冲突导致存放在同一个单元的链表中的下一个元素
    struct bucket *pLast;       // 指向由于哈希冲突导致存放在同一个单元的链表中的上一个元素
    // 保存当前值所对于的key字符串，这个字段只能定义在最后，实现变长结构体
    char arKey[1];              
} Bucket;

Bucket 構造体には、ユーザー データを指す pData 要素があり、実際には、前に紹介した変数 zval 構造体を指します。配列を作成するときに配列要素 1 が表示されるのはなぜですか? 変数コンテナ。

ハッシュ テーブルの内部構造図

注: 画像はインターネットから引用しました

上の画像よりBucket がデータを保存するときに、ハッシュの競合がある場合、複数のキーワードがリンク リストにマッピングされ、二重リンク リストが形成されることがわかります。配列をエントリ ポイントとして使用して、基本的なデータ構造であるハッシュ テーブルとリンク リストを簡単に理解しました。また、配列の基礎となる実装、つまり

ハッシュ テーブル

ダブル リンク リスト##についても学びました。 ＃。実際、ハッシュ テーブルは PHP で最も重要なデータ構造であり、多くの用途があります。

【関連する推奨事項:

PHP ビデオ チュートリアル ]

以上がPHP ハッシュ テーブルと配列の概要 (コード付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。