Por que o XOR é a maneira padrão de combinar hashes?

145

Digamos que você tenha dois hashes H(A)e H(B)deseje combiná-los. Eu li que uma boa maneira de combinar dois hashes é para XOReles, por exemplo XOR( H(A), H(B) ).

A melhor explicação que encontrei foi abordada brevemente aqui nestas diretrizes de função de hash :

XORing dois números com distribuição aproximadamente aleatória resulta em outro número ainda com distribuição aproximadamente aleatória *, mas que agora depende dos dois valores.
...
* Em cada bit dos dois números a serem combinados, um 0 é emitido se os dois bits forem iguais, senão um 1. Em outras palavras, em 50% das combinações, um 1 será emitido. Portanto, se cada um dos dois bits de entrada tiver aproximadamente 50-50 chances de serem 0 ou 1, o mesmo ocorrerá com o bit de saída.

Você pode explicar a intuição e / ou a matemática por trás do motivo pelo qual o XOR deve ser a operação padrão para combinar funções de hash (em vez de OR ou AND etc.)?

Nate Murray
fonte
20
Eu acho que você acabou de fazer;)
Massa
22
observe que o XOR pode ou não ser uma maneira "boa" de "combinar" hashes, dependendo do que você deseja em uma "combinação". XOR é comutativo: XOR (H (A), H (B)) é igual a XOR (H (B), H (A)). Isso significa que o XOR não é uma maneira adequada de criar um tipo de hash de uma sequência de valores ordenada, pois não captura a ordem.
Thomas Pornin
6
Além do problema com o pedido (comentário acima), há um problema com valores iguais. XOR (H (1), H (1)) = 0 (para qualquer função H), XOR (H (2), H (2)) = 0 e assim por diante. Para qualquer N: XOR (H (N), H (N)) = 0. Valores iguais acontecem com frequência em aplicativos reais, significa que o resultado do XOR será 0 com muita frequência para ser considerado como um bom hash.
Andrei Galatyn 06/04
O que você usa para a sequência ordenada de valores? Digamos que eu gostaria de criar um hash de timestamp ou índice. (MSB menos importante que LSB). Desculpe se este tópico tem 1 ano de idade.
Alexis #

Respostas:

120

Supondo entradas uniformemente aleatórias (1 bit), a distribuição de probabilidade de saída da função AND é de 75% 0e 25% 1. Por outro lado, o OR é de 25% 0e 75% 1.

A função XOR é de 50% 0e 50% 1, portanto, é boa para combinar distribuições de probabilidade uniformes.

Isso pode ser visto escrevendo tabelas de verdade:

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

 a | b | a OR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    1

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

Exercício: Como muitas funções lógicas de duas entradas de 1 bit ae btem essa distribuição de saída uniforme? Por que o XOR é o mais adequado para o objetivo indicado em sua pergunta?

Greg Hewgill
fonte
24
respondendo ao exercício: das 16 possíveis operações diferentes a XXX b (0, a & b, a > b, a, a < b, b, a % b, a | b, !a & !b, a == b, !b, a >= b, !a, a <= b, !a | !b, 1), as seguintes têm distribuições de 50% a 50% de 0s e 1s, assumindo que aeb têm distribuições de 50% a 50% de 0s e 1s: a, b, !a, !b, a % b, a == bou seja, o oposto de XOR (EQUIV) poderia ter sido usado como bem ...
Massa
7
Greg, esta é uma resposta incrível. A lâmpada acendeu para mim depois que vi sua resposta original e escrevi minhas próprias tabelas da verdade. Considerei a resposta de @ Massa sobre como existem 6 operações adequadas para manter a distribuição. E embora a, b, !a, !btenha a mesma distribuição que suas respectivas entradas, você perde a entropia da outra entrada. Ou seja, o XOR é mais adequado para o propósito de combinar hashes, porque queremos capturar entropia de a e b.
Nate Murray
1
Aqui está um artigo que explica que combinar hashes com segurança, onde cada função é chamada apenas uma vez, não é possível sem gerar menos bits do que a soma do número de bits em cada valor de hash. Isso sugere que esta resposta não está correta.
Tamás Szelei
3
@Massa Eu nunca vi% usado para XOR ou não é igual.
Buge
7
Como Yakk ressalta , o XOR pode ser perigoso, pois produz zero para valores idênticos. Isso significa (a,a)e (b,b)ambos produzem zero, o que em muitos casos (na maioria dos casos) aumenta muito a probabilidade de colisões em estruturas de dados baseadas em hash.
de Drew Noakes
170

