在PHP中，除了zval, 另一个比较重要的数据结构非hash table莫属，例如我们最常见的数组，在底层便是hash table。除了数组，在线程安全（TSRM）、GC、资源管理、Global变量、ini配置管理中，几乎都有Hash table的踪迹（上一次我们也提到，符号表也是使用Hash table实现的）。那么，在PHP中，这种数据有什么特殊之处，结构是怎么实现的？ 带着这些问题，我们开始本次的内核探索之旅。

本文主要内容：

1. Hash table的基本介绍
2. PHP底层Hash table的结构和实现
3. Zend Hash table API

1. 基本定义

Hash table,又叫哈希表，散列表，Hash表，维基百科上对哈希表的定义是："散列表，是根据关键字（Key value）而直接访问在内存存储位置的数据结构。也就是说，它通过把键值通过一个函数的计算，映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。”。提取文中的主干，我们可以得出如下信息：

（1）.Hash table是一种数据结构。

（2）.这种数据结构是普通数组的扩展。

（3）.这种数据结构通过key->value的映射关系，使得插入和查找的效率很高（数组可以直接寻址，可在O(1)的时间内访问任意元素）。

我们知道，在一般的数组、线性表、树中，记录在结构中的位置是相对随机的，即记录和关键字之间不存在直接的、确定的对应关系。在这些结构中，要查找和插入关键字，常常需要进行一系列的比较，查找的效率通常是O(n)或者O(lgn)的。而Hash table通过Hash函数建立了关键字和记录之间的对应关系，使得普通的查找和插入操作可以在O(1)（平均时间复杂度）的时间内完成，这显然是最理想的查找方式。

2. Hash函数

如上所述，Hash函数建立了关键字和记录之间的对应关系,即：Record = Hash(key) , 这种对应关系如下所示：

理论上，哈希函数可以是任何函数如Crc32, unique_id,md5,SHA1或者用户自定义的函数。这个函数的好坏直接关系到Hash table的性能（考虑冲突和查找的性能）。这里列举了几个常见的Hash函数和对应的实现，有兴趣的童鞋可以看看。一个典型的字符串Hash算法如下：

function hash( $key ){    $result = 0;    $len = strlen($key);    for($i = 0;$i < $len; $i++ ){        $result += ord($key{$i}) * ((1 << 5) + 1);    }    return $result;}

3.冲突解决

在理想的情况下，我们期望任何关键字计算出的Hash值都是唯一的，这样我们便可以通过Hash(key)这种方式直接定位到要查找的记录。但不幸的，几乎没有一个Hash函数可以满足这样的特性（即使有这样的Hash函数，也可能很复杂，无法在实际中使用）。也就是说，即使是精心设计的Hash函数，也经常会出现key1 != key2 但是hash(key1) = hash(key2)的情况，这便是Hash冲突（Hash碰撞）。解决Hash碰撞的主要方法有多种（见这里），作为示例，我们只简单讨论下链接法解决冲突。这种方法的基本思想是：在哈希表出现冲突时，使用链表的形式链接所有具有相同hash值的记录，而哈希表中只保存链表的头指针。PHP底层的Hash table，便是使用链表（双向链表）来解决hash冲突的。关于这一点，后续会有详细的介绍。

引入链表之后，Hash table的结构如下所示：

一个简单的Hash table的实现如下：

