Será que o hash função em STL dar 1-1 mapeamento entre char * e size_t?
Pergunta
Eu tenho um par
Eu sei o valor da pair.first não pode ter mais que 1000.
Sei também que o pair.second, a corda, é sempre uma palavra. Nunca mais de 1 palavra.
Assim, para construir o valor de hash para o par que eu estou fazendo o seguinte:
pair<int,string> p;
hash<char*> H;
hash_vale = H(p.second)*1000 + p.first;
Eu acho que isso vai dar valores únicos, desde que o valor de hash de cordas não é muito grande e que H (p.second) dará 1-1 mapeamentos. São estes pressupostos válido?
Obrigado,
Solução
Por definição, um hash não pode ser um-para-um, devido ao princípio da escaninho. Isto é, existem 2 ^ 32 possíveis valores hash, mas muito mais possíveis cadeias de caracteres. Portanto, deve haver duas cordas com o mesmo valor hash.
Em segundo lugar, você está quase certamente causando estouro multiplicando o seu valor de hash em 1000, uma vez que um hash deve usar todos os 32 bits. Você está muito melhor hash da int e, em seguida, misturar os hashes. Impulso tem uma função hash_combine
: a + 0x9e3779b9 + (b << 6) + (b >> 2);