PHP 內核陣列與雜湊表實作：Vector vs Linked List、HashTable 核心操作 API

PHP 陣列底層為 有序雜湊表，結合 Vector（陣列）與 Linked List（鏈表）優點。本文對比兩種資料結構特性，深入剖析 Zend HashTable 核心 API 與遍歷模式。

Vector（向量/動態陣列）

• 連續記憶體區塊，元素固定間距。
• 隨機存取 O(1)：addr = base + index * element_size。
• 記憶體分配/釋放單次完成，效率高。
• 插入/刪除中間元素需移動後續元素 O(n)。
• PHP 內部應用：zval ***args = safe_emalloc(ZEND_NUM_ARGS(), sizeof(zval**), 0); 函式參數向量。

Linked List（鏈表）

• 節點含 data + next 指標。
• 插入/刪除 O(1)（已知前驅節點）。
• 隨機存取 O(n)，需從頭遍歷。
• 適合 FIFO 佇列、頻繁頭尾操作場景。

PHP HashTable：融合兩者優點

typedef struct _hashtable {
    uint nTableSize;        // 雜湊桶總數 (2 的冪)
    uint nTableMask;        // nTableSize - 1
    uint nNumOfElements;    // 實際元素數
    ulong nNextFreeElement; // 下一個數值索引
    Bucket *pInternalPointer; // 內部指標 (foreach 用)
    Bucket *pListHead;      // 雙向鏈表頭 (維護插入順序)
    Bucket *pListTail;      // 雙向鏈表尾
    Bucket **arBuckets;     // 雜湊桶陣列 (Vector)
    dtor_func_t pDestructor; // 元素析構函式
    zend_bool persistent;   // 持久分配標記
    // ...
} HashTable;

Bucket 結構

typedef struct bucket {
    ulong h;                // 雜湊值 (數值索引或字串雜湊)
    uint nKeyLength;        // 鍵長度 (0 表示數值索引)
    void *pData;            // 指向資料 (zval*)
    void *pDataPtr;         // 直接指向資料 (優化)
    struct bucket *pListNext; // 全域鏈表下一個
    struct bucket *pListLast; // 全域鏈表上一個
    struct bucket *pNext;     // 同桶鏈表下一個 (解決衝突)
    struct bucket *pLast;     // 同桶鏈表上一個
    char arKey[1];          // 可變長度鍵名 (柔性陣列)
} Bucket;

核心操作 API

遍歷模式

1. 內部指標遍歷 (foreach 底層)

zend_hash_internal_pointer_reset(ht);
while (zend_hash_has_more_elements(ht) == SUCCESS) {
    zval **data;
    char *key;
    uint key_len;
    ulong index;
    
    zend_hash_get_current_key_ex(ht, &key, &key_len, &index, 0, NULL);
    zend_hash_get_current_data(ht, (void**)&data);
    
    // 處理 *data
    
    zend_hash_move_forward(ht);
}

2. 回調函式遍歷

zend_hash_apply(ht, (apply_func_t)my_callback TSRMLS_CC);
// my_callback: int (*)(void *pDest TSRMLS_DC)

3. 帶參數回調遍歷

zend_hash_apply_with_argument(ht, (apply_func_arg_t)my_callback, arg TSRMLS_CC);
// my_callback: int (*)(void *pDest, void *arg TSRMLS_DC)

陣列操作實戰：zend_get_parameters_array_ex

int arg_count = ZEND_NUM_ARGS();
zval ***args = safe_emalloc(arg_count, sizeof(zval**), 0);
zend_get_parameters_array_ex(arg_count, args);

for (int i = 0; i < arg_count; i++) {
    php_var_dump(args[i], 1 TSRMLS_CC); // var_dump 每個參數
}
efree(args);

效能建議

• 頻繁查找用 zend_hash_find (O(1) 平均)。
• 需保持順序遍歷時，內部指標遍歷最佳。
• 大量批次插入前預估大小 zend_hash_init(ht, estimated_size, ...) 減少重雜湊。
• 持久陣列 (跨請求) 設定 persistent=1，使用 pemalloc 分配。