Pergunta sobre c++, hash – String para Integer Hashing Function com precisão

4

Eu quero hash um array char em um int ou um longo. O valor resultante tem que aderir a um determinado valor de precisão. A função que estou usando é dada abaixo:

<code>int GetHash(const char* zKey, int iPrecision /*= 6*/)
{
        /////FROM : http://courses.cs.vt.edu/~cs2604/spring02/Projects/4/elfhash.cpp

        unsigned long h = 0;
        long M = pow(10, iPrecision);

        while(*zKey)
        {
                h = (h << 4) + *zKey++;
                unsigned long g = h & 0xF0000000L;
                if (g) h ^= g >> 24;
                h &= ~g;
        }            

        return (int) (h % M);
}
</code>

A cadeia a ser dividida é semelhante a "SAEUI1210.00000010_1".

No entanto, isso produz valores duplicados em alguns casos. Existem boas alternativas que não duplicariam o mesmo hash para diferentes valores de string.

Tente usar o CRC 32:en.wikipedia.org/wiki/Crc32 Akira Yamamoto

Sua resposta

4   a resposta
1

MD5 ouSHA. Existem muitas implementações abertas e é muito improvável que o resultado produza um resultado duplicado.

Verdade, mas a conversão é trivial - de 128 bits para 32 bits inteiro. Você obterá um código de 2 linhas (hash, int conversion) que produz um hash de colisão de fato. Adam Matan
Sim. Mas minha exigência também inclui o fato de que o resultado tem que ser um inteiro. Os hashes MD5 contêm tanto ints quanto chars. Eu acho que é o mesmo para algoritmos SHA Gayan
2

Problema de aniversário.

Você pode querer verificar se a criptografia tem funções como o MD5 (relativamente rápido e você não se importa que seja inseguro), mas também terá colisões.

Hashes perfeitos por definição não. MSalters
2

. Tudo o que você pode fazer é criar uma função hash com distribuição suficiente ou profundidade de bits (ou ambos) para minimizar essas colisões. Já que você tem essa restrição adicional de precisão (0 a 5), ​​você vai atingir colisões com muito mais frequência.

13

a alguns valores, devido ao intervalo de valores de hash ser menor que o espaço dos dados com hash.

Em teoria, um hash de 32 bits tem intervalo suficiente para hash todas as seqüências de caracteres de 6 caracteres (A-Z, a-z, 0-9 somente), sem causar uma colisão. Na prática, os hashes não são uma permutação perfeita da entrada. Dado um hash de 32 bits, você pode esperar obter colisões de hash após hashing ~ 16 bit de entradas aleatórias, devido àparadoxo de aniversário.

Dado um conjunto estático de valores de dados, é sempre possível construir uma função hash projetada especificamente para eles, que nunca colidirá com eles mesmos (obviamente, o tamanho de sua saída será pelo menoslog(|data set|). No entanto, exige que você conheça todos os possíveis valores de dados com antecedência. Isso é chamadohashing perfeito.

Dito isto,Aqui Existem algumas alternativas que devem ajudá-lo (elas são projetadas para minimizar colisões)

Qual é a melhor função de hashing para usar dentre as fornecidas no link que você forneceu e a que estou usando no momento. A função que estou usando parece ser mais complexa que djb2 e sdbm. Isso significa que é melhor evitar colisões? Gayan
A única maneira de testar qual função hash é "melhor" para seus propósitos é realizar uma referência na amostra de dados que se ajusta aos dados reais esperados. A função que você está usando não tenta misturar os bits de entrada com muita força para criar um hash - a cada passo, no máximo 4 bits mais altos são misturados; e em strings de comprimento <8, mesmo que isso não aconteça, seu hash simplesmente acumula todos os caracteres, com um pouco de sobreposição. ASk

Perguntas relacionadas