Class HashTable{    PRivate $buckets = null; /* current size */private $size = 0;    /* max hashtable size */private $max = 2048;private $mask = 0;public function __construct($size){$this->_init_hash($size);}/* hashtable init */private function _init_hash($size){if($size > $this->max){$size = $this->max;}$this->size     = $size;$this->mask    = $this->size - 1;// SplFixedArray is faster when the size is known// see http://php.net/manual/en/class.splfixedarray.php$this->buckets = new SplFixedArray($this->size);}    public function hash( $key ){        $result = 0;        $len  = strlen($key);         for($i = 0;$i < $len; $i++ ){            $result += ord($key{$i}) * ((1 << 5) + 1);        }        return $result % ($this->size);    }    /* 拉链法 */    public function insert( $key, $val ){        $h = $this->hash($key);        if(!isset($this->buckets[$h])){            $next = NULL;        }else{            $next = $this->bucket[$h];        }        $this->buckets[$h] = new Node($key, $val, $next);    }      /* 拉链法 */    public function lookup( $key ){        $h   = $this->hash($key);        $cur = $this->buckets[$h];         while($cur !== NULL){            if( $cur->key == $key){                return $cur->value;            }            $cur = $cur->next;        }        return NULL;    }}Class Node{    public $key;    public $value;    public $next = null;     public function __construct($key, $value, $next = null){        $this->key   = $key;        $this->value = $value;        $this->next  = $next;    }}$hash = new HashTable(200);$hash->insert('apple','this is apple');$hash->insert('orange','this is orange');$hash->insert('banana','this is banana');echo $hash->lookup('apple');

我们知道，在PHP中，数组支持k->v这样的关联数组，也支持普通的数组。不仅支持直接寻址（根据关键字直接定位），而且支持线性遍历（foreach等）。这都要归功于Hash table这一强大和灵活的数据结构。那么，在PHP底层，Hash table究竟是如何实现的呢？我们一步步来看。

1. 基本数据结构

在PHP底层，与Hash table相关的结构定义、算法实现都位于Zend/zend_hash.c和Zend/zend_hash.h这两个文件中。PHP 的hash table实现包括两个重要的数据结构，一个是HashTable,另一个是bucket.前者是hash table的主体，后者则是构成链表的每个“结点”,是真正数据存储的容器。

（1） HashTable的基本结构

定义如下（zend_hash.h）：

typedef struct _hashtable {    uint nTableSize;    uint nTableMask;    uint nNumOfElements;    ulong nNextFreeElement;    Bucket *pInternalPointer;   /* Used for element traversal */    Bucket *pListHead;    Bucket *pListTail;    Bucket **arBuckets;    dtor_func_t pDestructor;    zend_bool persistent;    unsigned char nApplyCount;    zend_bool bApplyProtection;#if ZEND_DEBUG    int inconsistent;#endif} HashTable;

这是一个结构体，其中比较重要的几个成员：

nTableSize 这个成员用于标明Hash表的大小，在hash表初始化操作的时候，会设定nTableSize的大小，而在hash表扩容的时候，也会相应调整这个数值的大小。注意这个数值并不是hash表中元素的个数。

nTableMask 是一个“掩码”，主要用于快速计算一个元素的索引（nIndex = h & ht->nTableMask，在一般的Hash函数中，是通过模运算来确定索引的，但显然，位运算比模运算效率要高），在arBuckets初始化之后，该值默认固定为nTableSize – 1;

nNumOfElements 这个成员保存了hashtable中保存的元素的个数，通常情况下，我们在PHP脚本中使用count($arr)与这个结果是一致的（参见ext/standard/array.c）

nNextFreeElement 这个字段记录下一个可用的索引位置，我们在脚本中使用$array[] = 'key'的时候，就是使用nNextFreeElement给出的索引值（zend_hash.c）：

if (flag & HASH_NEXT_INSERT) {    h = ht->nNextFreeElement;}

pInternalPointer 这是一个指针。在PHP脚本中，我们使用current,next,key,end等 与数组相关的操作时，都是使用pInternalPointer这一指针来完成的。

pListHead 和pListTail PHP底层实际上维护了两个重要的数据结构，除了hash表（以及用于解决冲突的双链表），还有一个双向链表用于hash表元素的线性扫描。pListHead和pListTail便指向这个双链表的表头和表尾。

arBuckets 这是一个bucket *类型的数组，数组中每个元素都是一个bucket* 的指针，具有相同hash值的元素通过bucket的pNext和pLast指针连接成一个双链表（这个双链表与前面说的用于线性遍历的双链表并不是一个东西）。因此，bucket是实际存储数据的容器。

nApplyCount和bApplyProtection 提供了一种保护机制，主要是用于防止循环引用导致的无限递归。

persistent 这是一个布尔变量，该变量会影响到内存分配的方式，这涉及到PHP内存管理的一些知识，我们暂时不做更多解释，详细的可以参考：

http://cn2.php.net/manual/en/internals2.memory.persistence.php

（2）另一个数据结构是Bucket

该结构的定义为：

typedef struct bucket {    ulong h;    uint nKeyLength;    void *pData;    void *pDataPtr;    struct bucket *pListNext;    struct bucket *pListLast;    struct bucket *pNext;    struct bucket *pLast;    const char *arKey;} Bucket;

其中：

h ,arKey,nKeyLength PHP数组中，有两类不同的索引，一类是数字索引，这与C中的数组非常类似(如$arr = array(1=>'cont')), 另一类是字符串索引，也就是使用关键词作为数组项的索引（如$arr = array('index'=>'cont');）.这两类索引在PHP底层是通过不同的机制来区分的：对于数字型索引，直接使用h作为hash值，同时，arKey=NULL 且nKeyLength=0, 而对于字符串索引，arKey保存字符串key, nKeyLength保存该key的长度，h则是该字符串通过hash函数计算后的hash值。这样，在PHP中，实际上通过h, arKey, nKeyLength来唯一确定数组中的一个元素的，这从zend_hash_key这个结构体的定义也可以看出来：

typedef struct _zend_hash_key {    const char *arKey;    uint nKeyLength;    ulong h;} zend_hash_key;

而确定数组元素在hashtable中的位置则是通过h & ht->nTableMask 来实现的：

/* 字符串型索引 */h = zend_inline_hash_func(arKey, nKeyLength);nIndex = h & ht->nTableMask; /* 数字型索引-append $arr[] = 'test';这种形式 */if (flag & HASH_NEXT_INSERT) {    h = ht->nNextFreeElement;}/* 指定数字索引时直接使用h */nIndex = h & ht->nTableMask;

pData和pDataPtr 通常情况下，Bucket中的数据是保存在pData指针指向的内存空间的。但是也有例外，例如保存的是一个指针。这时，pDataPtr指向该指针，而pData指向pDataPtr。这从INIT_DATA这个宏定义可以看出来：

#define INIT_DATA(ht, p, pData, nDataSize);                             \    if (nDataSize == sizeof(void*)) {                                   \        memcpy(&(p)->pDataPtr, pData, sizeof(void *));                  \        (p)->pData=&(p)->pDataPtr;                                      \    }else{                                                              \        (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\if(!(p)->pData){                                                \pefree_rel(p, (ht)->persistent);                            \return FAILURE;                                             \}                                                               \memcpy((p)->pData,pData,nDataSize);                             \(p)->pDataPtr