identificar, unicamente, com URLs um número de 64 bits

Question

Este é basicamente um problema de matemática, mas muito a programação relacionada: se eu tiver 1 bilhão de strings contendo URLs, e eu levo os primeiros 64 bits do hash MD5 de cada um deles, que tipo de freqüência de colisão devo esperar

Como é que a mudança de resposta se eu só tenho 100 milhões de URLs?

Parece-me que as colisões será extremamente raro, mas essas coisas tendem a ser confuso.

Será que eu estaria melhor fora de usar algo diferente do MD5? Veja bem, eu não estou à procura de segurança, apenas uma boa função hash rápido. Além disso, o suporte nativo no MySQL é bom.

Editar : não é bem um duplicado

Answer 1

Se os primeiros 64 bits do MD5 constituído um hash com a distribuição ideal, o paradoxo do aniversário seria ainda significa que você deseja obter colisões para cada 2 ^ 32 URL. Em outras palavras, a probabilidade de uma colisão é o número de URL está dividido por 4294967296. Consulte http://en.wikipedia.org/wiki/Birthday_paradox#Cast_as_a_collision_problem para mais detalhes.

Eu não me sentiria confortável apenas jogando fora metade dos bits MD5; seria melhor para XOR o alto e palavras de baixa de 64 bits para dar-lhes uma chance para misturar. Então, novamente, MD5 não é de forma rápida ou seguro, então eu não me incomodaria com ele em tudo. Se você quer uma velocidade estonteante com boa distribuição, mas nenhuma pretensão de segurança, você pode tentar as versões do MurmurHash de 64 bits. Consulte http://en.wikipedia.org/wiki/MurmurHash para detalhes e código.

Answer 2

Você marcou este como "aniversário-paradoxo", acho que você sabe a resposta já .

P(Collision) = 1 - (2^64)!/((2^64)^n (1 - n)!)

onde n é 1 bilhão em seu caso.

Você vai ser um pouco melhor usando algo diferente, em seguida, MD5, porque Tem prático conluio problema MD5 .

Answer 3

Pelo que vejo, você precisa de uma função hash com os seguintes requisitos,

1. cadeias de comprimento Hash arbitrária a um valor de 64 bits
   • Seja bom - evitar colisões
   • Não necessariamente one-way (segurança não obrigatório)
   • De preferência rápido - o que é uma característica necessária para uma aplicação não é de segurança

Este função hash pesquisa pode ser útil para a perfuração para baixo para a função mais adequada para você. < br> Vou sugerir experimentar múltiplas funções a partir daqui e caracterizando-as para o seu conjunto de entrada provável (escolher alguns bilhões de URL que você acha que você vai ver).

Você pode realmente gerar outra coluna como este teste levantamento para sua lista de URL de teste para caracterizar e selecione na quaisquer novas funções hash (mais linhas nessa tabela) que você pode querer verificar ou existente. Eles têm código-fonte MSVC ++ para começar com (referência para ZIP ligação ).

Alterar as funções hash para atender a sua largura de saída (64-bit) lhe dará uma caracterização mais precisa para a sua aplicação.

Answer 4

Se você tem 2 ^ n possibilidades de hash, há mais de 50% de chance de colisão quando você tem 2 ^ (n / 2) itens.

por exemplo. se seu hash é 64 bits, você tem 2 ^ 64 possibilidades de hash, você tem 50% de chance de colisão se você tem 2 ^ 32 itens em uma coleção.

Answer 5

Apenas usando um hash, há sempre a chance de colisões. E você não sabe de antemão wether colisões vai acontecer uma ou duas vezes, ou mesmo centenas ou milhares de vezes em sua lista de URLs.

A probabilidade ainda é apenas uma probabilidade. É como jogar um dado 10 ou 100 vezes, quais são as chances de todos os sixes? A probabilidade diz que é baixo, mas ainda pode acontecer. Talvez até mesmo muitas vezes em uma linha ...

Assim, enquanto os aniversário paradoxo mostra como calcular as probabilidades, você ainda precisa decidir se as colisões são aceitáveis ??ou não.

... e colisões são aceitáveis, e hashes ainda são o caminho certo a seguir; encontrar um algoritmo de hash de 64 bits em vez de confiar em "meia-MD5" ter uma boa distribuição. (Apesar de que provavelmente tem ...)