1.基本概念

1.1 數(shù)組的語義

本質(zhì)上PHP數(shù)組是一個有序字典境蔼，它必須同時滿足以下2個條件：

• 語義一：PHP數(shù)組是一個字典物咳，存儲著鍵-值（key-value）對顺又。通過鍵可以快速地找到對應(yīng)的值萧福，鍵可以是整型一屋，也可以是字符串涨薪。
• 語義二：PHP數(shù)組是有序的骑素。這個有序指的是插入順序，即遍歷數(shù)組的時候刚夺，遍歷元素的順序應(yīng)該和插入順序一致献丑，而不像普通字典一樣是隨機的。

1.2 數(shù)組的概念

PHP的數(shù)組zend_array對應(yīng)的是HashTable光督。HashTable(哈希表)是一種通過某種哈希函數(shù)將特定的鍵映射到特定值的一種數(shù)據(jù)結(jié)構(gòu)阳距，它維護著鍵和值的一一對應(yīng)關(guān)系，并且可以快速地根據(jù)鍵檢索到值结借，查找效率為O(1)筐摘。HashTable的示意如圖下：

HashTable示意圖

說明：

• key：鍵，通過它可以快速檢索到對應(yīng)的value船老。一般是數(shù)字或字符串咖熟。
• value：值，目標(biāo)數(shù)據(jù)柳畔♀晒埽可以是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。
• bucket：桶薪韩，HashTable中存儲數(shù)據(jù)的單元确沸。用來存儲key和value以及輔助信息的容器捌锭。
• slot：槽，HashTable有多個槽罗捎，一個bucket必須從屬于具體的某一個slot观谦，一個slot下可以有多個bucket。
• 哈希函數(shù)：需要自己實現(xiàn)桨菜，在存儲的時候豁状，會對key應(yīng)用哈希函數(shù)確定所在的slot。
• 哈希沖突：當(dāng)多個key經(jīng)過哈希計算后倒得，得出的slot的位置是同一個泻红，那么就叫作哈希沖突。這時霞掺，一般有兩種方法解決沖突——鏈地址法和開放地址法谊路。PHP中采用的是鏈地址法，即將同一個slot中的bucket通過鏈表連接起來根悼。

在具體實現(xiàn)過程中凶异，PHP基于上述基本概念，對bucket以及哈希函數(shù)進行了一些補充挤巡，增加了hash1函數(shù)以生成h值，然后通過hash2函數(shù)散列到不同的slot, 示意圖如下：

php hash table

說明：

• bucket里面增加h字段酷麦。
• 哈希函數(shù)拆分成了hash1和hash2函數(shù)矿卑。hash1將key映射為h值，hash2將h值映射為slot的索引值沃饶。
• bucket里面的key字段作為字符串key母廷，不再表示數(shù)字key。

這個h值的作用是什么呢糊肤？

• HashTable中的key可能是數(shù)字也可能是字符串琴昆，所以在設(shè)計bucket的key時，分為字符串key和數(shù)字
  key馆揉，在上圖中的bucket中业舍，“h”代表數(shù)字key，“key”代表字符串key升酣，對于數(shù)字key舷暮，hash1函數(shù)并沒
  有做任何事情，h值就是數(shù)字key噩茄。
• 每個字符串key下面，經(jīng)過hash1函數(shù)都會計算一個h值〖ㄆ福可以加快字符串之間的比較速度沥割。如果要比較2個
  字符串是否相等耗啦，首先比較這2個key的h值是否相等，如果相等再比對2個key的長度和內(nèi)容机杜。否則可以
  判定不相等芹彬。這樣可以提高HashTable插入，查找速度叉庐。

1.3 php7中h值的計算方法

php7中h的計算(即1.2節(jié)中所說的hash1)采用了DJB hash function舒帮，俗稱“Times33”算法。很多流行的hash map都使用了這種計算方法陡叠，它的思想十分簡單：

h(0) = 任意初始值
h(i) = 33 * h(i-1) + str[i]

一個簡單的c版本實現(xiàn)如下：

unsigned int DJBHash(char* str, unsigned int len)
{
    //初始值
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {   
      //左移5相當(dāng)于*32玩郊，再加一個自身的值就相當(dāng)于*33，用位移替代乘法枉阵，以提高速度
      hash = ((hash << 5) + hash) + (*str);
   }   

   return hash;
}

php7中源碼如下译红，函數(shù)上方還有一大段注釋，講述了一些time33算法的內(nèi)容兴溜，有興趣可以查看侦厚。

//php-7.0.14/Zend/zend_string.h 

