PHP HashTable の内部構造を理解する必要がある理由

なぜphp HashTable

の内部構造を理解する必要があるのか​​1. HASHTable

の定義1. ? ?ハッシュテーブルは、指定されたハッシュ関数HASHに従って、キー名keyをテーブル内のレコードにマッピングします。この配列がハッシュテーブルです。ここでの HASH は、MD5、CRC32、SHA1、カスタム関数などの関数を指します。

2. ハッシュテーブルの性能

? HashTable は非常に検索性能の高いデータ構造であり、多くの言語で実装されています。理想的には、HashTable のパフォーマンスは O(1) です。パフォーマンスの消費は主に、HASH(key) を通じてテーブル内のレコードを直接検索するハッシュ関数 HASH(key) に集中します。実際には、key1!=key2 が発生することがよくありますが、HASH(key1)=HASH(key2) という状況が発生する可能性が低いほど、HashTable のパフォーマンスは向上します。もちろん、ハッシュ アルゴリズムが複雑すぎると、Hashtable のパフォーマンスにも影響します。

3. HashTable のアプリケーション

? HashTable は PHP カーネルにも実装されており、スレッド セーフ、変数ストレージ、リソース管理などに広く使用されています。彼はどこにでもいます。それだけでなく、配列とクラスも PHP スクリプトで広く使用されています。以下では、配列、変数、関数、クラスにおける HashTable の適用に焦点を当てます。

2. 配列に対する HashTable の適用

? PHP のほとんどの関数は、配列を含めて HashTable を通じて実装されます。 HashTable は二重リンクリストの利点を持ちながら、データに見合った動作性能を備えています。 PHP で定義された変数はシンボル テーブルに格納されます。このシンボル テーブルは実際には HashTable であり、その各要素は zval* 型の変数です。それだけでなく、ユーザー定義の関数、クラス、リソースなどを格納するコンテナーが HashTable の形式でカーネルに実装されます。

? 以下は PHP で定義された配列です:

?コード マクロ展開:

$array = array();$array["key"] = "value";

? 上記のコードを通じて、配列での HashTable の応用を発見しました。実際、配列は PHP カーネルの HashTable を通じて実装されます。配列を初期化した後の次のステップは、配列に要素を追加することです。 PHP 言語には多くの種類の変数があるため、add_assoc_*()、add_index_*、および add_next_index_*() 関数もさまざまな種類があります。これらの 3 つの関数は、それぞれ、PHP プログラミングで配列に要素を追加する方法に対応しています。 add_assoc_*() は、指定された key->value の形式で配列要素を追加します。 add_index_*() は、キーが数値型である要素を追加します。 add_next_index_*() は、要素を追加します。キーを指定せずに。リソース、オブジェクト、配列などの複合タイプの PHP 変数を配列に追加できます。

zval* array;array_init(array);add_assoc_string(array,"key","value",1);

??このとき、クライアント側で var_dump 関数を使用すると、戻り値は次のようになります:

zval* array;  ALLOC_INIT_ZVAL(array);  Z_TYPE_P(array) = IS_ARRAY;    HashTable *h;  ALLOC_HASHTABLE(h);  Z_ARRVAL_P(array)=h;  zend_hash_init(h, 50, NULL,ZVAL_PTR_DTOR, 0);    zval* barZval;  MAKE_STD_ZVAL(barZval);  ZVAL_STRING(barZval, "value", 0);  zend_hash_add(h, "key", 4, &barZval, sizeof(zval*), NULL);

ZEND_FUNCTION(sample_array){    zval *subarray; array_init(return_value);       /* Add some scalars */  add_assoc_long(return_value, "life", 42);   add_index_bool(return_value, 123, 1);   add_next_index_double(return_value, 3.1415926535);      /* Toss in a static string, dup'd by PHP */ add_next_index_string(return_value, "Foo", 1);      /* Now a manually dup'd string */   add_next_index_string(return_value, estrdup("Bar"), 0); /* Create a subarray */ MAKE_STD_ZVAL(subarray);    array_init(subarray);       /* Populate it with some numbers */ add_next_index_long(subarray, 1);   add_next_index_long(subarray, 20);  add_next_index_long(subarray, 300);     /* Place the subarray in the parent */  add_index_zval(return_value, 444, subarray);}

