注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TOTO

Think and Be Different

 
 
 

日志

 
 

PHP中数组实现分析  

2009-12-03 19:54:39|  分类: 看看书 写写笔记 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关于PHP的数组实现,已经有文章比较详细的说明了
[1] [x]  [2]
【第一个链接不知道怎么回事,已经失效,但是还是最权威的一个版本,很多网站抄了这篇文章,但是没有留下原文地址,对此我也感到悲哀。还好看Goolgle的快照还能看到一些 比如:这篇
【突然想到一个办法来判断这篇文章是不是博主原创的办法:如果博主的博客中有图片,使用了自己域名下的图片,那么这篇文章很有可能是原创,当然这个也不是完全之策,还要加上其他特征】
转入正题:
php的数组实际上就是hash_table,无论是array(1, 2, 3)还是array(1 => 2 , 2=> 4)等等。
这里的hash_table有几个特殊的地方:
(1)遍历的时候的顺序和插入的顺序一致,也就是如果你插入的时候顺序是:
$a = array();
$a[3] = 3;
$a[2] = 2;
$a[1] = 1;
那么它foreach的遍历顺序还是3, 2, 1。
我们可以利用这个特殊的性质,如果开始的时候,插入的顺序是有序的,那么foreach也是有序的,这个是很方便的。
(2)插入和删除都是O(1)的复杂度,特别是删除,比较方便
(3)遍历的效率低于一般的数组,因为数据不是连续的。【为什么foreach会快于for呢?对于一般的数组来说,这两个的效率应该是一样的,但是由于它是hash_table,所以for的话,相当于每次key为i,取它的value,而foreach是内部的一个链表遍历,相对来说会快~~~~】
(4)对于数组一些方法的实现也不能完全按照一般数组的方式来设想,可能会有差别,如果想知道在什么地方不同,请查看Zend_hash.c这个函数。
下面开始分析?这里我只说一些比较重要的地方:
既然是hash_table,那么必然有所谓的桶,桶的数据结构如下:
typedef struct bucket {
    ulong h;                        /* Used for numeric indexing */ /*这里的h对于数字数组来说,就存i,对于其他的,存hash_code*/
    uint nKeyLength;         /*存arKey的长度*/
    void *pData;                /*存key对应的value*/
    void *pDataPtr;            /*存key对应vlaue的指针,这个用于大对象,指向已经存在的对象*/
    struct bucket *pListNext;   /* 下一个元素, 用于遍历*/
    struct bucket *pListLast;  /* 上一个元素,用户遍历*/
    struct bucket *pNext;    /*同一个桶的下一个元素,用于冲突*/
    struct bucket *pLast;    /*同一个桶的上一个元素,用于冲突*/
    char arKey[1]; /* Must be last element */   /*这里是为了处理变长数组,而特意设定的,否则它会紧挨着nKeyLength*/
} Bucket;
这里着重说一下arKey这个东东,它是为了处理变长的key而存在并设定为最后一个域。
在函数_zend_hash_add_or_update 有这么一段:
    p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
    if (!p) {
        return FAILURE;
    }
    memcpy(p->arKey, arKey, nKeyLength);
    p->nKeyLength = nKeyLength;
注意到分配的大小是sizeof(Bucket)-1+nKeyLength,这里已经就把arKey的字符串大小包含了进去,所以bucket的实际大小是不定的。也只有放在最后才能实现变长,放在其他位置都不能变长。另外也可以使用char arKey[0]来代替,不过char arKey[0]到了C99才支持,所以这个地方可能是为了兼容其他的C标准,所以写了char arKey[1]。
这里有更详细的描述

咱们再来分析另外一个结构体 _hashtable:
typedef struct _hashtable {
    uint nTableSize;            /*Hash 表的大小,一般为2的幂*/
    uint nTableMask;          /*nTableSize-1,不知道为什么把它也单独作为一个变量?现在知道的作用是将桶的序号Mask为小雨nTableSize的数,方法是a&nTableMask。*/
    uint nNumOfElements;  /*已经存储的元素个数*/
    ulong nNextFreeElement; /*指向下一个空闲的桶的索引,用于指定索引情形下的元素插入*/
    Bucket *pInternalPointer;    /* Used for element traversal */  /*比如 foreach*/
    Bucket *pListHead;        /*第一个元素*/
    Bucket *pListTail;           /*最后一个元素*/
    Bucket **arBuckets;       /*桶数组*/
    dtor_func_t pDestructor;  /*pDestructor是一个函数指针,在HashTable的增加、修改、删除Bucket时自动调用,用于处理相关数据的清理工作。*/
    zend_bool persistent;    /*persistent标志位指出了Bucket内存分配的方式。如果persisient为TRUE,则使用操作系统本身的内存分配函数为Bucket分配内存,否则使用php的内存分配函数*/
    unsigned char nApplyCount;
    zend_bool bApplyProtection;  /*nApplyCount与bApplyProtection结合提供了一个防止在遍历HashTable时进入递归循环时的一种机制。*/
#if ZEND_DEBUG
    int inconsistent;  /*debug */
#endif
} HashTable;

这里就不多解释了。
这里再说一下hash的函数:php和其他开源软件一样使用的是DJBX33A (Daniel J. Bernstein, Times 33 with Addition)这个hash算法,可以用一个表达式来说明这个算法:
hash(i) = hash(i-1) * 33 + str[i]。
这里需要注意的是: 33。为什么会选择33这个数字?[代码里面有这么段注释
]
/*
* DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
*
* This is Daniel J. Bernstein's popular `times 33' hash function as
* posted by him years ago on comp.lang.c. It basically uses a function
* like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
* known hash functions for strings. Because it is both computed very
* fast and distributes very well.
*
* The magic of number 33, i.e. why it works better than many other
* constants, prime or not, has never been adequately explained by
* anyone. So I try an explanation: if one experimentally tests all
* multipliers between 1 and 256 (as RSE did now) one detects that even
* numbers are not useable at all. The remaining 128 odd numbers
* (except for the number 1) work more or less all equally well. They
* all distribute in an acceptable way and this way fill a hash table
* with an average percent of approx. 86%.
*
* If one compares the Chi^2 values of the variants, the number 33 not
* even has the best value. But the number 33 and a few other equally
* good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
* advantage to the remaining numbers in the large set of possible
* multipliers: their multiply operation can be replaced by a faster
* operation based on just one shift plus either a single addition
* or subtraction operation. And because a hash function has to both
* distribute good _and_ has to be very fast to compute, those few
* numbers should be preferred and seems to be the reason why Daniel J.
* Bernstein also preferred it.
*
*
* -- Ralf S. Engelschall <rse@engelschall.com>
*/

其实这里需要我学习的还有它的实现:
static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
{
register ulong hash = 5381;

/* variant with the hash unrolled eight times */
for (; nKeyLength >= 8; nKeyLength -= 8) {
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
hash = ((hash << 5) + hash) + *arKey++;
}
switch (nKeyLength) {
case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 1: hash = ((hash << 5) + hash) + *arKey++; break;
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
return hash;
}
它用到了这么几个技术:
(1)语言层面上:static , inline对函数的修饰, register对变量的修饰
(2)起始数字的选择: ulong hash = 5381;
(3)
unroll,加快CPU的流水运行 [这个技术参看csapp 第五章]
(4)直接* 33 换成 hash <<5 + hash

finished




  评论这张
 
阅读(564)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017