static zend_always_inline zend_ulong zend_inline_hash_func(const char *str, size_t len){
    //hash初始值
    register zend_ulong hash = Z_UL(5381);
    /* variant with the hash unrolled eight times */
    //8個一組計算，減少循環(huán)次數(shù)
    for (; len >= 8; len -= 8) {
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
        hash = ((hash << 5) + hash) + *str++;
    }
    //累加字串余下部分(一定小于8)的值
    switch (len) {
        case 7: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 6: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 5: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 4: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 3: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 2: hash = ((hash << 5) + hash) + *str++; /* fallthrough... */
        case 1: hash = ((hash << 5) + hash) + *str++; break;
        case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
    }

    /* Hash value can't be zero, so we always set the high bit */
#if SIZEOF_ZEND_LONG == 8
    return hash | Z_UL(0x8000000000000000);
#elif SIZEOF_ZEND_LONG == 4
    return hash | Z_UL(0x80000000);
#else
# error "Unknown SIZEOF_ZEND_LONG"
#endif
}

2.php7數(shù)組的實現(xiàn)

PHP7通過鏈地址法來解決哈希沖突拙徽，只不過PHP5的鏈表是真實物理存在的鏈表刨沦，鏈表中bucket間的上下游是通過真實存在的指針來維護，而PHP7的鏈表其實是一種邏輯上的鏈表膘怕，所有的bucket都分配在一段連續(xù)的數(shù)組內(nèi)存中想诅，且不再通過指針維護上下游關(guān)系，每一個bucket只維護一個bucket在數(shù)組中的索引(由于內(nèi)存是連續(xù)的岛心，通過索引可以快速定位到bucket)来破，即可完成鏈表上的bucket遍歷。

2.1 基本結(jié)構(gòu)

在PHP 7中忘古，數(shù)組的核心結(jié)構(gòu)是struct _zend_array和bucket徘禁，并且為struct_zend_array起了兩個別名：HashTable和zend_array。

zend_array定義如下：

//php-7.0.14/Zend/zend_types.h

typedef struct _zend_array zend_array;
typedef struct _zend_array HashTable;

typedef struct _Bucket {
    zval              val;
    zend_ulong        h;                /* hash value (or numeric index)   */
    zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

struct _zend_array {    
    zend_refcounted_h gc;
    union {        
        struct {            
            ZEND_ENDIAN_LOHI_4(                
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,                
                zend_uchar    reserve)
        } v;
        uint32_t flags;
    } u;    
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

2.1.1 bucket結(jié)構(gòu)分析

由于不再依賴于物理指針髓堪，整個bucket變得清爽了很多送朱，只有val、h旦袋、key3個字段骤菠。

• val：對應(yīng)HashTable設(shè)計中的value，始終是zval類型疤孕。PHP7將zval嵌入到bucket中商乎，每一個zval只有16個字節(jié)。相比于PHP5的pData和pDataPtr祭阀，所占的字節(jié)數(shù)并沒有增加鹉戚。而且不用再額外申請保存zval的內(nèi)存鲜戒。
• h：對應(yīng)HashTable設(shè)計中的h，表示數(shù)字key或者字符串key的h值抹凳。
• key：對應(yīng)HashTable設(shè)計中的key遏餐，表示字符串key，是一個指向zend_string的指針赢底。

bucket從使用角度可以分為3種：未使用bucket失都、有效bucket、無效bucket幸冻。

• 未使用bucket：最初所有的bucket都是未使用的狀態(tài)粹庞。
• 有效bucket：存儲著有效的數(shù)據(jù)（key、val洽损、h)庞溜，當(dāng)進行插入時，會選擇一個未使用bucket碑定，這樣該bucket就變成了有效bucket流码。更新操作只能發(fā)生在有效bucket上，更新之后延刘，仍然是有效bucket漫试。
• 無效bucket：當(dāng)bucket上存儲的數(shù)據(jù)被刪除時，有效bucket就會變?yōu)闊o效bucket访娶。同時商虐，對于某些場景的插入，除了會生成一個有效bucket外崖疤，還會有副作用，生成多個無效bucket典勇。

在內(nèi)存分布上劫哼，有效bucket和無效bucket會交替分布，但都在未使用bucket的前面割笙。插入的時候永遠在未使用bucket上進行权烧。當(dāng)由于刪除等操作，導(dǎo)致無效bucket非常多伤溉，而有效bucket很少時般码，會對整個bucket數(shù)組進行rehash操作。這樣乱顾，稀疏的有效bucket就會變得連續(xù)而緊密板祝，部分無效bucket會被重新利用而變?yōu)橛行ucket。還有一部分有效bucket和無效bucket會被釋放出來走净，重新變?yōu)槲词褂胋ucket券时。

2.1.2 HashTable結(jié)構(gòu)分析

接下來看看HashTable孤里。

HashTable結(jié)構(gòu)

