função hash para string

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 !

:-)

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;
}

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).

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;
}

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.

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.

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.

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.

• Esta é uma resposta parcial à pergunta sobre quais são as funções de hash do GCC C ++ 11 usadas , afirmando que o GCC usa uma implementação de "MurmurHashUnaligned2", de Austin Appleby ( http://murmurhash.googlepages.com/ ).
• No arquivo "gcc / libstdc ++ - v3 / libsupc ++ / hash_bytes.cc", aqui ( https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc ), encontrei as implementações. Aqui está o valor de retorno "32-size size_t", por exemplo (extraído em 11 de agosto de 2017):

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;
}

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.

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.