algoritmo de hash colisão não para cadeias de até 255 caracteres

Question

Eu estou procurando um hash-algoritmo, para criar o mais próximo a um hash exclusivo de uma string (len max = 255) quanto possível, que produz um inteiro longo (DWORD).

Eu percebo que 26 ^ 255 >> 2 ^ 32, mas também sabemos que o número de palavras no idioma Inglês é muito menos do que 2 ^ 32.

As cordas que eu preciso 'haxixe' seria palavras na sua maioria individuais ou alguma construção simples, usando duas ou três palavras.

---

A resposta :

Um dos FNV variantes deve atender às suas necessidades. Eles são rápidos, e produzir resultados de forma bastante equilibrada distribuídos. (Atendida por Aracnídeo )

---

Answer 1

Veja aqui para uma iteração anterior desta pergunta (ea resposta).

Answer 2

Uma técnica é a utilização de um algoritmo de hash bem conhecido (por exemplo, MD5 ou SHA-1) e utilizar somente os primeiros 32 bits do resultado.

Esteja ciente de que o risco de colisões de hash aumenta mais rápido do que você poderia esperar. Para obter informações sobre isso, leia sobre a aniversário Paradox .

Answer 3

Ronny Pfannschmidt fez um teste com palavras inglesas comuns ontem e não encontrou qualquer colisão para as 10000 palavras que ele testados na função de cadeia de hash Python. Eu não testei isso sozinho, mas que o algoritmo é muito simples e rápido, e parece ser otimizado para palavras comuns.

Aqui a implementação:

static long
string_hash(PyStringObject *a)
{
    register Py_ssize_t len;
    register unsigned char *p;
    register long x;

    if (a->ob_shash != -1)
        return a->ob_shash;
    len = Py_SIZE(a);
    p = (unsigned char *) a->ob_sval;
    x = *p << 7;
    while (--len >= 0)
        x = (1000003*x) ^ *p++;
    x ^= Py_SIZE(a);
    if (x == -1)
        x = -2;
    a->ob_shash = x;
    return x;
}

Answer 4

H (chave) = [GetHash (chave) + 1 + (((GetHash (chave) >> 5) + 1)% (hashsize - 1))]% hashsize

artigo do MSDN sobre hashcodes

Answer 5

String.hash () do Java podem ser facilmente visualizados aqui , seu algoritmo é

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]