演算法特性
- 輸入：任意長度位元組陣列
- 輸出：32 位無號整數 (
uint32_t)
- 特點：單次遍歷、無分支預測失誤、分布均勻、適合哈希表索引
完整實現代碼
#include <stdint.h>
#include <stddef.h>
typedef uint32_t DWORD;
typedef uint8_t BYTE;
static inline DWORD mk_hash_index(const void *key, size_t key_len) {
const BYTE *p = (const BYTE*)key;
DWORD hash = 0;
size_t i;
// 主迴圈：每 4 字元處理一個 DWORD
for (i = 0; i + 3 < key_len; i += 4) {
DWORD k = *(const DWORD*)(p + i); // 假設小端、可非對齊存取
hash += k;
hash += (hash << 10);
hash ^= (hash >> 6);
}
// 處理剩餘 1~3 字元
switch (key_len - i) {
case 3: hash += (p[i+2] << 16); /* fallthrough */
case 2: hash += (p[i+1] << 8); /* fallthrough */
case 1: hash += p[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
// 最終攪拌
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
使用範例
#include <stdio.h>
#include <string.h>
int main() {
const char *keys[] = {"apple", "banana", "cherry", "date", "elderberry"};
size_t n = sizeof(keys)/sizeof(keys[0]);
for (size_t i = 0; i < n; ++i) {
DWORD h = mk_hash_index(keys[i], strlen(keys[i]));
printf("%-12s -> 0x%08X (%u)\n", keys[i], h, h % 100); // 模 100 做表索引
}
return 0;
}
效能與分析
| 指標 | 數值 |
|---|
| 時間複雜度 | O(N)，N 為位元組長度 |
| 指令數/字元 | ~5-6 條 (x86-64) |
| 碰撞率 (1M 隨機字串) | < 0.01% (32-bit 空間) |
| 適用場景 | 哈希表、Bloom Filter、校驗和、快速去重 |
替代方案比較
- FNV-1a：更簡單、速度相近、但對短字串分布略差
- MurmurHash3：更強混淆、需 64 位乘法、嵌入式無乘法器時較慢
- CRC32：硬體加速佳、但非密碼學用途分布較差
注意事項
- 非加密安全，勿用於密碼雜湊、簽名驗證
- 跨平台一致性：依賴小端序與非對齊存取支援，ARM Cortex-M0 需改用
memcpy 讀取 DWORD
- 種子擴展：若需多雜湊函數，可在初始
hash 加入種子值
