摘要：插入一個(gè)元素時(shí)先將元素按先后順序插入數(shù)組，位置是，再根據(jù)的哈希值映射到散列表中的某個(gè)位置，將存入這個(gè)位置查找時(shí)先在散列表中映射到，得到在數(shù)組的位置，再?gòu)臄?shù)組中取出元素。目前只有兩種類型會(huì)使用這種機(jī)制。

1.變量結(jié)構(gòu)

typedef struct _zval_struct     zval;

typedef union _zend_value {
    zend_long         lval;    //int整形
    double            dval;    //浮點(diǎn)型
    zend_string      *str;     //string字符串
    zend_array       *arr;     //array數(shù)組
    zend_object      *obj;     //object對(duì)象
    zend_resource    *res;     //resource資源類型
    zend_reference   *ref;     //引用類型，通過&$var_name定義的
} zend_value;

struct _zval_struct {
    zend_value        value; //變量實(shí)際的value
    union {
        struct {
            ZEND_ENDIAN_LOHI_4( 
                zend_uchar    type,         //變量類型
                zend_uchar    type_flags,  //類型掩碼，不同的類型會(huì)有不同的幾種屬性，內(nèi)存管理會(huì)用到
                zend_uchar    const_flags,
                zend_uchar    reserved)
        } v;
        uint32_t type_info; //上面4個(gè)值的組合值，可以直接根據(jù)type_info取到4個(gè)對(duì)應(yīng)位置的值
    } u1;
    union {
        uint32_t     var_flags;
        uint32_t     next;  //哈希表中解決哈希沖突時(shí)用到   
        uint32_t     cache_slot;   
        uint32_t     lineno;    
        uint32_t     num_args;    
        uint32_t     fe_pos;  
        uint32_t     fe_iter_idx;
    } u2;
};

2.變量類型

#define IS_UNDEF                    0
#define IS_NULL                     1
#define IS_FALSE                    2
#define IS_TRUE                     3
#define IS_LONG                     4
#define IS_DOUBLE                   5
#define IS_STRING                   6
#define IS_ARRAY                    7
#define IS_OBJECT                   8
#define IS_RESOURCE                 9
#define IS_REFERENCE                10

其中undef、true、false、null沒有value，直接根據(jù)type區(qū)分，而long、double的值則直接存在value中，其他類型為指針

3.字符串

typedef struct _zend_string   zend_string;

struct _zend_string {
    zend_refcounted_h gc;  //變量引用信息，比如當(dāng)前value的引用數(shù)
    size_t            len;  //字符串長(zhǎng)度，通過這個(gè)值保證二進(jìn)制安全
    char              val[1]; //字符串內(nèi)容，變長(zhǎng)struct，分配時(shí)按len長(zhǎng)度申請(qǐng)內(nèi)存
};

4.數(shù)組

typedef struct _zend_array HashTable;
typedef struct _zend_array zend_array;

typedef struct _Bucket {
    zval              val; //存儲(chǔ)的具體value，這里嵌入了一個(gè)zval，而不是一個(gè)指針
    zend_ulong        h;   //哈希值
    zend_string      *key; //key值
} Bucket;

struct _zend_array {
    zend_refcounted_h gc; //引用計(jì)數(shù)信息
    uint32_t          nTableMask;  //計(jì)算bucket索引時(shí)的掩碼，用于散列表的計(jì)算nIndex
    Bucket           *arData;     //bucket數(shù)組
    uint32_t          nNumUsed;   //已用bucket數(shù)
    uint32_t          nNumOfElements; //已有元素?cái)?shù)，nNumOfElements <= nNumUsed，因?yàn)閯h除的并不是直接從arData中移除
    uint32_t          nTableSize; //數(shù)組的大小，為2^n,默認(rèn)為8
    uint32_t          nInternalPointer; //數(shù)值索引,用于HashTable遍歷
    zend_long         nNextFreeElement;//下一個(gè)空閑可用位置的數(shù)字索引
    dtor_func_t       pDestructor;//析構(gòu)函數(shù),銷毀時(shí)調(diào)用的函數(shù)指針
};

HashTable主要依賴arData實(shí)現(xiàn)元素的存儲(chǔ)、索引。插入一個(gè)元素時(shí)先將元素按先后順序插入Bucket數(shù)組，位置是idx，再根據(jù)key的哈希值映射到散列表中的某個(gè)位置nIndex，將idx存入這個(gè)位置；查找時(shí)先在散列表中映射到nIndex，得到value在Bucket數(shù)組的位置idx，再?gòu)腂ucket數(shù)組中取出元素。

$arr["a"] = 1;
$arr["b"] = 2;
$arr["c"] = 3;
$arr["d"] = 4;

unset($arr["c"]);

