É possível combinar códigos de hash para membros privados para gerar um novo código de hash?

Question

Eu tenho um objeto para o qual eu quero gerar um hash exclusivo (GetHashCode override ()), mas eu quero evitar excessos ou algo imprevisível.

O código deve ser o resultado de combinar os códigos de hash de uma pequena coleção de strings.

Os códigos de hash será parte de gerar uma chave de cache, portanto o ideal seria que deve ser único no entanto, o número de possíveis valores que estão sendo hash é pequeno, então eu acho probabilidade é a meu favor aqui.

Será que algo como isso ser suficiente E há uma maneira melhor de fazer isso?

int hash = 0;
foreach(string item in collection){
    hash += (item.GetHashCode() / collection.Count)
}
return hash;

EDIT: Obrigado por respostas até agora. @ Jon Skeet: Não, a ordem não é importante

Eu acho que isso é quase uma outra pergunta, mas desde que eu estou usando o resultado de gerar uma chave de cache (string) faria sentido usar uma função hash criptográfica como MD5 ou apenas usar a representação em cadeia deste int?

Answer 1

Os fundamentos apontado por Marc e Jon não são ruins, mas eles estão longe de ser ideal em termos de uniformidade de distribuição dos resultados. Infelizmente, a 'multiplicar por primos' abordagem copiado por tantas pessoas de Knuth é não a melhor escolha em muitos casos melhor distribuição pode ser alcançado por mais barato para calcular funções (embora este é muito ligeira em hardware moderno). Na verdade jogando primos em muitos aspectos de hashing é nenhuma panacéia .

Se estes dados são utilizados para tabelas de hash significativamente tamanho eu recomendo a leitura de excelente estudo e explicação de Bret Mulvey de várias técnicas modernas (e não tão modernos) hash com folga feito com c #.

Note que o comportamento com cordas de várias funções hash é fortemente inclinado para wehther as cordas são curtas (grosso modo quantos caracteres são misturados antes de os bits começam a mais de fluxo) ou longo prazo.

Uma das mais simples e mais fácil de implementar também é um dos melhores, o Jenkins Um de cada hash de tempo.

private static unsafe void Hash(byte* d, int len, ref uint h)
{
    for (int i = 0; i < len; i++)
    {
        h += d[i];
        h += (h << 10);
        h ^= (h >> 6);
    }
}

public unsafe static void Hash(ref uint h, string s)
{
    fixed (char* c = s)            
    {
        byte* b = (byte*)(void*)c;
        Hash(b, s.Length * 2, ref h);
    }
}

public unsafe static int Avalanche(uint h)
{
    h += (h<< 3);   
    h ^= (h>> 11);  
    h += (h<< 15);  
    return *((int*)(void*)&h);
}

Você pode então usar esta assim:

uint h = 0;
foreach(string item in collection) 
{
    Hash(ref h, item);
}
return Avalanche(h);

Você pode mesclar vários tipos diferentes assim:

public unsafe static void Hash(ref uint h, int data)
{ 
    byte* d = (byte*)(void*)&data;
    AddToHash(d, sizeof(int), ref h);
}

public unsafe static void Hash(ref uint h, long data)
{ 
    byte* d= (byte*)(void*)&data;
    Hash(d, sizeof(long), ref h);
}

Se você só tem acesso ao campo como um objeto sem o conhecimento dos internos você pode simplesmente chamar GetHashCode () em cada um e combinar esse valor como assim:

uint h = 0;
foreach(var item in collection) 
{
    Hash(ref h, item.GetHashCode());
}
return Avalanche(h);

Infelizmente você não pode fazer sizeof (T) para que você deve fazer cada struct individualmente.

Se você deseja usar a reflexão que você pode construir em uma base por tipo uma função que faz a identidade estrutural e hashing em todos os campos.

Se você quiser evitar código inseguro, então você pode usá-bit mascaramento técnicas para retirar pedaços individuais de ints (e caracteres se tratar de cordas) com problemas não muito extra.

Answer 2

Hashes não são significava de ser único - eles estão apenas a intenção de ser bem distribuídas na maioria das situações. Eles estão apenas pretende ser consistente. Note-se que transborda não deve ser um problema.

Apenas adicionando geralmente não é uma boa idéia, e dividindo certamente não é. Aqui é a abordagem que eu costumo usar:

int result = 17;
foreach (string item in collection)
{
    result = result * 31 + item.GetHashCode();
}
return result;

Se você é de outra forma em um contexto marcada, você pode querer fazer deliberadamente a opção desligada.

Note que isto assume que a ordem é importante, ou seja, que { "a", "b"} deve ser diferente do { "b", "a"}. Por favor, deixe-nos saber se esse não é o caso.

Answer 3

Não há nada de errado com essa abordagem, desde que os membros cujos hashcodes você está combinando seguir as regras de códigos de hash. Em suma ...

1. O código hash dos membros privados não deve mudar para a vida útil do objeto
2. O recipiente não deve alterar o objeto os membros privados apontam para para que não na mudança por sua vez, o código de hash do recipiente

Answer 4

Se a ordem dos itens não é importante (ou seja, { "a", "b"} é o mesmo que { "b", "a"}), então você pode usar exclusivo ou para combinar os códigos de hash:

hash ^= item.GetHashCode();

[Edit: Como Mark apontou em um comentário a uma resposta diferente, isto tem a desvantagem de também dar coleções como { "a"} e { "a", "b", "b"} o mesmo código hash .]

Se a ordem é importante, você pode em vez multiplicar por um número primo e adicionar:

hash *= 11;
hash += item.GetHashCode();

(Quando você multiplicar às vezes você vai obter uma sobrecarga que é ignorado, mas multiplicando com um número primo você perde um mínimo de informação. Se você em vez multiplicado com um número como 16, você perderia quatro bits de informação de cada vez , então depois de oito itens do código de hash do primeiro item seria completamente desaparecido.)