xoré uma função padrão perigosa a ser usada no hash. É melhor que ande or, mas isso não diz muito.

xoré simétrico, então a ordem dos elementos é perdida. Então "bad", o hash combinará o mesmo que "dab".

xor mapeia valores idênticos aos pares para zero e evite mapear valores "comuns" para zero:

Então, (a,a)é mapeado para 0 e (b,b)também para 0. Como esses pares são quase sempre mais comuns do que a aleatoriedade pode implicar, você acaba com muitas colisões em zero do que deveria.

Com esses dois problemas, xoracaba sendo um combinador de hash que parece meio decente na superfície, mas não após uma inspeção mais aprofundada.

No hardware moderno, adicionar normalmente tão rápido quanto xor(provavelmente usa mais energia para fazer isso, é certo). A tabela verdade de Adding é semelhante à xordo bit em questão, mas também envia um bit para o próximo bit quando ambos os valores são 1. Isso significa que apaga menos informações.

Portanto, hash(a) + hash(b)é melhor do hash(a) xor hash(b)que se a==b, o resultado for em hash(a)<<1vez de 0.

Isso permanece simétrico; portanto, "bad"e "dab"obter o mesmo resultado continua sendo um problema. Podemos quebrar essa simetria por um custo modesto:

hash(a)<<1 + hash(a) + hash(b)

aka hash(a)*3 + hash(b). ( hash(a)é recomendável calcular uma vez e armazenar se você usar a solução de turno). Qualquer constante ímpar, em vez de 3, mapeará bijetivamente um knúmero inteiro não assinado de "bits" para si próprio, pois o mapa em números inteiros não assinados é o módulo matemático 2^kpara alguns k, e qualquer constante ímpar é relativamente primordial 2^k.

Para uma versão ainda mais sofisticada, podemos examinar o boost::hash_combineque é efetivamente:

size_t hash_combine( size_t lhs, size_t rhs ) {
  lhs ^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
  return lhs;
}

aqui adicionamos algumas versões deslocadas de seedcom uma constante (que é basicamente aleatória se 0es 1- em particular, é o inverso da proporção áurea como uma fração de ponto fixo de 32 bits) com alguma adição e um xor. Isso quebra a simetria, e introduz alguns "ruído" se os valores hash de entrada são pobres (ou seja, imaginar cada hashes de componentes para 0 - as alças acima bem, gerando uma mancha de 1e 0. S após cada combinar meu ingênuo 3*hash(a)+hash(b)simplesmente emite um 0em Aquele caso).

(Para aqueles que não estão familiarizados com C / C ++, a size_té um valor inteiro não assinado que é grande o suficiente para descrever o tamanho de qualquer objeto na memória. Em um sistema de 64 bits, geralmente é um número inteiro não assinado de 64 bits. Em um sistema de 32 bits , um número inteiro não assinado de 32 bits.)