3. 変数のシンボルテーブル (変数の適用)

<?phpvar_dump(sample_array());?>//输出array(6){ ["life"]=> int(42)   [123]=> bool(true)   [124]=> float(3.1415926535)  [125]=> string(3) "Foo"  [126]=> string(3) "Bar"  [444]=> array(3) {       [0]=> int(1)     [1]=> int(20)        [2]=> int(300)   }}

? 配列における HashTable の適用について説明しました。変数はどのように適用されますか。ここで 2 つの問題を理解する必要があります。1 つは、変数は変数名と変数値に対応して表示されるため、それらはどのように格納されるのかということです。もう 1 つは、変数には対応するライフサイクルがあるということです。これはどのように実装されるのでしょうか。

??PHP コードでは、いつでも 2 つの変数シンボル テーブル、symbol_table と active_symbol_table を参照できます。前者はグローバル シンボル テーブルと呼ばれる、グローバル変数を格納するために使用されます。現在のアクティビティ 変数シンボル テーブルは通常、グローバル シンボル テーブルです。ただし、PHP 関数 (ここではユーザーが PHP コードを使用して作成した関数を指します) を入力するたびに、Zend は関数ローカル変数シンボル テーブルを作成し、active_symbol_table がローカル シンボル テーブルを指すようにします。 Zend は常に active_symbol_table を使用して変数にアクセスするため、ローカル変数のスコープ制御を実現します。 ? しかし、グローバルとしてマークされた変数が関数内でローカルにアクセスされると、Zend は特別な処理を実行します。同じ名前の変数が active_symbol_table に存在しない場合は、その変数への参照が作成されます。 symbol_table は最初に作成されます。

? EG マクロを通じて変数シンボル テーブルにアクセスできます。EG (symbol_table) はグローバル スコープの変数シンボル テーブルにアクセスし、EG (active_symbol_table) は現在のスコープの変数シンボル テーブルにアクセスします。

? 上記のコードは非常に単純で、変数 foo を作成し、それを bar に割り当てます。 $foo 変数は、後続の PHP コードで呼び出すことができます。ここで、PHP で定義された変数と、それらがカーネルでどのように実装されるかを見てみましょう。疑似コード:

struct _zend_executor_globals {      //略      HashTable symbol_table;//全局变量的符号表      HashTable *active_symbol_table;//局部变量的符号表      //略  };

ステップ 1: zval 構造体を作成し、型を設定します。

<?php  $foo='bar';  ?>

ステップ 2: bar に値を割り当てます。

zval* foo;  MAKE_STD_ZVAL(foo);  ZVAL_STRING(foo, "bar", 1);  ZEND_SET_SYMBOL( EG(active_symbol_table), "foo", foo);

ステップ 3: 現在の

スコープ シンボル テーブル

に追加すると、ユーザーはこの変数を PHP で使用できるようになります。

备注：大家都知道PHP脚本在执行的时候用户全局变量(在用户空间显式定义的变量)会保存在一个HashTable数据类型的符号表(symbol_table)中， 在PHP中有一些比较特殊的全局变量例如: $_GET，$_POST，$_SERVER等变量，我们并没有在程序中定义这些变量，并且这些变量也同样保存在符号表中， 从这些表象我们不难得出结论：PHP是在脚本运行之前就将这些特殊的变量加入到了符号表中了。

四、HashTable在类上的应用

? ? ?类和函数类似，PHP内置及PHP扩展均可以实现自己的内部类，也可以由用户使用PHP代码进行定义。 当然我们在编写代码时通常是自己定义。

? ? ?使用上，我们使用class关键字进行定义，后面接类名，类名可以是任何非PHP保留字的名字。 在类名后面紧跟着一对花括号，里面是类的实体，包括类所具有的属性，这些属性是对象的状态的抽象， 其表现为PHP中支持的数据类型，也可以包括对象本身，通常我们称其为成员变量。 除了类的属性， 类的实体中也包括类所具有的操作，这些操作是对象的行为的抽象，其表现为用操作名和实现该操作的方法， 通常我们称其为成员方法或成员函数。看类示例的代码：

class ParentClass {} interface Ifce {        public function iMethod();} final class Tipi extends ParentClass implements Ifce {        public static $sa = 'aaa';        const CA = 'bbb';         public function __constrct() {        }         public function iMethod() {        }         private function _access() {        }         public static function access() {        }}

? ??这里定义了一个父类ParentClass，一个接口Ifce，一个子类Tipi。子类继承父类ParentClass， 实现接口Ifce，并且有一个静态变量$sa，一个类常量 CA，一个公用方法，一个私有方法和一个公用静态方法。 这些结构在Zend引擎内部是如何实现的？我们看看类的内部存储结构：

struct _zend_class_entry {    char type;     // 类型：ZEND_INTERNAL_CLASS / ZEND_USER_CLASS    char *name;// 类名称    zend_uint name_length;                  // 即sizeof(name) - 1    struct　_zend_class_entry *parent; // 继承的父类    int　refcount;  // 引用数    zend_bool constants_updated;     zend_uint ce_flags; // ZEND_ACC_IMPLICIT_ABSTRACT_CLASS: 类存在abstract方法    // ZEND_ACC_EXPLICIT_ABSTRACT_CLASS: 在类名称前加了abstract关键字    // ZEND_ACC_FINAL_CLASS    // ZEND_ACC_INTERFACE    HashTable function_table;      // 方法    HashTable default_properties;          // 默认属性    HashTable properties_info;     // 属性信息    HashTable default_static_members;// 类本身所具有的静态变量    HashTable *static_members; // type == ZEND_USER_CLASS时，取&default_static_members;    // type == ZEND_INTERAL_CLASS时，设为NULL    HashTable constants_table;     // 常量    struct _zend_function_entry *builtin_functions;// 方法定义入口      union _zend_function *constructor;    union _zend_function *destructor;    union _zend_function *clone;      /* 魔术方法 */    union _zend_function *__get;    union _zend_function *__set;    union _zend_function *__unset;    union _zend_function *__isset;    union _zend_function *__call;    union _zend_function *__tostring;    union _zend_function *serialize_func;    union _zend_function *unserialize_func;    zend_class_iterator_funcs iterator_funcs;// 迭代     /* 类句柄 */    zend_object_value (*create_object)(zend_class_entry *class_type TSRMLS_DC);    zend_object_iterator *(*get_iterator)(zend_class_entry *ce, zval *object,        intby_ref TSRMLS_DC);     /* 类声明的接口 */    int(*interface_gets_implemented)(zend_class_entry *iface,            zend_class_entry *class_type TSRMLS_DC);      /* 序列化回调函数指针 */    int(*serialize)(zval *object， unsignedchar**buffer, zend_uint *buf_len,             zend_serialize_data *data TSRMLS_DC);    int(*unserialize)(zval **object, zend_class_entry *ce, constunsignedchar*buf,            zend_uint buf_len, zend_unserialize_data *data TSRMLS_DC);      zend_class_entry **interfaces;  //  类实现的接口    zend_uint num_interfaces;   //  类实现的接口数      char *filename; //  类的存放文件地址 绝对地址    zend_uint line_start;   //  类定义的开始行    zend_uint line_end; //  类定义的结束行    char *doc_comment;    zend_uint doc_comment_len;      struct _zend_module_entry *module; // 类所在的模块入口：EG(current_module)};

? ? 我们可以看到，在类的实现上，大量使用了hashTable来存储一些类的相关信息，类的属性和方法这些关键信息都是由hashTable存储记录的。

? ? 上面我们列举了hashTable在php应用的几个方面，可以看到hashTable在php内核代码中应用非常广泛，所以有必要深入了解一下hashTable是如何实现的，这对我们深入理解php有很大的帮助。