萬盛學電腦網

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

PHP 與 Perl 共用的 DJBX33A 雜湊演算法深度解析

前言:APR 預設雜湊函數的由來

APR (Apache Portable Runtime) 採用的預設雜湊演算法 DJBX33A (Daniel J. Bernstein, Times 33 with Addition),源自 Daniel J. Bernstein 提出的 "Times 33" 演算法,廣泛應用於 Perl 語言內部雜湊表與 Berkeley DB。本文將剖析其 C 原始碼邏輯與效能優勢。

核心原始碼走讀

unsigned int hash = 0;
const unsigned char *key = (const unsigned char *)char_key;
const unsigned char *p;
apr_ssize_t i;

if (*klen == APR_HASH_KEY_STRING) {
    for (p = key; *p; p++) {
        hash = hash * 33 + *p;
    }
    *klen = p - key;
} else {
    for (p = key, i = *klen; i; i--, p++) {
        hash = hash * 33 + *p;
    }
}
return hash;

演算機制解析

  • 初始值:hash = 0
  • 迴圈核心:hash = hash * 33 + 當前字元 ASCII 值
  • 兩種模式:
    • 字串模式 (APR_HASH_KEY_STRING):遇到 \0 結束,並回傳字串長度。
    • 指定長度模式:依 klen 處理固定位元組,支援含 \0 的二進位資料。

為何選擇乘數 33?歷史與效能考量

註解引用 Ralf S. Engelschall 說明:

  1. 分布均勻:1~256 中 128 個奇數 (除 1 外) 分布表現相近,平均填充率約 86%。
  2. 速度優勢:33、17、31、63、127、129 等數字的乘法可轉換為 位移 + 加減法:
    hash * 33 = (hash << 5) + hash
    在無硬體乘法器的早期 CPU 上極快,現代 CPU 仍受益於指令級並行。
  3. 歷史淵源:Chris Torek 1990 年於 Usenet comp.lang.c 發表,後被 Berkeley DB 採用,Perl 沿用至今。

PHP 開發者的啟示

雖然 PHP 內建 hash() 提供更強雜湊 (SHA256 等),但理解 DJBX33A 有助於:

  • 實作自訂雜湊表、快取鍵值生成時,選擇輕量高效的演算法。
  • 閱讀底層擴充套件 (如 Redis、Memcached PHP 擴充) 原始碼時,識別其雜湊策略。
  • 面試時展示對經典演算法「時空權衡」的深度理解。

此演算法以極簡代碼兼顧速度與分布,是演算法設計「簡單即是美」的經典範例。

copyright © 萬盛學電腦網 all rights reserved