Yakk - Adam Nevraumont
fonte
Boa resposta Yakk. Esse algoritmo funciona igualmente bem em sistemas de 32 bits e 64 bits? Obrigado.
21415 Dave
1
@dave adicione mais bits a 0x9e3779b9.
precisa saber é o seguinte
10
OK, para ser concluído ... aqui está a constante de precisão total de 64 bits (calculada com dobras longas e longas sem assinatura): 0x9e3779b97f4a7c16. Curiosamente, ainda é uniforme. Voltar a fazer o mesmo cálculo usando PI em vez da Proporção áurea produz: 0x517cc1b727220a95 que é ímpar, em vez de par, provavelmente "mais primo" que a outra constante. Eu usei: std :: cout << std :: hex << (sem assinatura por muito tempo) ((1.0L / 3.14159265358979323846264338327950288419716939937510L) * (powl (2.0L, 64.0L))) << std :: endl; com cout.precision (numeric_limits <long double> :: max_digits10); Mais uma vez obrigado Yakk.
Dave
2
@ A regra inversa da proporção áurea nesses casos é o primeiro número ímpar igual ou maior que o cálculo que você está fazendo. Portanto, basta adicionar 1. É um número importante porque a sequência de N * a razão, mod o tamanho máximo (2 ^ 64 aqui) coloca o próximo valor na sequência exatamente nessa proporção no meio da maior 'lacuna' em números. Pesquise na web por "Fibonacci hashing" para obter mais informações.
Scott Carey
1
@Dave o número certo seria 0.9E3779B97F4A7C15F39 ... Ver link . Você pode estar sofrendo com a regra do arredondamento para o par (o que é bom para os contadores), ou simplesmente, se você começar com uma constante literal sqrt (5), quando subtrair 1, removerá o bit de ordem superior, um bit deve ter sido perdido.
migle
29

Apesar de suas práticas propriedades de mistura de bits, o XOR não é uma boa maneira de combinar hashes devido à sua comutatividade. Considere o que aconteceria se você armazenasse as permutações de {1, 2,…, 10} em uma tabela de 10 tuplas.

Uma escolha muito melhor é m * H(A) + H(B), onde m é um grande número ímpar.

Crédito: O combinador acima foi uma dica de Bob Jenkins.

Marcelo Cantos
fonte
2
Às vezes, a comutatividade é uma coisa boa, mas o xor é uma péssima escolha, mesmo porque todos os pares de itens correspondentes serão divididos em zero. Uma soma aritmética é melhor; o hash de um par de itens correspondentes reterá apenas 31 bits de dados úteis em vez de 32, mas isso é muito melhor do que reter zero. Outra opção pode ser calcular a soma aritmética como a longe depois mover a parte superior de volta com a parte inferior.
Supercat 2/13
1
m = 3é realmente uma boa escolha e muito rápido em muitos sistemas. Observe que, para qualquer número minteiro ímpar, a multiplicação é modulo 2^32ou 2^64e, portanto, é invertível para que você não perca nenhum bit.
StefanKarpinski
O que acontece quando você vai além do MaxInt?
disruptive
2
em vez de qualquer número ímpar deve-se escolher um número primo
TermoTux
2
@ Infinum que não é necessário ao combinar hashes.
Marcelo Cantos
17

Xor pode ser a maneira "padrão" de combinar hashes, mas a resposta de Greg Hewgill também mostra por que tem suas armadilhas: O xor de dois valores de hash idênticos é zero. Na vida real, existem hashes idênticos e são mais comuns do que se poderia esperar. Você pode descobrir que, nesses casos de canto (não tão pouco frequentes), os hashes combinados resultantes são sempre os mesmos (zero). As colisões de hash seriam muito, muito mais frequentes do que o esperado.

Em um exemplo artificial, você pode combinar senhas com hash de usuários de diferentes sites que você gerencia. Infelizmente, um grande número de usuários reutiliza suas senhas, e uma proporção surpreendente dos hashes resultantes é zero!

Leo Goodstadt
fonte
Espero que o exemplo artificial nunca aconteça, as senhas sejam salgadas.
user60561
8

Há algo que quero destacar explicitamente para outras pessoas que encontram esta página. AND e OR restringem a saída como BlueRaja - Danny Pflughoe está tentando apontar, mas pode ser melhor definido:

Primeiro, quero definir duas funções simples que vou usar para explicar isso: Min () e Max ().

Min (A, B) retornará o valor menor entre A e B, por exemplo: Min (1, 5) retorna 1.

Max (A, B) retornará o valor que é maior entre A e B, por exemplo: Max (1, 5) retorna 5.