• gc：垃圾回收，引用計數(shù)相關(guān)字段橘洞。
• arData：實際的存儲容器捌袜。通過指針指向一段連續(xù)的內(nèi)存，存儲著bucket數(shù)組炸枣。
• nTableSize:HashTable的大小虏等。表示arData指向的bucket數(shù)組的大小，即所有bucket的數(shù)量适肠。該字段取值始終是2n霍衫，最小值是8，最大值在32位系統(tǒng)中是0x40000000（230）迂猴，在64位系統(tǒng)中是0x80000000（231）慕淡。
• nNumUsed：指所有已使用bucket的數(shù)量，包括有效bucket和無效bucket的數(shù)量沸毁。在bucket數(shù)組中峰髓，下標(biāo)從0～(nNumUsed-1)的bucket都屬于已使用bucket，而下標(biāo)為nNumUsed～(nTableSize-1)的bucket都屬于未使用bucket息尺。
• nNumOfElements：有效bucket的數(shù)量携兵。該值總是小于或等于nNumUsed。

nTableSize搂誉、nNumUsed徐紧、nNumOfElements三者關(guān)系如下：

nTableSize、nNumUsed炭懊、nNumOfElements三者關(guān)系

• nTableMask：掩碼并级。一般為-nTableSize(負數(shù))。

• nInternalPointer:HashTable的全局默認游標(biāo)侮腹。在PHP7中reset/key/current/next/prev等函數(shù)和該字段有緊密的關(guān)系嘲碧。該值是一個有符號整型，由于所有bucket分配在連續(xù)的內(nèi)存父阻，所以只要維護正在遍歷的bucket在數(shù)組中的下標(biāo)即可愈涩。

• nNextFreeElement:HashTable的自然key。自然key是指HashTable的應(yīng)用語義是純數(shù)組時加矛，插入元素?zé)o須指定key, key會以nNextFreeElement的值為準(zhǔn)履婉。該字段初始值是0。比如$a[] = 1斟览，實際上是插入到key等于0的bucket上毁腿，然后nNextFreeElement會遞增變?yōu)?，代表下一個自然插入的元素的key是1。

• pDestructor：析構(gòu)函數(shù)狸棍。當(dāng)bucket元素被更新或者被刪除時身害，會對bucket的value調(diào)用該函數(shù)，如果value是引用計數(shù)的類型草戈，那么會對value引用計數(shù)減1塌鸯，進而引發(fā)可能的gc。

• u.v.flags：用各個bit來表達HashTable的各種標(biāo)記唐片。共有下面6種flag丙猬，分別對應(yīng)u.v.flags的第1位至第6位。

//php-7.0.14/Zend/zend_hash.h
#define HASH_FLAG_PERSISTENT       (1<<0)   //是否使用持久化內(nèi)存费韭，不使用內(nèi)存池
#define HASH_FLAG_APPLY_PROTECTION (1<<1)   //是否開啟遞歸遍歷保護
#define HASH_FLAG_PACKED           (1<<2)   //是否是packed array
#define HASH_FLAG_INITIALIZED      (1<<3)   //是否已經(jīng)初始化
#define HASH_FLAG_STATIC_KEYS      (1<<4)   //標(biāo)記key為數(shù)字key或者字符串key
#define HASH_FLAG_HAS_EMPTY_IND    (1<<5)   //是否存在空的間接val

• u.v.nApplyCount：遞歸遍歷計數(shù)茧球。為了解決循環(huán)引用導(dǎo)致的死循環(huán)問題，當(dāng)對某數(shù)組進行某種遞歸操作時（比如遞歸count）星持，在遞歸調(diào)用入棧之前將nApplyCount加1抢埋，遞歸調(diào)用出棧之后將nApplyCount減1。當(dāng)循環(huán)引用出現(xiàn)時督暂，遞歸調(diào)用會不斷入棧揪垄，當(dāng)nApplyCount增加到一定閾值時，不再繼續(xù)遞歸下去逻翁，返回一個合法的值饥努，并打印“recursion detected”之類的warning或者error日志。這個閾值一般不大于3八回。
• u.v.nIteratorsCount：迭代器計數(shù)酷愧。PHP中每一個foreach語句都會在全局變量EG中創(chuàng)建一個迭代器，迭代器包含正在遍歷的HashTable和游標(biāo)信息缠诅。該字段記錄了當(dāng)前runtime正在迭代當(dāng)前HashTable的迭代器的數(shù)量溶浴。
• u.v.consistency：成員用于調(diào)試目的，只在PHP編譯成調(diào)試版本時有效管引。

2.1.3 為什么HashTable的掩碼是負數(shù)

PHP 7在分配bucket數(shù)組內(nèi)存時戳葵，在bucket數(shù)組的前面額外多申請了一些內(nèi)存，這段內(nèi)存是一個索引數(shù)組（也叫索引表）汉匙，數(shù)組里面的每個元素代表一個slot，存放著每個slot鏈表的第一個bucket在bucket數(shù)組中的下標(biāo)生蚁。如果當(dāng)前slot沒有任何bucket元素噩翠，那么索引值為-1。而為了實現(xiàn)邏輯鏈表邦投，由于bucket元素的val是zval, PHP 7通過bucket.val.u2.next表達鏈表中下一個元素在數(shù)組中的下標(biāo)伤锚，如下圖（n等于nTableSize）所示。