哈希碰撞:當(dāng)出現(xiàn)沖突時(shí)將原value的位置保存到新value的zval.u2.next中，然后將新value代替原value位置

擴(kuò)容:PHP散列表的大小為2^n，插入時(shí)如果容量不夠則首先檢查已刪除元素所占比例，如果達(dá)到閾值，則將已刪除元素移除，重建索引，如果未到閾值則進(jìn)行擴(kuò)容操作，擴(kuò)大為當(dāng)前大小的2倍，將當(dāng)前Bucket數(shù)組復(fù)制到新的空間，然后重建索引。

重建散列表:當(dāng)刪除元素達(dá)到一定數(shù)量或擴(kuò)容后都需要重建散列表，因?yàn)関alue在Bucket位置移動(dòng)了或哈希數(shù)組nTableSize變化了導(dǎo)致key與value的映射關(guān)系改變，重建過程實(shí)際就是遍歷Bucket數(shù)組中的value，然后重新計(jì)算映射值更新到散列表，移除已刪除的value，將后面未刪除的value依次前移

5.引用

引用是PHP中比較特殊的一種類型，它實(shí)際是指向另外一個(gè)PHP變量，對(duì)它的修改會(huì)直接改動(dòng)實(shí)際指向的zval，可以簡(jiǎn)單的理解為C中的指針，在PHP中通過&操作符產(chǎn)生一個(gè)引用變量，也就是說不管以前的類型是什么，&首先會(huì)創(chuàng)建一個(gè)zend_reference結(jié)構(gòu)，其內(nèi)嵌了一個(gè)zval，這個(gè)zval的value指向原來zval的value(如果是布爾、整形、浮點(diǎn)則直接復(fù)制原來的值)，然后將原zval的類型修改為IS_REFERENCE，原zval的value指向新創(chuàng)建的zend_reference結(jié)構(gòu)。

typedef struct _zend_reference  zend_reference;

struct _zend_reference {
    zend_refcounted_h gc;
    zval              val;
};

6.引用計(jì)數(shù)

typedef struct _zend_refcounted_h {
    uint32_t         refcount;         
    union {
        struct {
            ZEND_ENDIAN_LOHI_3(
                zend_uchar    type,
                zend_uchar    flags,   
                uint16_t      gc_info)  
        } v;
        uint32_t type_info;
    } u;
} zend_refcounted_h;

$a = "time:" . time();   //$a       ->  zend_string_1(refcount=1)
$b = $a;                 //$a,$b    ->  zend_string_1(refcount=2)
$c = $b;                 //$a,$b,$c ->  zend_string_1(refcount=3)

unset($b);               //$b = IS_UNDEF  $a,$c ->  zend_string_1(refcount=2)

并不是所有的數(shù)據(jù)類型都會(huì)用到引用計(jì)數(shù)，long、double直接都是硬拷貝，只有value是指針的那幾種類型(除interned string，immutable array)才能用到引用計(jì)數(shù)?？捎蓏val.u1.type_flag判斷

7.寫時(shí)復(fù)制

$a = array(1,2);
$b = &$a;
$c = $a;

//發(fā)生分離
$b[] = 3;

事實(shí)上只有string、array兩種支持,

8.垃圾回收

PHP變量的回收主要有兩種：主動(dòng)銷毀、自動(dòng)銷毀。主動(dòng)銷毀指的就是 unset ，而自動(dòng)銷毀就是PHP的自動(dòng)管理機(jī)制，在return時(shí)減掉局部變量的refcount，即使沒有顯式的return，PHP也會(huì)自動(dòng)給加上這個(gè)操作，另外一個(gè)就是寫時(shí)復(fù)制時(shí)會(huì)斷開原來value的指向，這時(shí)候也會(huì)檢查斷開后舊value的refcount。

$a = [1];
$a[] = &$a;

unset($a);

unset($a)之前引用關(guān)系：

unset($a)之后：

可以看到，unset($a)之后由于數(shù)組中有子元素指向$a，所以refcount > 0，無法通過簡(jiǎn)單的gc機(jī)制回收，這種變量就是垃圾，垃圾回收器要處理的就是這種情況，目前垃圾只會(huì)出現(xiàn)在array、object兩種類型中，所以只會(huì)針對(duì)這兩種情況作特殊處理：當(dāng)銷毀一個(gè)變量時(shí)，如果發(fā)現(xiàn)減掉refcount后仍然大于0，且類型是IS_ARRAY、IS_OBJECT則將此value放入gc可能垃圾雙向鏈表中，等這個(gè)鏈表達(dá)到一定數(shù)量后啟動(dòng)檢查程序?qū)⑺凶兞繖z查一遍，如果確定是垃圾則銷毀釋放。

目前只有object、array兩種類型會(huì)使用這種機(jī)制。