Tenha uma boa função hash para um C ++ tabela hash?

StackOverflow https://stackoverflow.com/questions/628790

  •  07-07-2019
  •  | 
  •  

Pergunta

Eu estou na necessidade de uma implementação de função hash orientada para o desempenho em C ++ para uma tabela hash que será codificação. Eu olhei em torno de questões já e só encontrados perguntando o que é uma boa função hash "em geral". Eu considerei CRC32 (mas onde encontrar boa implementação?) E alguns algoritmos de criptografia. Minha mesa, no entanto, tem exigências muito específicas.

Aqui está o que a tabela vai ser como: 

100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
     examples: "become"    "and he"    ", not "

O prioridade número um da minha tabela hash é rápida pesquisa (recuperação). Inserção rápida não é importante, mas ele vai vir junto com pesquisa rápida. Eliminação não é importante, e re-hash não é algo que eu vou estar olhando para. Para colisões punho, eu vou estar provavelmente usando encadeamento separado , conforme descrito aqui . Já olhou para este artigo , mas gostaria de uma opinião daqueles que têm tratado tais tarefa antes.

Foi útil?

Solução

Agora assumming você quer um hash, e quer algo super rápido que iria trabalhar no seu caso, porque suas cordas são apenas 6 caracteres longa que você poderia usar essa magia: 

size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
   return (*(size_t*)str)>> precision;
}

CRC é para slowpokes;)

Explicação: Isso funciona, lançando o conteúdo do ponteiro de string para "Olhe como" um size_t (int32 ou int64 baseado no jogo ideal para o seu hardware). Assim, o conteúdo da corda são interpretados como um número cru, não se preocupa com caracteres mais, e você, então bit-shift esta a precisão necessária (você ajustar este número para o melhor desempenho, eu encontrei 2 funciona bem para hash cordas em conjunto de alguns milhares).

Além disso, a parte realmente interessante é qualquer compilador decente em hardware moderno vai botar uma string como esta em 1 instrução de montagem, difícil de bater que;)

Outras dicas

Esta polinomial simples funciona surpreendentemente bem. I got it from Paul Larson da Microsoft Research que estudou uma ampla variedade de funções hash e multiplicadores de hash. 

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

salt deve ser inicializada com alguns aleatoriamente valor escolhido antes da hashtable é criado para se defender contra ataques de tabela de hash . Se isso não é um problema para você, é só usar 0.

O tamanho da tabela também é importante, para minimizar colisões. Sons como a sua é bom.

Boost.Functional / Hash pode ser de usar para você. Eu não tentei isso, então eu não posso garantir para o seu desempenho.

Aumento também tem um CRC biblioteca .

Gostaria de olhar um Boost.Unordered primeiro (boost :: ie unordered_map <>). Ele usa hash de mapas em vez de árvores binárias para contêineres.

Eu acredito que algumas implementações STL ter um recipiente hash_map <> no namespace stdext.

O tamanho da sua mesa vai ditar o tamanho de hash você deve usar. Você gostaria de minimizar colisões de curso. Eu não tenho certeza do que você está especificando por itens max e capacidade (que parece ser a mesma coisa para mim) Em qualquer caso qualquer um desses números sugerem que uma de 32 bits de hash seria suficiente. Você pode começar afastado com CRC16 (~ 65000 possibilidades), mas você provavelmente tem um monte de colisões de lidar. Por outro lado, uma colisão pode ser mais rápido para lidar do que do que um hash CRC32.

Eu diria, vai com CRC32. Você vai encontrar nenhuma escassez de documentação e código de exemplo. Desde que você tenha seus máximos descobriu e velocidade é uma prioridade, ir com uma matriz de ponteiros. Usar o hash para gerar um índice. Na colisão, o índice de incremento até você acertar um balde vazio .. rápido e simples.

Uma vez que você armazenar palavras em inglês, a maioria de seus personagens vão ser letras e não haverá muita variação nos mais significativos dois bits de seus dados. Além de que eu iria mantê-lo muito simples, basta usar XOR. Afinal, você não está olhando para a força de criptografia, mas apenas para uma distribuição razoavelmente uniforme. Algo ao longo destas linhas: 

size_t hash(const std::string &data) {
  size_t h(0);
  for (int i=0; i<data.length(); i++)
    h = (h << 6) ^ (h >> 26) ^ data[i];
  }
  return h;
}

Além disso, você já olhou para std :: tr1 :: hash como uma função hash e / ou std :: tr1 :: unordered_map como uma implementação de uma tabela hash? Usando estes provavelmente seria poupar muito trabalho oposição à implementação de suas próprias classes.

A prioridade número um da minha tabela hash é rápida pesquisa (recuperação).

Bem, então você está usando a estrutura de dados direito, como a procura em uma tabela hash é O (1)! :)

O CRC32 deve fazer bem. A implementação não é tão complexo, é baseado principalmente em XORs. Apenas certifique-se que ele usa uma boa polinomial.

Como sobre algo simples: 

// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];

// Hash function for six character strings.
int hash(const char *str)
{
    int ret = 0, mult = 1;
    for (const char *p = str; *p; *p++, mult *= 32) {
        assert(*p >= 0 && *p < 256);
        ret += mult * hashLookup[*p];
    }

    return ret;
}

Isso pressupõe 32 ints bits. Ele usa 5 bits por caractere, de modo que o valor de hash só tem 30 bits na mesma. Você poderia corrigir isso, talvez, através da geração de seis bits para o primeiro um ou dois caracteres. Se você conjunto de caracteres é pequeno o suficiente, você pode não precisar mais de 30 bits.

Se você precisa procurar seqüências curtas e de inserção não é um problema, talvez você poderia usar uma árvore-B, ou uma árvore de 2-3, você não ganhar muito hashing no seu caso.

A maneira como você faria isso é colocando uma carta em cada nó para que você verifique primeiro para o nó "a", então você verificar "a" 's crianças de 'p', e é as crianças para 'p', e, em seguida, "l" e "e". Em situações onde você tem "maçã" e "aplicar" você precisa procurar para o último nó, (uma vez que a única diferença é no último "e" e "y")

Mas, mas na maioria dos casos você vai ser capaz de obter a palavra depois de apenas alguns passos ( "xilofone" => "x" -> "ylophone"), para que possa optimizar assim. Isso pode ser mais rápido do que hash

Desde C ++ 11, C ++ tem proporcionado um std::hash< string >( string ) . Que é provável que seja uma função hash eficiente que fornece uma boa distribuição de Maconha códigos para a maioria das cordas.

Além disso, se você está pensando em implementar um hash-table, agora você deve estar pensando em usar um C ++ std::unordered_map .

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top