为什么要了解php内部结构HashTable

一、认识HASHTable

1、hashtable的定义

     哈希表是将键名key按指定的散列函数HASH经过HASH（key)计算后映射到表中一个记录，而这个数组就是哈希表。其中这里的HASH指任意的函数，例如：MD5、CRC32、SHA1或自定义的函数。

2、hashtable的性能

     hashtable是一种查找性能极高的数据结构，在很多语言内部都实现了HashTable。理想情况下HashTable的性能是O(1)的，性能消耗主要集中在散列函数HASH(key)，通过HASH（key)直接定位到表中的记录。而在实际情况下经常会发生key1!=key2,但HASH(key1)=HASH(key2),这种情况即HASH碰撞问题，碰撞的概率越低HashTable的性能越好。当然Hash算法太过复杂也会影响Hashtable的性能。

3、HashTable的应用

     在php内核也同样实现了HashTable并广泛应用，包括线程安全、变量存储、资源管理等基本上所有的地方都能看到他的身影。不仅如此，在php脚本中数组、类也是被广泛使用的。下面就着重介绍一下HashTable在数组、变量、函数、类这几个方面的应用。

二、HashTable在数组上的应用

    PHP大部分功能都是通过HashTable来实现，其中就包括数组。HashTable即具有双向链表的优点，同时具有能与数据匹配的操作性能。PHP中的定义的变量保存在一个符号表里，而这个符号表其实就是一个HashTable，它的每一个元素都是一个zval*类型的变量。不仅如此，保存用户定义的函数、类、资源等的容器都是以HashTable的形式在内核中实现的。

    下面是PHP中定义的数组：

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

    在内核中使用宏来实现：

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

    将上述代码中的宏展开：

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);

    通过上面的代码，我们就发现了HashTable在array中的应用。实际上在PHP内核中数组正是通过HashTable实现的。将数组初始化后，接下来就要向其添加元素了。因为PHP语言中有多种类型的变量，所以也对应的有多种类型的add_assoc_*()、add_index_*、add_next_index_*()函数，这三个函数分别对应着我们在php编程中为数组添加元素的方式，其中：add_assoc_*（）是添加指定key->value形式的数组元素；add_index_*()是添加key为数字类型的元素；add_next_index_*()是不指定key添加元素。数组中允许添加资源、对象、数组等复合类型的PHP变量。下面让我们通过一个例子来演示下它们的用法：

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);
}

    这时如果我们用户端var_dump这个函数的返回值便会得到：

<?php
var_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在数组中的应用，下面我们来看看HashTable在变量中是如何应用的。在这里我们需要了解两方面的问题：一个是变量都是变量名和变量值对应出现的，那他们是如何存储的呢？另一个是变量都有对应的生命周期，这个是如何实现的呢？

    在任一时刻PHP代码都可以看见两个变量符号表——symbol_table和active_symbol_table——前者用于存储全局变量，称为全局符号表；后者是个指针，指向当前活动的变量符号表，通常情况下就是全局符号表。但是，当每次进入一个PHP函数时（此处指的是用户使用PHP代码创建的函数），Zend都会创建函数局部的变量符号表，并将active_symbol_table指向局部符号表。Zend总是使用active_symbol_table来访问变量，这样就实现了局部变量的作用域控制。

    但如果在函数局部访问标记为global的变量，Zend会进行特殊处理——在active_symbol_table中创建symbol_table中同名变量的引用，如果symbol_table中没有同名变量则会先创建。

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

   可以通过EG宏来访问变量符号表，EG(symbol_table)访问全局作用域的变量符号表，EG(active_symbol_table)访问当前作用域的变量符号表。

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

   上面这段代码很简单，创建变量foo，并赋值bar。之后的PHP代码中就可以调用$foo变量了。现在看看PHP中定义的变量，内核中是如何实现的。伪代码：

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

第1步：创建一个zval结构，并设置类型。

第2步：赋值为bar。

第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有很大的帮助。