索引

這里一個非常巧妙的設(shè)計是索引數(shù)組仍然通過HashTable.arData來引用志衣。由于索引數(shù)組和bucket數(shù)組是連續(xù)的內(nèi)存屯援，因此arData[0...n-1]表示bucket數(shù)組元素猛们，((uint32_t*) (arData))[-1...-n]表示索引數(shù)組元素。因此在計算bucket屬于哪個slot時狞洋，要做的就是確定它在索引數(shù)組中的下標(biāo)弯淘，而這個下標(biāo)是從-n～-1的負數(shù)，分別代表slot1到slotN吉懊。

為了得到介于[-n, -1]之間的負數(shù)的下標(biāo)庐橙，PHP7的HashTable設(shè)計中的hash2函數(shù)（根據(jù)h值取得slot值）是這樣的（其中nIndex就是slot值）：

nIndex = h | ht->nTableMask;

以nTableSize=8為例，nTableMask=-8借嗽，二進制表示是：

11111111111111111111111111111000

任何整數(shù)和它進行按位或之后的結(jié)果只有以下8種态鳖，這恰好滿足[-n, -1]的取值范圍：

11111111111111111111111111111000    //-8
11111111111111111111111111111001    //-7
11111111111111111111111111111010    //-6
11111111111111111111111111111011    //-5
11111111111111111111111111111100    //-4
11111111111111111111111111111101    //-3
11111111111111111111111111111110    //-2
11111111111111111111111111111111    //-1

2.2 packed array和hash array的區(qū)別

PHP數(shù)組有兩種用法:

• 純數(shù)組
• 基于key-value的map

例如：

$a = [1, 2, 3];   //純數(shù)組
$b = ["a" => 1, "b" => 2, "c" => 3];  //map

對于上面的兩種用法，PHP7引申出了 Packed Array 和 Hash Array的概念恶导。當(dāng)HashTable的u.v.flags & HASH_FALG_PACKED > 0時浆竭，表示當(dāng)前數(shù)組是Packed Array，否則是Hash Array惨寿。

2.2.1 內(nèi)存的本質(zhì)區(qū)別

packed array和hash array的區(qū)別在哪里呢邦泄？先看下面兩段代碼：

//array1.php
$start = memory_get_usage();
$test = [];
for($i=0; $i<=200000; $i++){
    $test[$i] = $i;
}

$end = memory_get_usage();

echo $end - $start, "\n"

//array2.php
$start = memory_get_usage();
$test = [];
for($i=200000; $i>=0; $i--){
    $test[$i] = $i;
}
$end = memory_get_usage();

echo $end - $start, "\n";

運行結(jié)果如下：

php array1.php
8392840

php array2.php
9437320

array2.php比array1.php多使用了1M左右內(nèi)存，這是為什么呢缤沦？原因就在于這兩種寫法虎韵，test數(shù)組的內(nèi)存結(jié)構(gòu)是有區(qū)別的，一種是packed array缸废，另一種是hash array包蓝。

2.2.2 packed array

packed array具有以下約束和特性。

• key全是數(shù)字key企量。
• key按插入順序排列测萎，必須是遞增的。
• 每一個key-value對的存儲位置都是確定的届巩，都存儲在bucket數(shù)組的第key個元素上硅瞧。
• packed array不需要索引數(shù)組。

它實際上利用了bucket數(shù)組的連續(xù)性特點恕汇，對于某些只有數(shù)字key的場景進行的優(yōu)化腕唧。由于不再需要索引數(shù)組，從內(nèi)存空間上節(jié)省了(nTableSize-2 )*sizeof(uint32_t) 個字節(jié)瘾英。另外枣接，由于存取bucket是直接操作bucket數(shù)組，在性能上也有所提升缺谴。

接下來我們看下本小節(jié)開頭舉的例子但惶，array1.php中test的key都是數(shù)字key，且key插入順序為0，1膀曾，2,滿足遞增的特性县爬，所以它是Packed Array。示意圖如下:

packed array

說明：

• u.v.flag：30添谊，對應(yīng)二進制11110财喳。含義如下：

  
  
  u.v.flag

• nTableSize：必須是2的n次方。數(shù)組元素有200001個碉钠，所以最小的nTableSize為2^18 = 2672144纲缓。

• nTableMask: 對于packed數(shù)組，固定-2喊废。因為其實不需要索引祝高。

2.2.3 hash array

hash array依賴索引數(shù)組來維護每一個slot鏈表中首元素在bucket數(shù)組中的下標(biāo)。對array2.php污筷，$test的key不是遞增的工闺，因此它不是packed array，而是hash array瓣蛀。示意圖如下：

hash array

• u.v.flag：26陆蟆，對應(yīng)二進制11010。含義如下：

  
  
  u.v.flag
