função hash para string

124

Estou trabalhando na tabela de hash na linguagem C e testando a função de hash para string.

A primeira função que tentei é adicionar código ascii e usar o módulo (% 100), mas obtive resultados ruins com o primeiro teste de dados: 40 colisões por 130 palavras.

Os dados finais de entrada conterão 8.000 palavras (é um arquivo armazenado em um arquivo). A tabela de hash é declarada como tabela int [10000] e contém a posição da palavra em um arquivo txt.

A primeira pergunta é qual é o melhor algoritmo para hash de string? e como determinar o tamanho da tabela de hash?

desde já, obrigado !

:-)

lilawood
fonte
11
Se sua tabela de hash tiver 10 mil entradas, por que você usaria o módulo 100? Obter 40 colisões em 130 palavras não é surpreendente com um módulo tão pequeno.
Carey Gregory
13
Consulte burtleburtle.net/bob/hash/evahash.html e partow.net/programming/hashfunctions para os quais são recursos sobre vários hash (de geral a string para criptografia).
3
Para esclarecer o @CareyGregory: Você percebe que, como uma verdade matemática básica, 130 itens em 100 baldes (ou seja, mod 100) devem produzir 30 colisões (onde a colisão é contada como cada vez que um segundo, terceiro etc.) é colocado um balde), correto? Então você está apenas um pouco acima disso.
Derobert 5/10
4
@ilawood: OK, foi o que eu imaginei, mas para ser um teste melhor, você deve usar 80 palavras com uma tabela de hash de 100 entradas. Isso daria as mesmas proporções que seus dados ativos e não forçaria colisões.
Carey Gregory
4
Possível duplicata da Good Hash Function para Strings
MJ Rayburn

Respostas:

185

Eu tive bons resultados com djb2Dan Bernstein.

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}
cnicutar
fonte
37
a página vinculada na resposta é muito interessante.
Adrien Plisson
2
como o programa fica fora do loop while? = S
Daniel N.
1
@ danfly09 Quando c é zero. O equivalente a while (c = * str ++) seria (0 = (c = * str ++)!)
rxantos
5
@Josepas, a função hash deve retornar idealmente um size_tou outro valor não assinado (como o não assinado por muito tempo neste código). O chamador é responsável por receber o módulo do resultado para ajustá-lo à tabela de hash. O chamador controla o slot da tabela que está sendo hash; não é a função. Ele apenas retorna um número não assinado.
precisa saber é o seguinte
6
surpreendente. esse algoritmo venceu o hash Murmur, hashes de variantes FNV e muitos outros! 1
David Haim
24

Primeiro, você geralmente não deseja usar um hash criptográfico para uma tabela de hash. Um algoritmo que é muito rápido pelos padrões criptográficos ainda é terrivelmente lento pelos padrões da tabela de hash.

Segundo, você deseja garantir que cada bit da entrada possa / irá afetar o resultado. Uma maneira fácil de fazer isso é girar o resultado atual por um número de bits e, em seguida, XOR o código de hash atual com o byte atual. Repita até chegar ao final da string. Observe que geralmente você também não deseja que a rotação seja um múltiplo múltiplo do tamanho de bytes.

Por exemplo, supondo o caso comum de bytes de 8 bits, você pode girar 5 bits:

int hash(char const *input) { 
    int result = 0x55555555;

    while (*input) { 
        result ^= *input++;
        result = rol(result, 5);
    }
}

Editar: Observe também que 10000 slots raramente são uma boa opção para um tamanho de tabela de hash. Você geralmente deseja uma de duas coisas: você quer um número primo como o tamanho (necessário para garantir a correção com alguns tipos de resolução de hash) ou então uma potência de 2 (portanto, reduzir o valor para o intervalo correto pode ser feito com um simples máscara de bits).

