問題描述

boost::hash_combine 模板函數引用一個哈希(稱為seed)和一個對象v.根據文檔，它將seed 與v 的hash 組合起來，由

The boost::hash_combine template function takes a reference to a hash (called seed) and an object v. According to the docs, it combines seed with the hash of v by

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);

我可以看出這是確定性的.我明白為什么要使用 XOR.

I can see that this is deterministic. I see why a XOR is used.

我敢打賭，添加有助于將相似的值映射得相距甚遠，因此探查哈希表不會崩潰，但有人可以解釋魔術常數是什么嗎?

I bet the addition helps in mapping similar values widely apart so probing hash tables won't break down, but can someone explain what the magic constant is?

推薦答案

幻數應該是 32 個隨機位，其中每個位都是 0 或 1 的可能性相等，并且這些位之間沒有簡單的相關性.找到一串這樣的位的常用方法是使用無理數的二進制展開；在這種情況下，該數字是黃金比例的倒數:

The magic number is supposed to be 32 random bits, where each is equally likely to be 0 or 1, and with no simple correlation between the bits. A common way to find a string of such bits is to use the binary expansion of an irrational number; in this case, that number is the reciprocal of the golden ratio:

phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9

所以包括這個數字隨機"改變種子的每一位；正如您所說，這意味著連續的值將相距甚遠.包括舊種子的移位版本可以確保，即使 hash_value() 的值范圍很小，差異也會很快擴散到所有位.

So including this number "randomly" changes each bit of the seed; as you say, this means that consecutive values will be far apart. Including the shifted versions of the old seed makes sure that, even if hash_value() has a fairly small range of values, differences will soon be spread across all the bits.

這篇關于boost::hash_combine 中的幻數的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！