• nTableSize：必須是2的n次方惋增。數(shù)組元素有200001個叠殷，所以最小的nTableSize為2^18 = 2672144。
• nTableMask: 通常為-nTableSize诈皿， 所以值為-262144
• 對于數(shù)字key, 直接將key作為h值林束，不再使用額外的hash函數(shù)，所以我們看到bucket中存儲的val.lval值與h相同稽亏。

下面以$test[199999]為例壶冒，說明hash方式如何尋找其值。

• h = key = 199999
• index = h | nTableMask = 199999 | -262144 = -62145
• 在索引區(qū)查到-62145存儲的值為1截歉，說明值存儲在bucket數(shù)組的第1個元素中胖腾。
• bukcet[1].val.lval = 199999

2.2.4 幾個例子

$a = [1=>'a', 3=>'b', 5=>'c'];  //packed array
$b = [1=>'a', 5=>'c', 3=>'b'];  //hash array
    
$c = [1=>'a', 8=>'b'];  //hash array

說明：

• $b: key沒有遞增，所以形成了hash array
• c為什么不是packed array呢宵睦？其實理論上是可以的性宏，但如果按packed array插入的話，會比較浪費空間状飞。如下圖所示：
  
  浪費空間

bucket數(shù)組中下標(biāo)為2～7的6個bucket為了保持packed array特性，無法再插入元素，成為浪費的空間诬辈。因此酵使，PHP 7會在packed array的空間效率以及時間效率優(yōu)化與空間浪費之間做一個平衡，當(dāng)空間浪費比較多的時候焙糟，PHP 7會將packed array轉(zhuǎn)化為hash array口渔，變成下面的樣子：

轉(zhuǎn)化為hash array

2.3 哈希沖突的解決

數(shù)據(jù)在插入HashTable時，不同的key經(jīng)過哈希函數(shù)得到的值可能相同穿撮，導(dǎo)致插入索引數(shù)組沖突缺脉，理論上需要在索引數(shù)組外再加一個鏈表把所有沖突的value以雙鏈表的形式關(guān)聯(lián)起來，然后讀取的時候去遍歷這個雙鏈表中的數(shù)據(jù)悦穿，比較對應(yīng)的key攻礼。

PHP7的hash array的做法是，不單獨維護一個雙鏈表栗柒，而是把每個沖突的idx存儲在bucket的zval.u2.next中礁扮，插入的時候把老的value存儲的地址（idx）放到新value的next中，再把新value的存儲地址更新到索引數(shù)組中瞬沦。

舉個例子太伊，假如順次插入的第1、2逛钻、3元素, 它們的h|nTableMask相同僚焦，均為-6， 發(fā)生哈希沖突芳悲，那么解決方法如下圖所示：

沖突解決

2.4 擴容和rehash操作

在hash array中unset一個key的時候并不會真正觸發(fā)刪除屡江，是只做一個標(biāo)記，刪除是在擴容和rehash(重建索引)的時候才會觸發(fā)惩嘉。插入時觸發(fā)擴容及rehash的整體流程如下圖所示：

插入流程

說明：

• array的容量分配是固定的毫别，初始化時每次申請的是2n的容量痛倚，容量的最小值為23，最大值為0x80000000耸峭。
• 當(dāng)容量足夠時直接執(zhí)行插入操作桩蓉。
• 當(dāng)容量不夠時（nNumUsed >=nTableSize）院究，檢查已刪除元素所占的比例，假如達到閾值

ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)

則將已刪除元素從HashTable中移除伙窃，并重建索引(rehash)样漆。如果未到閾值，則要進行擴容操作鳍怨，新的容量擴大到當(dāng)前大小的2倍（即2*nTableSize）跪妥，將當(dāng)前bucket數(shù)組復(fù)制到新的空間骗奖，然后重建索引。

相關(guān)源碼如下：

//php-7.0.14/Zend/zend_hash.c
static void ZEND_FASTCALL zend_hash_do_resize(HashTable *ht)
{
    IS_CONSISTENT(ht);
    HT_ASSERT(GC_REFCOUNT(ht) == 1);
    
    if (ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)) { /* additional term is there to amortize the cost of compaction */
        HANDLE_BLOCK_INTERRUPTIONS();
        //觸發(fā)條件鄙皇，重建索引伴逸，以便釋放空間
        zend_hash_rehash(ht);
        HANDLE_UNBLOCK_INTERRUPTIONS();
    } 
    //將現(xiàn)有空間翻倍
    else if (ht->nTableSize < HT_MAX_SIZE) {  /* Let's double the table size */
        //獲取新舊arData位置
        void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
        //此時nsize為2*nTableSize膘壶，加法比*2快
        uint32_t nSize = ht->nTableSize + ht->nTableSize;
        Bucket *old_buckets = ht->arData;

        HANDLE_BLOCK_INTERRUPTIONS();        
        //申請新的數(shù)組內(nèi)存大小
        new_data = pemalloc(HT_SIZE_EX(nSize, -nSize), ht->u.flags & HASH_FLAG_PERSISTENT);
        
        //設(shè)置新的table大小
        ht->nTableSize = nSize;
        //hash array中颓芭，nTableMask等于-nTableSize
        ht->nTableMask = -ht->nTableSize;
        //設(shè)置新的arData位置
        HT_SET_DATA_ADDR(ht, new_data);
        //拷貝舊的bucket數(shù)組數(shù)據(jù)到新的arData
        memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
        //釋放舊的arData數(shù)據(jù)
        pefree(old_data, ht->u.flags & HASH_FLAG_PERSISTENT);
        //重建索引
        zend_hash_rehash(ht);
        HANDLE_UNBLOCK_INTERRUPTIONS();
    } else {
        //內(nèi)存不夠，報錯
        zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%zu * %zu + %zu)", ht->nTableSize * 2, sizeof(Bucket) + sizeof(uint32_t), sizeof(Bucket));
    }
}

