Cadeia rápido algoritmo de hashing com baixas taxas de colisão com 32 bit inteiro [fechado]
https://stackoverflow.com/questions/114085
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu tenho muitos não relacionados coisas nomeadas que eu gostaria de fazer pesquisas rápidas contra. Um "aardvark" é sempre uma "aardvark" em todos os lugares, então hash a corda e reutilizar o inteiro iria funcionar bem para acelerar as comparações. Todo o conjunto de nomes é desconhecido (e muda ao longo do tempo). O que é um algoritmo de seqüência rápida hashing que irá gerar pequena (32 ou 16) os valores de bit e ter uma taxa de colisão de baixo?
Eu gostaria de ver uma aplicação específica otimizado para C / C ++.
Solução
Um dos FNV variantes deve atender às suas necessidades. Eles são rápidos, e produzir resultados de forma bastante equilibrada distribuídos.
Outras dicas
Murmur Hash é bastante agradável.
Para uma gperf uso cadeia de conjunto fixo.
Se a seqüência-set muda você tem que escolher uma função hash. Esse tema tem sido discutido antes:
Qual é o melhor algoritmo de hash para o uso em uma string stl ao usar hash_map?
Há também um belo artigo em eternallyconfuzzled.com .
Jenkins' One-em-um-Time hash para cordas deve ser algo como isto:
#include <stdint.h>
uint32_t hash_string(const char * s)
{
uint32_t hash = 0;
for(; *s; ++s)
{
hash += *s;
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
Outra solução que poderia ser ainda melhor dependendo do seu caso de uso é internados cordas . Isto é como símbolos trabalhar por exemplo em Lisp.
Um internado corda é um objeto string cujo valor é o endereço dos bytes seqüência real. Então você cria um objeto string internados, verificando em uma tabela global: se a cadeia está lá, você inicializar a string internados para o endereço dessa cadeia. Se não, você inseri-lo, e, em seguida, iniciar sua seqüência internados.
Isto significa que duas cordas internados construídas a partir da mesma cadeia terão o mesmo valor, que é um endereço. Então, se N é o número de cordas internados em seu sistema, as características são:
- construção lenta (necessidades pesquisar e, possivelmente, a alocação de memória)
- Requer global de dados e sincronização no caso de concorrente tópicos
- Compare é O (1), porque você está comparando endereços, e não reais bytes de cordas (o que significa a classificação funciona bem, mas não vai ser uma espécie alfabética).
Cheers,
Carl
Por que você não apenas usar bibliotecas de impulso ? Sua função hash é simples de usar e a maioria das coisas no impulso em breve será parte do padrão C ++. Alguns dos que já é.
Aumento de hash é tão fácil quanto
#include <boost/functional/hash.hpp>
int main()
{
boost::hash<std::string> string_hash;
std::size_t h = string_hash("Hash me");
}
Você pode encontrar impulso em boost.org
Nunca é tarde para um bom assunto e estou certo que as pessoas estariam interessadas em minhas descobertas.
Eu precisava de uma função hash e depois de ler este post e fazer um pouco de pesquisa sobre as ligações dadas aqui, eu vim com essa variação do algoritmo de Daniel J Bernstein, que eu usei para fazer um teste interessante:
unsigned long djb_hashl(const char *clave)
{
unsigned long c,i,h;
for(i=h=0;clave[i];i++)
{
c = toupper(clave[i]);
h = ((h << 5) + h) ^ c;
}
return h;
}
Este hashes variação cordas ignorando o caso, que se adapte a minha necessidade de hashing usuários credenciais de login. 'Clave' é 'chave' em espanhol. Lamento para o espanhol, mas sua minha língua materna e o programa está escrito nele.
Bem, eu escrevi um programa que irá gerar nomes de usuário de 'test_aaaa' para 'test_zzzz', e -para fazer as cordas mais longo que eu adicionei a eles um domínio aleatório nesta lista: 'cloud-nueve.com', ' yahoo.com', 'gmail.com' e 'hotmail.com'. Portanto cada um deles seria parecido com:
test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, test_aaac@gmail.com, test_aaad@hotmail.com and so on.
Aqui está a saída do teste -'Colision Entre XXX XXX y' significa 'Colisão de XXX e XXX'. 'palavras' 'Palabras' meios e 'Total' é a mesma em ambas as línguas -.
Buscando Colisiones...
Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108)
Total de Colisiones: 11
Total de Palabras : 456976
Isso não é ruim, 11 colisões fora de 456976 (fora do curso usando o 32 bits full lenght como mesa).
A execução do programa usando 5 caracteres, que é de 'test_aaaaa' para 'test_zzzzz', realmente ficar sem memória construção da mesa. Abaixo é a saída. 'No hay memoria para insertar XXXX (insertadas XXX)' significa 'não há memória esquerda para inserir XXX (XXX inserido)'. Basicamente malloc () falhou nesse ponto.
No hay memoria para insertar 'test_epjcv' (insertadas 2097701).
Buscando Colisiones...
...451 'colision' strings...
Total de Colisiones: 451
Total de Palabras : 2097701
O que significa que apenas 451 colisões em 2,097,701 cordas. Note-se que em nenhuma das ocasiões, havia mais de 2 colisões por código. Que eu confirmar que é um grande hash para mim, como o que eu preciso é converter o ID de login para um de 40 bits ID único para a indexação. Então, eu uso isso para converter as credenciais de login para um pouco de hash 32 e usar o extra 8 bits para lidar com até 255 colisões por código, que lookign com os resultados de teste seria quase impossível gerar.
Hope isso é útil a alguém.
EDIT:
Como a caixa de teste é AIX, eu executá-lo usando LDR_CNTRL = MAXDATA = 0x20000000 para dar-lhe mais memória e correr mais, os resultados aqui:
Buscando Colisiones ... Total de Colisiones: 2908 Total de Palabras: 5366384
Isso é 2908 após 5.366.384 tentativas !!
MUITO IMPORTANTE : Compilando o programa com -maix64 (tão longo não assinado é de 64 bits), o número de colisões é 0 para todos os casos !!!
Tenha um olhar em GNU gperf .
Bob Jenkins tem muitas funções hash disponíveis , todos os quais são rápidos e têm taxas baixas de colisão.
Você pode ver o que .NET utiliza no método String.GetHashCode () com refletor.
Eu arriscaria um palpite de que a Microsoft passou um tempo considerável otimizar isso. Eles têm impressa em toda a documentação MSDN também que é sujeito a alterações o tempo todo. Então, claramente, é no seu "radar ajustes performance"; -)
Seria bastante trivial para a porta para C ++ também Eu teria pensado.
Há alguma boa discussão neste pergunta anterior
E uma boa visão geral de como escolher funções hash, bem como estatísticas sobre a distribuição de vários dos mais comuns aqui
Descrito aqui é uma maneira simples de implementar it yourself: http : //www.devcodenote.com/2015/04/collision-free-string-hashing.html
Um trecho do post:
se dizer que temos um conjunto de caracteres de letras maiúsculas inglesas, então o comprimento do conjunto de caracteres é de 26, onde A pode ser representado pelo número 0, B pelo número 1, C pelo número 2 e assim por diante até Z pelo número 25. Agora, sempre que queremos mapear uma sequência de caracteres deste conjunto de caracteres de um número único, realizamos a mesma conversão como fizemos no caso do formato binário
CRC-32 . Há cerca de um trilhão de links no Google para isso.
