MyException - 我的异常网
当前位置:我的异常网» PHP » 为什么要懂得php内部结构HashTable

为什么要懂得php内部结构HashTable

www.MyException.Cn  网友分享于:2014-08-05  浏览:1次
为什么要了解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有很大的帮助。

文章评论

一个程序员的时间管理
一个程序员的时间管理
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
Java程序员必看电影
Java程序员必看电影
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
那些争议最大的编程观点
那些争议最大的编程观点
中美印日四国程序员比较
中美印日四国程序员比较
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
老程序员的下场
老程序员的下场
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
编程语言是女人
编程语言是女人
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
程序员和编码员之间的区别
程序员和编码员之间的区别
总结2014中国互联网十大段子
总结2014中国互联网十大段子
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员应该关注的一些事儿
程序员应该关注的一些事儿
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
为什么程序员都是夜猫子
为什么程序员都是夜猫子
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
 程序员的样子
程序员的样子
如何成为一名黑客
如何成为一名黑客
我的丈夫是个程序员
我的丈夫是个程序员
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
漫画:程序员的工作
漫画:程序员的工作
鲜为人知的编程真相
鲜为人知的编程真相
旅行,写作,编程
旅行,写作,编程
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
10个调试和排错的小建议
10个调试和排错的小建议
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员都该阅读的书
程序员都该阅读的书
代码女神横空出世
代码女神横空出世
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有