下面我們對rehash作更詳細的說明：

• rehash對應(yīng)源碼中的zend_hash_rehash(ht)方法官紫。
• rehash的主要功能就是把HashTable bucket數(shù)組中標(biāo)識為IS_UNDEF的數(shù)據(jù)剔除州藕，把有效數(shù)據(jù)重新聚合到bucket數(shù)組并更新插入索引表床玻。
• rehash不重新申請存內(nèi)存，整個過程是在原有結(jié)構(gòu)上做聚合調(diào)整贫堰。具體實現(xiàn)步驟如下：

1. 重置所有nIndex數(shù)組為-1；
2. 初始化兩個bucket類型的指針p粱檀、q，循環(huán)遍歷bucket數(shù)組压彭；
3. 每次循環(huán)壮不，p++，遇到第一個IS_UNDEF時隐孽，q=p健蕊；繼續(xù)循環(huán)數(shù)組；
4. 當(dāng)再一次遇到一個正常數(shù)據(jù)時晴及，把正常數(shù)據(jù)拷貝到q指向的位置嫡锌，q++势木；
5. 直到遍歷完數(shù)組，更新nNumUsed等計數(shù)溯壶。

下面來看源碼

//php-7.0.14/Zend/zend_hash.c

ZEND_API int ZEND_FASTCALL zend_hash_rehash(HashTable *ht)
{
    Bucket *p;
    uint32_t nIndex, i;

    IS_CONSISTENT(ht);
    
    //數(shù)組里沒有元素
    if (UNEXPECTED(ht->nNumOfElements == 0)) {
        if (ht->u.flags & HASH_FLAG_INITIALIZED) {            
            ht->nNumUsed = 0;
            //索引區(qū)的值均置為HT_INVALID_IDX(-1)
            HT_HASH_RESET(ht);
        }
        return SUCCESS;
    }

    HT_HASH_RESET(ht);
    i = 0;
    p = ht->arData;
    /*
     * 數(shù)組里沒有刪除的元素
     * 重新計算索引數(shù)組即可
     */
    if (ht->nNumUsed == ht->nNumOfElements) {
        do {
            nIndex = p->h | ht->nTableMask;
            //zval.u2.next記錄開鏈(有hash沖突的情況)
            Z_NEXT(p->val) = HT_HASH(ht, nIndex);
            //在索引區(qū)(nIndex處)記錄當(dāng)前元素位置
            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
            p++;
        } while (++i < ht->nNumUsed);
    }
    else{
        do{
            /*此時表明有已刪除元素
             *則將后面的value依次前移茸塞，壓實Bucket數(shù)組
             */
            if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) {
                //j記錄了當(dāng)前實際有效元素的個數(shù)
                uint32_t j = i;                
                //q記錄下第一個被刪除元素的位置
                Bucket *q = p;
                
                ... ...
                
                while (++i < ht->nNumUsed) {
                    p++;
                    //p碰到非IS_UNDEF元素時查剖，將其復(fù)制到q所指的位置
                    if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) {
                        ZVAL_COPY_VALUE(&q->val, &p->val);
                        q->h = p->h;
                        nIndex = q->h | ht->nTableMask;
                        q->key = p->key;
                        Z_NEXT(q->val) = HT_HASH(ht, nIndex);
                        HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j);
                        if (UNEXPECTED(ht->nInternalPointer == i)) {
                            ht->nInternalPointer = j;
                        }
                        //q向前移動
                        q++;
                        //有效元素增加一個
                        j++;
                    }
                }
            
                ... ...
                //數(shù)據(jù)被壓實了笋庄，所以ht->nNumUsed即為當(dāng)前有效元素的個數(shù)
                ht->nNumUsed = j;
                break;
            }
            
            //未碰到IS_UNDEF元素前走此邏輯倔监，只需要重算索引
            nIndex = p->h | ht->nTableMask;
            Z_NEXT(p->val) = HT_HASH(ht, nIndex);
            HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i);
            p++;
        }while (++i < ht->nNumUsed);
    }
    
     return SUCCESS;
}

來看一個例子：

