Por que os códigos hash gerados por esta função não são exclusivos?
https://stackoverflow.com/questions/63897
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou testando a função VB abaixo que obtive em uma pesquisa no Google.Pretendo usá-lo para gerar códigos hash para comparação rápida de strings.No entanto, há ocasiões em que duas strings diferentes possuem o mesmo código hash.Por exemplo, essas cadeias
"Tamanho de heap 122Gen 1 (memória .NET CLR w3wp): mccsmtpteweb025.20833333333333E-02"
"Tamanho de heap 122Gen 2 (memória .NET CLR w3wp): mccsmtpteweb015.20833333333333E-02"
têm o mesmo código hash de 237117279.
Por favor, diga:- O que há de errado com a função?- Como posso consertar isso?
Obrigado
Martinho
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, src As Any, ByVal bytes As Long)
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor codes(i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
Solução
Aposto que há mais do que apenas "ocasiões" em que duas strings geram o mesmo hash usando sua função.Na verdade, isso provavelmente acontece com mais frequência do que você pensa.
Algumas coisas para perceber:
Primeiro, haverá colisões de hash.Acontece.Mesmo com espaços muito grandes como MD5 (128 bits), ainda existem duas strings que podem gerar o mesmo hash resultante.Você tem que lidar com essas colisões criando baldes.
Segundo, um número inteiro longo não é realmente um grande espaço de hash.Você terá mais colisões do que se usasse mais bits.
Em terceiro lugar, existem bibliotecas disponíveis em Visual Basic (como .NET System.Security.Cryptography namespace) que fará um trabalho de hash muito melhor do que a maioria dos meros mortais.
Outras dicas
As duas Strings possuem os mesmos caracteres.(Observe o '2' e o '1' que são flip-flops)
É por isso que o valor do hash é o mesmo.
Certifique-se de que a função hash leve em consideração a ordem dos caracteres.
As funções hash não garantem a exclusividade dos valores hash.Se o intervalo de valores de entrada (a julgar pelas strings de amostra) for maior que o intervalo de valores de saída (por exemplo, número inteiro de 32 bits), a exclusividade será fisicamente impossível.
Se o maior problema é que não leva em conta a posição dos bytes, você pode consertar assim:
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor (codes(i) + i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
A única diferença é que ele adiciona a posição dos caracteres ao valor do byte antes do XOR.
Nenhuma função hash pode garantir exclusividade.Existem aproximadamente 4 bilhões de números inteiros de 32 bits, portanto, mesmo a melhor função hash gerará duplicatas quando apresentada com aproximadamente 4 bilhões e 1 strings (e provavelmente muito antes).
Mudar para hashes de 64 bits ou mesmo hashes de 128 bits não é realmente a solução, embora reduza a probabilidade de uma colisão.
Se você quiser uma função hash melhor, você pode olhar para os hashes criptográficos, mas seria melhor reconsiderar seu algoritmo e decidir se você pode lidar com as colisões de alguma outra maneira.
O Sistema.Segurança.Criptografia namespace contém várias classes que podem fazer hash para você (como MD5), o que provavelmente fará o hash deles melhor do que você mesmo e exigirá muito menos esforço.
Você nem sempre precisa reinventar a roda.
XOR simples é um hash ruim:você encontrará muitas strings que colidem.O hash não depende da ordem das letras na string, para começar.
Tente usar o hash FNV http://isthe.com/chongo/tech/comp/fnv/
Isso é realmente simples de implementar.Ele muda o código hash após cada XOR, de modo que as mesmas letras em uma ordem diferente produzirão um hash diferente.
As funções hash não se destinam a retornar valores distintos para strings distintas.No entanto, uma boa função hash deve retornar valores diferentes para strings semelhantes.As funções hash são usadas para pesquisar por vários motivos, incluindo a pesquisa em uma grande coleção.Se a função hash for boa e retornar valores do intervalo [0,N-1], então uma grande coleção de M objetos será dividida em N coleções, cada uma tendo cerca de M/N elementos.Dessa forma, você precisa pesquisar apenas em uma matriz de elementos M/N, em vez de pesquisar em uma matriz de elementos M.
Mas, se você tiver apenas 2 cordas, é não mais rápido para calcular o valor de hash para eles!Isso é melhorar apenas para comparar as duas strings.
Uma função hash interresing poderia ser:
unsigned int hash(const char* name) {
unsigned mul=1;
unsigned val=0;
while(name[0]!=0) {
val+=mul*((unsigned)name[0]);
mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards
name++;
}
return val;
}
Corrigi o destaque de sintaxe para ele.
Além disso, para aqueles que não tinham certeza sobre o ambiente ou estavam sugerindo um hash mais seguro:é VB clássico (pré-.Net), porque .Net exigiria parênteses para a chamada para CopyMemory.
IIRC, não há hashes seguros integrados para o Classic VB.Também não há muito na web, então esta pode ser sua melhor aposta.
Não consigo entender bem o ambiente em que você trabalha.Este é o código .Net?Se você realmente deseja bons códigos hash, recomendo pesquisar hashes criptográficos (algoritmos comprovados) em vez de tentar escrever os seus próprios.
A propósito, você poderia editar sua postagem e colar o código como um exemplo de código (veja a barra de ferramentas)?Isso tornaria mais fácil a leitura.
"Não faça isso."
Escrever sua própria função hash é um grande erro, porque sua linguagem certamente já possui uma implementação de SHA-1, que é uma função hash perfeitamente boa.Se você precisar apenas de 32 bits (em vez dos 160 fornecidos pelo SHA-1), basta usar os últimos 32 bits do SHA-1.
Este hash específico funciona com XOR de todos os caracteres em uma string.Infelizmente XOR é associativo:
(a XOR b) XOR c = a XOR (b XOR c)
Portanto, qualquer string com os mesmos caracteres de entrada resultará no mesmo código hash.As duas strings fornecidas são iguais, exceto pela localização de dois caracteres, portanto devem ter o mesmo código hash.
Talvez você precise encontrar um algoritmo melhor, o MD5 seria uma boa escolha.
A operação XOR é comutativa;isto é, ao fazer XOR em todos os caracteres em uma string, a ordem dos caracteres não importa.Todos os anagramas de uma string produzirão o mesmo hash XOR.
No seu exemplo, sua segunda string pode ser gerada a partir da primeira, trocando o "1" após "...Gen" pelo primeiro "2" após ele.
Não há nada de errado com sua função.Todas as funções de hashing úteis às vezes geram colisões e seu programa deve estar preparado para resolvê-las.
Uma colisão ocorre quando uma entrada faz hash para um valor já identificado com uma entrada anterior.Se um algoritmo de hash não pudesse gerar colisões, os valores de hash precisariam ser tão grandes quanto os valores de entrada.Tal algoritmo de hash seria de uso limitado em comparação com apenas o armazenamento dos valores de entrada.
-Al.
Há uma implementação visual básica do hash MD5 aqui
