• 从哈希结构去理解PHP数组的特性

    对PHP数组操作的几个认识
    服务器君一共花费 33.159 ms 进行了 4 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    对PHP数组操作的几个认识

    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这个函数。

    从哈希表的结构去理解PHP数组的特性

    PHP的hash table具有如下特点:

    • 支持典型的key->value查询
    • 可以当做数组使用
    • 添加、删除节点是O(1)复杂度
    • key支持混合类型:同时存在关联数组合索引数组
    • Value支持混合类型:array (“string”,2332)
    • 支持线性遍历:如foreach

    Zend hash table实现了典型的hash表散列结构,同时通过附加一个双向链表,提供了正向、反向遍历数组的功能。其结构如下图:

    • 可以看到,在hash table中既有key->value形式的散列结构,也有双向链表模式,使得它能够非常方便的支持快速查找和线性遍历。如果想再深入地理解哈希表,可以参看这个:PHP哈希表结构的深入剖析
    • 散列结构:Zend的散列结构是典型的hash表模型,通过链表的方式来解决冲突。需要注意的是zend的hash table是一个自增长的数据结构,当hash表数目满了之后,其本身会动态以2倍的方式扩容并重新元素位置。初始大小均为8。另外,在进行key->value快速查找时候,zend本身还做了一些优化,通过空间换时间的方式加快速度。比如在每个元素中都会用一个变量nKeyLength标识key的长度以作快速判定。
    • 双向链表:Zend hash table通过一个链表结构,实现了元素的线性遍历。理论上,做遍历使用单向链表就够了,之所以使用双向链表,主要目的是为了快速删除,避免遍历。Zend hash table是一种复合型的结构,作为数组使用时,即支持常见的关联数组也能够作为顺序索引数字来使用,甚至允许2者的混合。
    • PHP关联数组:关联数组是典型的hash_table应用。一次查询过程经过如下几步(从代码可以看出,这是一个常见的hash查询过程并增加一些快速判定加速查找。):
    • getKeyHashValue h;
      index = n & nTableMask;
      Bucket *p = arBucket[index];
      while (p) {
      if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
      	RETURN p->data;   
      }
      p=p->next;
      }
      RETURN FALTURE;
      
    • PHP索引数组:索引数组就是我们常见的数组,通过下标访问。例如 $arr[0],Zend HashTable内部进行了归一化处理,对于index类型key同样分配了hash值和nKeyLength(为0)。内部成员变量nNextFreeElement就是当前分配到的最大id,每次push后自动加一。正是这种归一化处理,PHP才能够实现关联和非关联的混合。由于push操作的特殊性,索引key在PHP数组中先后顺序并不是通过下标大小来决定,而是由push的先后决定。例如 $arr[1] = 2; $arr[2] = 3;对于double类型的key,Zend HashTable会将他当做索引key处理。

    关于哈希表结构体设计的几个问答

    前面已经几次提到了PHP哈希表结构体的设计(Zend 哈希表的内部实现),关于该数据结构的几点解释:

    1、链表散列中为什么使用双向链表?

    一般的链表散列只需要按key进行操作,只需要单链表就够了。但是,Zend有时需要从链表散列中删除给定的Bucket,使用双链表可以非常高效的实现。

    2、nTableMask是干什么的?

    这个值用于hash值到arBuckets数组下标的转换。当初始化一个HashTable,Zend首先为arBuckets数组分配nTableSize大小的内存,nTableSize取不小于用户指定大小的最小的2^n,即二进制的10*。nTableMask = nTableSize – 1,即二进制的01*,此时h & nTableMask就恰好落在 [0, nTableSize – 1] 里,Zend就以其为index来访问arBuckets数组。

    3、pDataPtr是干什么的?

    通常情况下,当用户插入一个键值对时,Zend会将value复制一份,并将pData指向value副本。复制操作需要调用Zend内部例程 emalloc来分配内存,这是个非常耗时的操作,并且会消耗比value大的一块内存(多出的内存用于存放cookie),如果value很小的话,将会造成较大的浪费。考虑到HashTable多用于存放指针值,于是Zend引入pDataPtr,当value小到和指针一样长时,Zend就直接将其复制到pDataPtr里,并且将pData指向pDataPtr。这就避免了emalloc操作,同时也有利于提高Cache命中率。

    4、arKey大小为什么只有1?为什么不使用指针管理key?

    arKey是存放key的数组,但其大小却只有1,并不足以放下key。在HashTable的初始化函数里可以找到如下代码:

    p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
    

    可见,Zend为一个Bucket分配了一块足够放下自己和key的内存,上半部分是Bucket,下半部分是key,而arKey“恰好”是Bucket的最后一个元素,于是就可以使用arKey来访问key了。这种手法在内存管理例程中最为常见,当分配内存时,实际上是分配了比指定大小要大的内存,多出的上半部分通常被称为cookie,它存储了这块内存的信息,比如块大小、上一块指针、下一块指针等,baidu的Transmit程序就使用了这种方法。

    不用指针管理key,是为了减少一次emalloc操作,同时也可以提高Cache命中率。另一个必需的理由是,key绝大部分情况下是固定不变的,不会因为key变长了而导致重新分配整个Bucket。这同时也解释了为什么不把value也一起作为数组分配了——因为value是可变的。

    关于HashTable还有一个疑问没有回答,就是nNextFreeElement是干什么的?

    不同于一般的散列,Zend的HashTable允许用户直接指定hash值,而忽略key,甚至可以不指定key(此时,nKeyLength为 0)。同时,HashTable也支持append操作,用户连hash值也不用指定,只需要提供value,此时,Zend就用 nNextFreeElement作为hash,之后将nNextFreeElement递增。

    HashTable的这种行为看起来很奇怪,因为这将无法按key访问value,已经完全不是个散列了。理解问题的关键在于,PHP数组就是使用 HashTable实现的——关联数组使用正常的k-v映射将元素加入HashTable,其key为用户指定的字符串;非关联数组则直接使用数组下标作为hash值,不存在key;而当在一个数组中混合使用关联和非关联时,或者使用array_push操作时,就需要用nNextFreeElement 了。

    再来看value,PHP数组的value直接使用了zval这个通用结构,pData指向的是zval*,按照上一节的介绍,这个zval*将直接存储在pDataPtr里。由于直接使用了zval,数组的元素可以是任意PHP类型。

    数组的遍历操作,即foreach、each等,是通过HashTable的双向链表来进行的,pInternalPointer作为游标记录了当前位置。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [软件工程与项目管理] 浏览器与CSS渲染技巧 2 个条目
  2. [软件工程与项目管理] 浏览器初步介绍 8 个条目
  3. [PHP程序设计] PHP里的布尔类型 3 个条目
  4. [移动开发] Android属性系统Property 9 个条目
  5. [智力开发与知识管理] 信息的类型与结构 9 个条目
  6. [PHP程序设计] PHP里的引用 5 个条目
  7. [数据库技术] SQL基础语法 1 个条目
  8. [软件工程与项目管理] 呈现树的构建 13 个条目
  9. [移动开发] Android View注入框架Butter Knife 3 个条目
  10. [智力开发与知识管理] 学习编程为什么没会这么难? 7 个条目
  11. [数据库技术] 数据库范式篇 5 个条目
  12. [Python程序设计] Tornado背景知识介绍 4 个条目
窗口 -- [协会]