//生成hash array
for($i=7; $i>=0; $i--){
    $arr[$i] = $i * 10;
}

//產(chǎn)生空洞
unset($arr[3]);
unset($arr[4]);
unset($arr[5]);

/*
 * ht->nNumUsed = 8
 * ht->nNumOfElements = 5
 * 插入新元素滿足ht->nNumUsed > ht->nNumOfElements + (ht->nNumOfElements >> 5)
 * 所以觸發(fā)rehash
 */
$arr[11] = 110;

rehash之前

rehash之前

rehash之后

rehash之后

值得注意的是，rehash后济丘，bucket數(shù)組中第6摹迷，7兩個位置存儲的值依然在，只是索引中找不到他們的位置近哟。另外使用gdb可看到nNumUsed = 6鲫寄，也表明6地来，7兩個位置是未使用的。

2.5 packed array與hash array的轉(zhuǎn)換

轉(zhuǎn)換代碼如下：

//packed array 轉(zhuǎn)hash array
ZEND_API void ZEND_FASTCALL zend_hash_packed_to_hash(HashTable *ht)
{
    //獲取新舊arData數(shù)據(jù)位置
    void *new_data, *old_data = HT_GET_DATA_ADDR(ht);
    //記錄原有的ht->arData位置
    Bucket *old_buckets = ht->arData;

    HT_ASSERT(GC_REFCOUNT(ht) == 1);
    HANDLE_BLOCK_INTERRUPTIONS();
    
    //去掉packed array標(biāo)記
    ht->u.flags &= ~HASH_FLAG_PACKED;
    //為新hash array申請bucket數(shù)組空間
    new_data = pemalloc(HT_SIZE_EX(ht->nTableSize, -ht->nTableSize), (ht)->u.flags & HASH_FLAG_PERSISTENT);
    //重新設(shè)置ht->nTableMask（packed array的nTableMask為-2,所以要重設(shè)）
    ht->nTableMask = -ht->nTableSize;
    //ht->arData指向新地址
    HT_SET_DATA_ADDR(ht, new_data);
    //拷貝舊數(shù)據(jù)到新的arData
    memcpy(ht->arData, old_buckets, sizeof(Bucket) * ht->nNumUsed);
    //釋放老的arData空間
    pefree(old_data, (ht)->u.flags & HASH_FLAG_PERSISTENT);
    //重建索引
    zend_hash_rehash(ht);
    HANDLE_UNBLOCK_INTERRUPTIONS();
}

下面我們結(jié)合gdb看一個轉(zhuǎn)換的例子，php代碼如下：

//hash.php

$arr[] = 'foo';
echo "packed array\n";
var_dump($arr);
$arr['a'] = 'bar';
echo "hash array\n";
var_dump($arr);

在命令行下執(zhí)行g(shù)db php颂碧， 進入gdb調(diào)試载城。

/*在var_dump處設(shè)置斷點诉瓦，查看數(shù)組變化*/
b php_var_dump
Breakpoint 1 at 0x597040: file /usr/local/src/php-7.0.14/ext/standard/var.c, line 79.

(gdb) run hash.php 
packed array

