Número mágico em aumento :: hash_combine

A function de modelo boost::hash_combine usa uma referência a um hash (chamado seed ) e um object v . De acordo com os documentos , combina seed com o hash de v por

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

Eu posso ver que isso é determinista. Eu vejo porque um XOR é usado.

Aposto que o acréscimo ajuda no mapeamento de valores semelhantes amplamente separados, de forma que as tabelas de hash não quebrem, mas alguém pode explicar qual é a constante mágica?

O número mágico é supostamente de 32 bits randoms, onde cada um tem a mesma probabilidade de ser 0 ou 1, e sem correlação simples entre os bits. Uma maneira comum de encontrar uma sequência de bits é usar a expansão binária de um número irracional; neste caso, esse número é o recíproco da razão áurea:

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

Então, include esse número “aleatoriamente” muda cada bit da semente; Como você diz, isso significa que valores consecutivos estarão distantes. Incluir as versões deslocadas da semente antiga garante que, mesmo que hash_value() tenha um intervalo de valores razoavelmente pequeno, as diferenças serão distribuídas rapidamente em todos os bits.

Dê uma olhada no artigo do DDJ de Bob Jenkins de 1997 . A constante mágica (“proporção áurea”) é explicada da seguinte forma:

A proporção áurea é realmente um valor arbitrário. Sua finalidade é evitar mapear todos os zeros para todos os zeros.