BijectiveHash（雙射哈希，即可逆哈希）的設計精髓在于它借鑒了現代密碼學和高性能哈希函數中的核心思想，但目標并非加密，而是實現一種無沖突、可逆的置換（Permutation）。

可逆哈希是什么，用來做什么？

首先要明確，它和我們通常說的用于哈希表或數據校驗的哈希函數（如?Hash64）完全不同。

• 普通哈希：是多對一的，輸入空間遠大于輸出空間，必然存在沖突（多個不同輸入產生相同輸出），并且是單向的（不可逆）。
• 可逆哈希：是一對一的，輸入和輸出空間大小相同，絕無沖突，并且是雙向的（可逆的）。

它的主要用途是數據混淆（Obfuscation）或ID置換。比如，你有一組從0開始連續的ID（0, 1, 2, ...），但你不想直接暴露它們，希望把它們變成一組看起來毫無規律、隨機分布的ID，同時還能在需要時恢復成原始ID。這時可逆哈希就派上用場了。

BijectiveHash2x64?設計精髓分析

這個函數的設計巧妙地改編自?XXH3?哈希算法中處理小數據塊的部分。XXH3為了達到雪崩效應，混合極其充分，而BijectiveHash則利用了這種充分混合的特性，并確保每一步操作都是可逆的。

我們來看它的核心代碼：

hash.cc

// ... existing code ...
void BijectiveHash2x64(uint64_t in_high64, uint64_t in_low64, uint64_t seed,uint64_t* out_high64, uint64_t* out_low64) {// Adapted from XXH3_len_9to16_128bconst uint64_t bitflipl = /*secret part*/ 0x59973f0033362349U - seed;const uint64_t bitfliph = /*secret part*/ 0xc202797692d63d58U + seed;Unsigned128 tmp128 =Multiply64to128(in_low64 ^ in_high64 ^ bitflipl, 0x9E3779B185EBCA87U);uint64_t lo = Lower64of128(tmp128);uint64_t hi = Upper64of128(tmp128);lo += 0x3c0000000000000U;  // (len - 1) << 54in_high64 ^= bitfliph;hi += in_high64 + (Lower32of64(in_high64) * uint64_t{0x85EBCA76});lo ^= EndianSwapValue(hi);tmp128 = Multiply64to128(lo, 0xC2B2AE3D27D4EB4FU);lo = Lower64of128(tmp128);hi = Upper64of128(tmp128) + (hi * 0xC2B2AE3D27D4EB4FU);*out_low64 = XXH3_avalanche(lo);*out_high64 = XXH3_avalanche(hi);
}
// ... existing code ...

設計精髓 1：保證無信息丟失的操作

要實現可逆，最關鍵的一點是任何操作都不能丟失信息。

• Multiply64to128：這是整個設計的核心。普通的64位乘法?uint64_t * uint64_t?的結果仍然是?uint64_t，這會丟失高64位的信息，導致不可逆。而?Multiply64to128?將兩個64位整數相乘，產生一個完整的128位結果（Unsigned128），完整保留了所有信息。這是可逆性的數學基礎。
• XOR (^) 和加法 (+)：這些操作本身就是可逆的。a ^ b?可以通過再異或一次?b?恢復?a。a + b?可以通過減去?b?恢復?a。

設計精髓 2：借鑒密碼學的“混淆”與“擴散”

為了讓輸出看起來隨機，它借鑒了密碼學中的兩個重要概念：

• 混淆（Confusion）：讓輸入和輸出之間的關系變得盡可能復雜。
  • 通過與seed相關的密鑰（bitflipl,?bitfliph）進行XOR操作。
  • 與大的素數（0x9E3779B185EBCA87U?等）相乘。
• 擴散（Diffusion）：讓輸入的任何一位微小變化都能影響到輸出的多位（雪崩效應）。
  • lo ^= EndianSwapValue(hi)：這是一個類似Feistel網絡的結構。它用一部分數據（hi）去改變另一部分數據（lo），然后再用改變后的lo去影響hi的計算。這種交叉影響能迅速地將輸入的變化擴散到整個128位狀態中。
  • XXH3_avalanche：最后調用XXH3的雪崩函數，進行最終的、徹底的混合，確保最終輸出的隨機性。

設計精髓 3：可逆的雪崩函數

XXH3_avalanche?本身是一個單向函數，但設計者巧妙地為它實現了一個逆函數?XXH3_unavalanche。

// ... existing code ...
inline uint64_t XXH3_avalanche(uint64_t h64) {h64 ^= h64 >> 37;h64 *= 0x165667919E3779F9U;h64 ^= h64 >> 32;return h64;
}inline uint64_t XXH3_unavalanche(uint64_t h64) {h64 ^= h64 >> 32;h64 *= 0x8da8ee41d6df849U;  // inverse of 0x165667919E3779F9Uh64 ^= h64 >> 37;return h64;
}
// ... existing code ...

這里的關鍵是?0x8da8ee41d6df849U，它是?0x165667919E3779F9U?在模?2^64?意義下的乘法逆元。這意味著?(a * b) * b_inverse = a (mod 2^64)。通過找到這個逆元，乘法步驟就變得可逆了。而XOR和移位操作的逆運算也相對直接。

BijectiveUnhash2x64：逆向工程的藝術

逆向函數?BijectiveUnhash2x64?的實現完美展示了如何一步步“撤銷”正向函數的操作。

// ... existing code ...
void BijectiveUnhash2x64(uint64_t in_high64, uint64_t in_low64, uint64_t seed,uint64_t* out_high64, uint64_t* out_low64) {// Inverted above (also consulting XXH3_len_9to16_128b)const uint64_t bitflipl = /*secret part*/ 0x59973f0033362349U - seed;const uint64_t bitfliph = /*secret part*/ 0xc202797692d63d58U + seed;uint64_t lo = XXH3_unavalanche(in_low64);uint64_t hi = XXH3_unavalanche(in_high64);// ... a series of inverse multiplications, subtractions, and XORs ...// ... in the exact reverse order of the forward function ...*out_high64 = hi;*out_low64 = lo;
}
// ... existing code ...

它的每一步都精確地對應?BijectiveHash2x64?的逆操作，并嚴格按照相反的順序執行：

1. 先用?XXH3_unavalanche?撤銷雪崩混合。
2. 用乘法逆元撤銷乘法。
3. 用減法撤銷加法。
4. 用XOR撤銷XOR。

總結：設計精髓

1. 以無損操作為基石：使用擴展精度運算（如64->128位乘法）來確保計算過程不丟失任何信息，這是可逆性的前提。
2. 借鑒密碼學思想：采用Feistel網絡、密鑰（seed）混淆、乘大素數等方式實現充分的混淆和擴散，讓輸出看起來隨機。
3. 依賴數論工具：可逆性的實現嚴重依賴于數論，特別是模乘法逆元的計算，這是將單向乘法變為雙向的關鍵。
4. 結構對稱：正向和逆向過程在結構上是完全對稱的，逆向過程是正向過程的完美“鏡像”。

通過學習這個設計，我們可以看到一個看似簡單的“可逆哈希”背后，融合了計算機體系結構（擴展精度乘法）、密碼學（混淆擴散）和數論（模逆元）的深刻原理，是高性能計算和算法設計的典范。