Breakpoint 1, php_var_dump (struc=0x7ffff7813160, level=1) at /usr/local/src/php-7.0.14/ext/standard/var.c:79
79      {

//struc即是$arr
(gdb) p struc
$1 = (zval *) 0x7ffff7813160

(gdb) p *struc.value.arr
$3 = {gc = {refcount = 2, u = {v = {type = 7 '\a', flags = 0 '\000', gc_info = 0}, type_info = 7}}, u = {v = {
      flags = 30 '\036', nApplyCount = 0 '\000', nIteratorsCount = 0 '\000', reserve = 0 '\000'}, flags = 30}, 
  nTableMask = 4294967294, arData = 0x7ffff785c788, nNumUsed = 1, nNumOfElements = 1, nTableSize = 8, nInternalPointer = 0, 
  nNextFreeElement = 1, pDestructor = 0x62faa0 <_zval_ptr_dtor>}

• flag=30：說明是packed數(shù)組(參見5.3.3.2 packed array)
• nNumOfElements=1：有一個元素
• nTableMask=4294967294：gdb是用無符號整數(shù)顯示的值睬澡，轉(zhuǎn)成int即為-2。符合packed array的特征斗躏。

//查看第0個元素內(nèi)容為foo昔脯，符合預(yù)期
(gdb) p *struc.value.arr.arData[0].val.value.str.val@3
$3 = "foo"

接下來查看變成hash的arr

(gdb) c
Continuing.
array(1) {
  [0]=>

Breakpoint 1, php_var_dump (struc=0x7ffff785c788, level=3) at /usr/local/src/php-7.0.14/ext/standard/var.c:79
79      {
(gdb) c
Continuing.
  string(3) "foo"
}
//輸出hash array后，說明是插入a=bar的$arr了
hash array

Breakpoint 1, php_var_dump (struc=0x7ffff7813160, level=1) at /usr/local/src/php-7.0.14/ext/standard/var.c:79
79      {

(gdb) p *struc.value.arr
$7 = {gc = {refcount = 2, u = {v = {type = 7 '\a', flags = 0 '\000', gc_info = 0}, type_info = 7}}, u = {v = {
      flags = 26 '\032', nApplyCount = 0 '\000', nIteratorsCount = 0 '\000', reserve = 0 '\000'}, flags = 26}, 
  nTableMask = 4294967288, arData = 0x7ffff785c8e0, nNumUsed = 2, nNumOfElements = 2, nTableSize = 8, nInternalPointer = 0, 
  nNextFreeElement = 1, pDestructor = 0x62faa0 <_zval_ptr_dtor>}

• flags=26：說明類型是hash array
• nNumOfElements=2：有兩個元素
• nTableMask=4294967288: 有符號的-8, 剛好是-nTableSize沈堡， 符合預(yù)期燕雁。
• 比較轉(zhuǎn)換前后arData指向的地址：0x7ffff785c788拐格，0x7ffff785c8e0說明的確是申請的新的空間。

(gdb) p struc.value.arr.arData[0]
//第0個元素h=0
$11 = {val = {value = {lval = 140737345758432, dval = 6.9533487626122526e-310, counted = 0x7ffff78024e0, 
      str = 0x7ffff78024e0, arr = 0x7ffff78024e0, obj = 0x7ffff78024e0, res = 0x7ffff78024e0, ref = 0x7ffff78024e0, 
      ast = 0x7ffff78024e0, zv = 0x7ffff78024e0, ptr = 0x7ffff78024e0, ce = 0x7ffff78024e0, func = 0x7ffff78024e0, ww = {
        w1 = 4152370400, w2 = 32767}}, u1 = {v = {type = 6 '\006', type_flags = 0 '\000', const_flags = 0 '\000', 
        reserved = 0 '\000'}, type_info = 6}, u2 = {var_flags = 4294967295, next = 4294967295, cache_slot = 4294967295, 
      lineno = 4294967295, num_args = 4294967295, fe_pos = 4294967295, fe_iter_idx = 4294967295}}, h = 0, key = 0x0}
//第0個元素內(nèi)容foo
(gdb) p *struc.value.arr.arData[0].val.value.str.val@3
$12 = "foo"

//第1個元素h=9223372036854953478
(gdb) p struc.value.arr.arData[1]
$13 = {val = {value = {lval = 140737345758560, dval = 6.9533487626185766e-310, counted = 0x7ffff7802560, 
      str = 0x7ffff7802560, arr = 0x7ffff7802560, obj = 0x7ffff7802560, res = 0x7ffff7802560, ref = 0x7ffff7802560, 
      ast = 0x7ffff7802560, zv = 0x7ffff7802560, ptr = 0x7ffff7802560, ce = 0x7ffff7802560, func = 0x7ffff7802560, ww = {
        w1 = 4152370528, w2 = 32767}}, u1 = {v = {type = 6 '\006', type_flags = 0 '\000', const_flags = 0 '\000', 
        reserved = 0 '\000'}, type_info = 6}, u2 = {var_flags = 4294967295, next = 4294967295, cache_slot = 4294967295, 
      lineno = 4294967295, num_args = 4294967295, fe_pos = 4294967295, fe_iter_idx = 4294967295}}, h = 9223372036854953478, 
  key = 0x7ffff7802540}
//第一個元素內(nèi)容為bar
(gdb) p *struc.value.arr.arData[1].val.value.str.val@3
$14 = "bar"
//第一個元素key為a
(gdb) p *struc.value.arr.arData[1].key
$16 = {gc = {refcount = 0, u = {v = {type = 6 '\006', flags = 2 '\002', gc_info = 0}, type_info = 518}}, 
  h = 9223372036854953478, len = 1, val = "a"}

下面來看看索引區(qū)

/* 第0個元素, h=0角撞，0|-8= -8, 所以index為-8
 * 查看索引數(shù)組第8個位置谒所，存儲的索引為0
 */
(gdb) p ((uint32_t *)struc.value.arr.arData)[-8]
$17 = 0
/* 第1個元素, h=9223372036854953478, 9223372036854953478|-8 = -2, 所以index為-2
 * 查看索引數(shù)組第2個位置，存儲的索引為1
 */
(gdb) p ((uint32_t *)struc.value.arr.arData)[-2]
$18 = 1

3. 一些啟示

1. 以后對字串進行hash姐军，除了md5尖淘，還可以考慮time33
2. 數(shù)組擴容和packed array轉(zhuǎn)換為hash array時會觸發(fā)rehash村生，這是個耗費cpu的操作。
3. 當(dāng)數(shù)組特別大時辽话，要小心擴容的邊界卫病，在邊界上蟀苛，多出一個元素，就可能讓你的內(nèi)存增大一倍础废。