function hash para string

Eu estou trabalhando na tabela de hash na linguagem C e estou testando a function hash para string.

A primeira function que tentei é adicionar o código ascii e usar o modulo (% 100), mas obtive resultados ruins com o primeiro teste de dados: 40 colisões para 130 palavras.

Os dados de input finais conterão 8 000 palavras (é um dictionnary armazena 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 hashing string? e como determinar o tamanho da tabela de hash?

desde já, obrigado !

🙂

    Eu tive bons resultados com o djb2 por Dan 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 por padrões criptocharts ainda é terrivelmente lento por padrões de tabela de hash.

    Segundo, você quer garantir que cada bit da input possa afetar o resultado. Uma maneira fácil de fazer isso é girar o resultado atual por um certo número de bits, então XOR o código hash atual com o byte atual. Repita até chegar ao final da string. Note que você geralmente não quer que a rotação seja igual a um múltiplo do tamanho do byte.

    Por exemplo, assumindo o caso comum de bytes de 8 bits, você pode rotacionar por 5 bits:

     int hash(char const *input) { int result = 0x55555555; while (*input) { result ^= *input++; result = rol(result, 5); } } 

    Edit: Observe também que 10000 slots raramente é uma boa escolha para um tamanho de tabela de hash. Você geralmente quer 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 (assim, reduzir o valor para o intervalo correto pode ser feito com um simples bit-mask).

    A Wikipedia mostra uma bela function hash de string chamada Jenkins One At A Time Hash. 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; } 

    Há um número de implementações hashtable existentes para C, da biblioteca padrão C hcreate / hdestroy / hsearch, àquelas do APR e do glib , que também fornecem funções hash pré-construídas. Eu recomendaria altamente usar aqueles em vez de inventar sua própria function hashtable ou hash; eles foram otimizados fortemente para casos de uso comuns.

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

    Primeiro, são 40 colisões de 130 palavras para 0.99 ruins? Você não pode esperar hashing perfeito se você não está tomando medidas especificamente para que isso aconteça. Uma function hash comum não terá menos colisões do que um gerador random na maioria das vezes.

    Uma function hash com boa reputação é o MurmurHash3 .

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

    Eu tentei essas funções hash e obtive o seguinte resultado. Eu tenho cerca de 960 ^ 3 inputs, cada um com 64 bytes de comprimento, 64 caracteres em ordem diferente, valor de hash de 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 hash têm 6% de taxa de colisão para meus dados.

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

    Você precomputa uma tabela T com um número random para cada caractere no alfabeto da sua chave [0,255]. Você hash sua chave ‘k0 k1 k2 … kN’ tomando T [k0] xor T [k1] xor … xor T [kN]. Você pode facilmente mostrar que isso é tão random quanto o seu gerador de números randoms e seu computacionalmente muito viável e se você realmente se deparar com uma instância muito ruim com muitas colisões você pode simplesmente repetir a coisa toda usando um novo lote de números randoms.

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

    1) Aparentemente um algoritmo hash terrível , como apresentado em K & R 1ª edição ( 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, conforme apresentado na versão 2 do K & R (verificado por mim na p. 144 do livro); NB: não se esqueça de remover % HASHSIZE da instrução de retorno se você planeja fazer o tamanho do módulo para o comprimento da matriz fora do algoritmo de hash. Além disso, eu recomendo que você faça o retorno e “hashval” digite unsigned long vez do simples unsigned (int).

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

    Note que é claro a partir dos dois algoritmos que uma razão pela qual a primeira edição hash é tão terrível é porque ela não leva em consideração a ordem dos caracteres, então hash("ab") retornaria o mesmo valor que hash("ba") . Isso não é assim com o hash da segunda edição, no entanto, o que (muito melhor!) Retorna dois valores diferentes para essas cadeias.

    As funções de hashing 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(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(buf[2]) < < 16; [[gnu::fallthrough]]; case 2: hash ^= static_cast(buf[1]) < < 8; [[gnu::fallthrough]]; case 1: hash ^= static_cast(buf[0]); hash *= m; }; // Do a few final mixes of the hash. hash ^= hash >> 13; hash *= m; hash ^= hash >> 15; return hash; }