萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 內核深度解析:HashTable 如何實現高效陣列

核心結構

PHP 陣列在 Zend 引擎中以 HashTable 實現,結合 雙向鏈表 維持插入順序,支援整數與字串鍵混用,查找/插入/刪除平均 O(1)。

資料結構定義(簡化)

typedef struct _Bucket {
    zval              *val;      // 值指標
    ulong              h;        // 整數鍵或字串雜湊值
    zend_ulong         key;      // 整數鍵
    zend_string       *key_str;  // 字串鍵
    struct _Bucket    *next;     // 雜湊衝突鏈表
    struct _Bucket    *prev;     // 雙向鏈表(維持順序)
} Bucket;

typedef struct _HashTable {
    Bucket           **arData;   // Bucket 陣列(連續記憶體)
    uint32_t           nNumOfElements;
    uint32_t           nTableSize;     // 2 的冪次
    uint32_t           nTableMask;     // nTableSize - 1
    Bucket            *pListHead;      // 雙向鏈表頭
    Bucket            *pListTail;      // 雙向鏈表尾
    // ... 其他欄位
} HashTable;

關鍵操作宏(PHP 7/8)

操作宏/函數說明
初始化陣列array_init(zv)分配 HashTable、設型別 IS_ARRAY
字串鍵插入zend_hash_str_add(ht, key, len, zv)自動計算雜湊、處理衝突
整數鍵插入zend_hash_index_add(ht, idx, zv)直接用整數索引
追加元素zend_hash_next_index_insert(ht, zv)自動分配下一整數索引
查找zend_hash_find(ht, key_str)回傳 zval* 或 nullptr
刪除zend_hash_del(ht, key_str)從雜湊表與鏈表移除

擴充開發實戰:建立回傳陣列

PHP_FUNCTION(my_array_func)
{
    zval *arr;
    array_init(return_value); // return_value 是預設回傳 zval*

    add_assoc_long(return_value, "id", 42);
    add_assoc_string(return_value, "name", "demo");
    add_next_index_long(return_value, 100);
    add_next_index_string(return_value, "auto index");

    // 子陣列
    zval sub;
    array_init(&sub);
    add_assoc_string(&sub, "note", "nested");
    add_assoc_zval(return_value, "sub", &sub);
}

效能特性

  • 記憶體緊湊:Bucket 陣列連續配置,CPU cache 友善。
  • 有序遍歷:雙向鏈表保證 foreach 依插入順序。
  • 自動擴容:負載因子超過閾值時 2x 擴容、重新雜湊。
  • Packed/Hash 兩態:純整數連續索引時為 Packed 陣列(更省記憶體、更快);混合鍵時轉為 Hash 模式。

除錯技巧

安裝 php-ast 或使用 var_dump() 觀察 u(Packed)與 a(Hash)標記;GDB 中可呼叫 zend_hash_display() 列印 HashTable 內部狀態。

copyright © 萬盛學電腦網 all rights reserved