Jerry Coffin
fonte
Este não é c, mas eu estaria interessado em seus pensamentos para esta resposta relacionada: stackoverflow.com/a/31440118/3681880
Suragch
1
@ Suragch: Desde que escrevi isso, alguns processadores começaram a incluir hardware especial para acelerar a computação SHA, o que a tornou muito mais competitiva. Dito isso, duvido que seu código seja tão seguro quanto você pensa - por exemplo, números de ponto flutuante IEEE têm dois padrões de bits diferentes (0 e -0) que devem produzir os mesmos hashes (eles serão comparados entre si) )
21415 Jerry Coffin
@ Jerry Coffin de que biblioteca eu preciso para a função rol ()?
thanos.a 28/03
@ thanos.a: Não sei se ele está em uma biblioteca, mas rolar o seu próprio código requer apenas uma ou duas linhas. Desloque um pedaço para a esquerda, o outro pedaço para a direita e ou eles juntos.
Jerry Coffin
8

A Wikipedia mostra uma boa função de hash de string chamada Jenkins, uma de cada vez. Ele também cita versões aprimoradas desse hash.

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}
RushPL
fonte
8

Existem várias implementações de hashtable existentes para C, da biblioteca padrão C hcreate / hdestroy / hsearch, às da APR e glib , que também fornecem funções de hash pré-construídas. Eu recomendo usá-las em vez de inventar sua própria função de hashtable ou hash; eles foram altamente otimizados para casos de uso comuns.

Se seu conjunto de dados é estático, no entanto, sua melhor solução é provavelmente usar um hash perfeito . O gperf irá gerar um hash perfeito para você para um determinado conjunto de dados.

Nick Johnson
fonte
hsearch pesquisa comparando as strings ou o endereço ptr da string? Eu acho que é apenas verificar o endereço ptr? Eu tentei usar ponteiros diferentes, mas o mesmo valor da string. hsearch falha declarando que nenhum elemento encontrado
mk .. 05/07
3

O djb2 possui 317 colisões para este dicionário de inglês de 466k, enquanto o MurmurHash não possui nenhum para hashes de 64 bits e 21 para hashes de 32 bits (cerca de 25 é esperado para 466k hashes aleatórios de 32 bits). Minha recomendação é usar o MurmurHash, se disponível, é muito rápido, pois leva vários bytes por vez. Mas se você precisar de uma função hash simples e curta para copiar e colar no seu projeto, eu recomendo o uso de murmúrios na versão de um byte por vez:

uint32_t inline MurmurOAAT32 ( const char * key)
{
  uint32_t h(3323198485ul);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e995;
    h ^= h >> 15;
  }
  return h;
}

uint64_t inline MurmurOAAT64 ( const char * key)
{
  uint64_t h(525201411107845655ull);
  for (;*key;++key) {
    h ^= *key;
    h *= 0x5bd1e9955bd1e995;
    h ^= h >> 47;
  }
  return h;
}

O tamanho ideal de uma tabela de hash é - em resumo - o maior possível, enquanto ainda se encaixa na memória. Como geralmente não sabemos ou queremos pesquisar quanta memória temos disponível, e pode até mudar, o tamanho ideal da tabela de hash é aproximadamente o dobro do número esperado de elementos a serem armazenados na tabela. Alocar muito mais do que isso tornará sua tabela de hash mais rápida, mas com retornos cada vez menores, tornando sua tabela de hash menor que isso, tornando-a exponencialmente mais lenta. Isso ocorre porque existe um trade-off não linear entre complexidade de espaço e tempo para tabelas de hash, com um fator de carga ideal de 2-sqrt (2) = 0,58 ... aparentemente.

Wolfgang Brehm
fonte
2

Primeiro, 40 colisões para 130 palavras com hash para 0..99 são ruins? Você não pode esperar o hash perfeito se não estiver tomando medidas específicas para que isso aconteça. Uma função hash comum não terá menos colisões do que um gerador aleatório na maioria das vezes.

Uma função de hash com boa reputação é MurmurHash3 .

Finalmente, em relação ao tamanho da tabela de hash, isso realmente depende do tipo de tabela de hash que você tem em mente, especialmente se os buckets são extensíveis ou de um slot. Se os buckets forem extensíveis, novamente existe uma opção: você escolhe o comprimento médio do bucket para as restrições de memória / velocidade que possui.

Pascal Cuoq
fonte
1
O número esperado de colisões de hash é n - m * (1 - ((m-1)/m)^n) = 57.075.... 40 colisões são melhores do que o que poderia ser esperado por acaso (46 a 70 com um p-score de 0,999). A função hash em questão é mais uniforme do que se fosse aleatória ou estamos testemunhando um evento muito raro.
Wolfgang Brehm
2

