Número mágico em boost :: hash_combine

94

A boost::hash_combinefunção de modelo leva uma referência a um hash (chamado seed) e um objeto v. De acordo com os documentos , ele combina seedcom o hash vpor

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

Posso ver que isso é determinístico. Eu vejo porque um XOR é usado.

Aposto que a adição ajuda a mapear valores semelhantes amplamente separados, de modo que as tabelas de hash de sondagem não quebram, mas alguém pode explicar o que é a constante mágica?

c++ algorithm boost hash magic-numbers Fred Foo
fonte
Dado que em muitos computadores uma rotação inteira custa quase o mesmo que um deslocamento, haveria qualquer benefício em converter a expressão em: <code> seed ^ = hash_value (v) + 0x9e3779b9 + rotl (seed, 6) + rotr (seed, 2); </code>
John Yates

Respostas:

140

O número mágico deve ser de 32 bits aleatórios, em que 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 string de tais bits é usar a expansão binária de um número irracional; neste caso, esse número é o recíproco da proporção áurea:

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

Portanto, incluir este número "aleatoriamente" altera cada bit da semente; como você disse, isso significa que os valores consecutivos estarão distantes. Incluir as versões alteradas da semente antiga garante que, mesmo que hash_value()tenha uma faixa de valores bastante pequena, as diferenças logo se espalharão por todos os bits.

Mike Seymour
fonte
14
Legal! Eu gosto quando a teoria dos números de repente se torna útil :)
Fred Foo
8
@larsmans Eu adoro o seu uso de 'de repente' - é muito apropriado! A teoria dos números é como "sim, isso é bom ... mas tenho um trabalho real a fazer, desculpe" em 99% de todos os casos. E então, como você diz, 'de repente', a teoria dos números é super super útil. Não é como um martelo, onde é bastante útil para um grande número de coisas. Em vez disso, é como um bisturi extremamente útil para um pequeno número de coisas.
corsiKa de
5
@SamKellett Funcionaria ainda melhor se você usasse o número correto de parênteses e obtivesse0x9e3779b97f4a7800
Barry,
5
Como o número de ponto flutuante do Python não tem precisão suficiente, as proporções de ouro de 64 bits acima não estão corretas. O resultado real deve ser 0x9e3779b97f4a7c15.
kennytm
1
@kennytm Você não quer dizer 0x9e3779b97f4a7c16? Quer dizer, é apenas 1 de desconto.
bit2shift
25

Dê uma olhada no artigo 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. Seu objetivo é evitar o mapeamento de todos os zeros para todos os zeros.

NPE
fonte