萬盛學電腦網

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

PHP Hash 算法深度解析:DJBX33A (Times33) 核心原理與優化細節

為什麼關心 Hash 算法?

Hash Table 是 PHP 核心數據結構:陣列、關聯陣列、物件屬性、函數表、符號表 全部基於 Hash Table 實現。Hash 函數品質直接決定陣列操作(插入、查找、遍歷)的效能。

DJBX33A 算法核心

hash(i) = hash(i-1) * 33 + str[i]
// 等價位運算優化:
hash = (hash << 5) + hash + str[i];  // hash * 33 = hash * 32 + hash

初始值 5381(魔數),Daniel J. Bernstein 1991 年提出,被 Apache、Perl、Berkeley DB、PHP 等廣泛採用。

PHP 內核實現 (zend_hash.h)

static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength) {
    register ulong hash = 5381;

    // 循環展開:每次處理 8 字元,減少循環開銷
    for (; nKeyLength >= 8; nKeyLength -= 8) {
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
        hash = ((hash << 5) + hash) + *arKey++;
    }

    // 剩餘 0-7 字元用 switch 處理(無 break 故意貫穿)
    switch (nKeyLength) {
        case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough */
        case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough */
        case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough */
        case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough */
        case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough */
        case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough */
        case 1: hash = ((hash << 5) + hash) + *arKey++; break;
        case 0: break;
    }
    return hash;
}

關鍵優化細節解析

1. 乘法 → 位移加法

hash * 33  ==  (hash << 5) + hash
// 位移比乘法指令快 1-3 倍(視 CPU 架構),編譯器通常會自動優化,
// 但顯式寫出確保所有編譯器一致行為。

2. 循環展開

  • 減少循環條件判斷、計數器更新、跳轉指令
  • 提高指令級並行(ILP),現代超標量 CPU 可並行執行多條獨立加法/位移
  • PHP 選擇 8 字元為單位,平衡代碼膨脹與收益

3. register 關鍵字

建議編譯器將 hash 變量保持在 CPU 寄存器中,避免記憶體存取。現代編譯器通常忽略此提示(自動分配更好),但無副作用。

4. inline 內聯

消除函數調用開銷(壓棧、跳轉、彈棧),對極高頻調用(陣列每次插入/查找)至關重要。

5. 魔數 5381 的數學特性

  • 質數
  • 奇數(保證最低位參與混合)
  • 虧數(真因子和 < 自身)
  • 二進位:10101000000101 — 位模式分散均勻

經驗證明:5381 在實際字串集合上碰撞率極低,優於 0、1、31 等常見初值。

對比:Perl / Apache 實現

// Perl 5.005 (hv.h PERL_HASH)
sub perlhash {
    $hash = 0;
    foreach (split //, shift) {
        $hash = $hash * 33 + ord($_);
    }
    return $hash;
}
// 差異:初值 0、無循環展開、用乘法而非位移

PHP 陣列 Hash 衝突解決:鏈地址法

  • Bucket 陣列 + 鏈表
  • 索引 = hash & (tableSize - 1)(tableSize 為 2 的冪)
  • 衝突時掛在同一 Bucket 鏈表末尾
  • PHP 7+ 引入 zend_ulong h 預計算 hash 存入 Bucket,避免重複計算

實戰驗證:碰撞測試

<?php
function djb33a(string $str): int {
    $h = 5381;
    for ($i = 0, $len = strlen($str); $i < $len; $i++) {
        $h = (($h << 5) + $h) + ord($str[$i]);
    }
    return $h;
}

// 測試 10 萬常見單詞碰撞
$words = file('/usr/share/dict/words', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_ROWS);
$words = array_slice($words, 0, 100_000);

$hashes = [];
$collisions = 0;
foreach ($words as $w) {
    $h = djb33a($w);
    if (isset($hashes[$h])) $collisions++;
    $hashes[$h] = true;
}
echo "唯一 hash: " . count($hashes) . "/100000, 碰撞: $collisions\n";
// 典型輸出:唯一 hash: 99987/100000, 碰撞: 13 (極低)

擴展:PHP 7+ 新 Hash API

<?php
// 通用 hash 函數(支援多種算法)
echo hash('xxh32', 'hello');     // 極快、非加密
echo hash('xxh64', 'hello');     // 64 位版本
echo hash('fnv1a32', 'hello');   // Fowler-Noll-Vo
echo hash('crc32c', 'hello');    // 硬體加速 CRC32C

// 密碼學安全
echo hash('sha256', 'secret');
echo password_hash('secret', PASSWORD_ARGON2ID); // 密碼專用

總結:DJBX33A 以「極簡數學、極致優化」在通用字串集上實現高速、低碰撞。PHP 內核通過循環展開、位移代乘、內聯、寄存器變量、魔數初值將其推向極限。理解這些細節,有助於在設計自定義鍵值存儲、分片算法、一致性哈希時做出更優選擇。

copyright © 萬盛學電腦網 all rights reserved