Embora djb2, como apresentado no stackoverflow da cnicutar , seja quase certamente melhor, acho que vale a pena mostrar os hashes K&R também:

1) Aparentemente, um terrível algoritmo de hash, como apresentado na 1ª edição da K&R ( fonte )

unsigned long hash(unsigned char *str)
{
    unsigned int hash = 0;
    int c;

    while (c = *str++)
        hash += c;

    return hash;
}

2) Provavelmente, um algoritmo de hash bastante decente, como apresentado na versão 2 da K&R (verificado por mim na p. 144 do livro); Nota: certifique-se de remover % HASHSIZEda instrução de retorno se você planeja fazer o módulo dimensionar para o comprimento da matriz fora do algoritmo hash. Além disso, eu recomendo que você faça o retorno e o tipo "hashval" em unsigned longvez do simples unsigned(int).

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31*hashval;
    return hashval % HASHSIZE;
}

Observe que, pelos dois algoritmos, fica claro que um dos motivos pelo qual o hash da 1ª edição é tão terrível é porque NÃO leva em consideração a ordem dos caracteres da string , portanto hash("ab"), retornaria o mesmo valor que hash("ba"). Isto não é acontece com o hash da 2ª edição, no entanto, que (muito melhor!) Retornaria dois valores diferentes para essas strings.

As funções de hash do GCC C ++ 11 usadas para unordered_map(um modelo de tabela de hash) e unordered_set(um modelo de conjunto de hash) parecem ser as seguintes.

Código:

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}
Gabriel Staples
fonte
2

Eu tentei essas funções de hash e obtive o seguinte resultado. Eu tenho cerca de 960 ^ 3 entradas, cada uma com 64 bytes de comprimento, 64 caracteres em ordem diferente, valor de hash 32 bits. Códigos daqui .

Hash function    | collision rate | how many minutes to finish
==============================================================
MurmurHash3      |           6.?% |                      4m15s
Jenkins One..    |           6.1% |                      6m54s   
Bob, 1st in link |          6.16% |                      5m34s
SuperFastHash    |            10% |                      4m58s
bernstein        |            20% |       14s only finish 1/20
one_at_a_time    |          6.16% |                       7m5s
crc              |          6.16% |                      7m56s

Uma coisa estranha é que quase todas as funções de hash têm taxa de colisão de 6% para meus dados.

Xiaoning Bian
fonte
Embora esse link possa responder à pergunta, é melhor incluir aqui as partes essenciais da resposta e fornecer o link para referência. As respostas somente para links podem se tornar inválidas se a página vinculada for alterada.
thewaywewere
Com um voto positivo para uma boa tabela, também é essencial postar o código-fonte de cada um desses hashes em sua resposta. Caso contrário, os links podem quebrar e estamos sem sorte.
Gabriel Staples
O número esperado de colisões deve ser 9.112499989700318E + 7 ou 0.103 * 960³ se os hashes forem realmente aleatórios, então eu não ficaria surpreso se eles estivessem em torno desse valor, mas 0,0616 * 960³ parece um pouco fora, quase como se o os hashes são distribuídos de maneira mais uniforme do que seria esperado por acaso e, com 64 bytes de comprimento, esse limite deve ser definitivamente aproximado. Você pode compartilhar o conjunto de strings que você hash para que eu possa tentar reproduzi-lo?
Wolfgang Brehm
0

Uma coisa que usei com bons resultados é a seguinte (não sei se já foi mencionado porque não me lembro o nome).

Você pré-calcula uma tabela T com um número aleatório para cada caractere no alfabeto da sua chave [0,255]. Você faz o hash da sua chave 'k0 k1 k2 ... kN', usando T [k0] xor T [k1] xor ... xor T [kN]. Você pode mostrar facilmente que isso é tão aleatório quanto o seu gerador de números aleatórios e é computacionalmente viável. Se você realmente encontrar uma instância muito ruim com muitas colisões, poderá repetir tudo usando um novo lote de números aleatórios.

Michael Nett
fonte
Se não me engano, isso sofre do mesmo problema que K&R 1st na resposta de Gabriel; ou seja, "ab" e "ba" terão hash no mesmo valor.
Johann Oskarsson