Se você receber: C = A AND B

Então você pode achar que C <= Min(A, B) sabemos disso porque não há nada que você possa AND com os 0 bits de A ou B para torná-los 1s. Portanto, todo bit zero permanece um bit zero e cada bit tem a chance de se tornar um bit zero (e, portanto, um valor menor).

Com: C = A OR B

O oposto é verdadeiro: C >= Max(A, B)com isso, vemos o corolário da função AND. Qualquer bit que já seja um não pode ser transformado em zero, portanto permanece um, mas cada bit zero tem a chance de se tornar um e, portanto, um número maior.

Isso implica que o estado da entrada aplique restrições à saída. Se você AND qualquer coisa com 90, você sabe que a saída será igual ou menor que 90, independentemente do outro valor.

Para o XOR, não há restrição implícita com base nas entradas. Há casos especiais em que você pode descobrir que, se você XOR um byte com 255, obtém o inverso, mas qualquer byte possível pode ser gerado a partir dele. Cada bit tem a chance de mudar de estado, dependendo do mesmo bit no outro operando.

Corey Ogburn
fonte
6
Pode-se dizer que ORé no máximo bit a bit , e ANDé bit a bit min .
Pa Elo Ebermann
Muito bem afirmado Paulo Ebermann. Prazer em vê-lo aqui, bem como Crypto.SE!
Corey Ogburn
Criei um filtro que inclui tudo o que foi criptografado com tags , também muda para perguntas antigas. Dessa forma, encontrei sua resposta aqui.
Pa Elo Ebermann
3

Se você for XORuma entrada aleatória com uma entrada tendenciosa, a saída será aleatória. O mesmo não é verdadeiro para ANDou OR. Exemplo:

00101001 XOR 00000000 = 00101001
00101001 AND 00000000 = 00000000
00101001 OR 11111111 = 11111111

Como o @Greg Hewgill menciona, mesmo se as duas entradas forem aleatórias, usando ANDou ORresultarão em resultados tendenciosos.

A razão pela qual usamos XORalgo mais complexo é que, bem, não há necessidade: XORfunciona perfeitamente e é incrivelmente rápido e estúpido.

BlueRaja - Danny Pflughoeft
fonte
1

Cubra as 2 colunas da esquerda e tente descobrir o que as entradas estão usando apenas a saída.

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

Quando você viu um bit, deveria ter percebido que as duas entradas eram 1.

Agora faça o mesmo para o XOR

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

O XOR não fornece nada sobre isso.

Robert
fonte
0

O código-fonte para várias versões do hashCode()in java.util.Arrays é uma excelente referência para algoritmos de hash sólidos e de uso geral. Eles são facilmente entendidos e traduzidos para outras linguagens de programação.

Grosso modo, a maioria dos multi-atributo hashCode()implementações seguem este padrão:

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

Você pode pesquisar outras Perguntas e Respostas sobre o StackOverflow para obter mais informações sobre a mágica por trás 31e por que o código Java a usa com tanta frequência. É imperfeito, mas possui muito boas características de desempenho geral.

kevinarpe
fonte
2
O hash padrão do Java "multiplique por 31 e adicione / acumule" o hash é carregado com colisões (por exemplo, qualquer colisão stringcom o string + "AA"IIRC) e há muito tempo eles desejavam não ter inserido esse algoritmo nas especificações. Dito isto, usar um número ímpar maior com mais bits definidos e adicionar mudanças ou rotações corrige esse problema. O 'mix' de MurmurHash3 faz isso.
Scott Carey
0

O XOR não ignora algumas das entradas às vezes como OR e AND .

Se você pegar AND (X, Y), por exemplo, e alimentar a entrada X com false, então a entrada Y não importa ... e provavelmente você gostaria que a entrada importasse ao combinar hashes.

Se você usar XOR (X, Y) , ambas as entradas importam SEMPRE . Não haveria valor de X onde Y não importa. Se X ou Y forem alterados, a saída refletirá isso.

Sunsetquest
fonte