É possível implementar uma tabela de hash bem distribuída sem usar o operador%?

11

Estou procurando implementar uma tabela de hash rápida e bem distribuída em C #. Estou tendo problemas para escolher minha função de restrição de hash que usa um código de hash arbitrário e a "restringe" para que possa ser usada para indexar os buckets. Existem duas opções que vejo até agora:

  • Por um lado, você pode garantir que seus depósitos sempre tenham um número primo de elementos e, para restringir o hash, basta modulá-lo pelo número de depósitos. Na verdade, é isso que o Dicionário do .NET faz . O problema com essa abordagem é que o uso de% é extremamente lento em comparação com outras operações; se você olhar para as tabelas de instruções do Agner Fog , idiv(que é o código de montagem gerado para%), possui uma latência de instruções de ~ 25 ciclos para os processadores Intel mais novos. Compare isso com cerca de 3 por mul, ou 1 para ops bit a bit como and, orou xor.

  • Por outro lado, você pode ter o número de buckets sempre com uma potência de 2. Você ainda precisará calcular o módulo do hash para não tentar indexar fora da matriz, mas desta vez será menos caro . Como as potências de 2 % Nsão justas & (N - 1), a restrição é reduzida a uma operação de mascaramento que leva apenas 1-2 ciclos. Isso é feito pelo esparso do Google . A desvantagem disso é que estamos contando com os usuários para fornecer bons hashes; mascarar o hash corta essencialmente parte do hash, portanto, não estamos mais levando em consideração todos os bits do hash. Se o hash do usuário é distribuído de maneira desigual, por exemplo, apenas os bits mais altos são preenchidos ou os bits mais baixos são sempre os mesmos, então essa abordagem tem uma taxa muito maior de colisões.

Estou procurando um algoritmo que eu possa usar que tenha o melhor dos dois mundos: leva em consideração todos os bits do hash e também é mais rápido do que usar%. Ele não precisa necessariamente ser um módulo, apenas algo que está garantido no intervalo 0..N-1(onde N é o comprimento dos baldes) e tem distribuição uniforme para todos os slots. Existe um algoritmo desse tipo?

Obrigado por ajudar.

James Ko
fonte
1
Procure o efeito avalanche , bem como a explicação em murmurhash3 (smhasher) . No entanto, o ponto fundamental da sua pergunta não é abordado com a adoção de uma melhor função de hash. Em vez disso, é uma pergunta sobre por que os usuários não adotam a mesma melhor função de hash e uma solicitação de contramedidas (como se os usuários fossem maliciosamente preguiçosos).
rwong 6/09/16
Para módulo rápido (2^N +/- 1), consulte stackoverflow.com/questions/763137/…
rwong 6/16
@rwong Sinto muito, mas não tenho certeza do que seu comentário tem a ver com o meu post. Eu não controlo o hash fornecido pelo usuário, portanto, não estou procurando uma função de hash melhor. Também não entendo o que você entende por "usuários maliciosamente preguiçosos".
James Ko
4
Se a função hash for ruim, não há nada que o implementador da tabela de hash possa fazer para "corrigir" a distribuição ruim. Módulo um número primo não repara um hash ruim. Considere uma função hash produzindo como saída múltiplos de um número primo. Eu já vi esse problema no código de produção real.
31816 Frank Hileman #

Respostas:

9

Implementações modernas de tabela de hash não usam a função modulo. Eles geralmente usam energia de duas tabelas de tamanho e cortam bits desnecessários. Uma função de hash ideal permitiria isso. O uso do módulo combinado com tamanhos de tabela com números primos surgiu nos dias em que as funções de hash eram geralmente ruins, pois geralmente estão no desenvolvimento .net. Eu recomendo ler sobre o SipHash , uma função de hash moderna, e depois ler sobre outras funções modernas, como xxHash .

Devo explicar por que as funções de hash .net geralmente são ruins. No .net, os programadores geralmente são forçados a implementar funções de hash, substituindo o GetHashcode. Mas o .net não fornece as ferramentas necessárias para garantir que as funções criadas pelo programador sejam de alta qualidade, a saber:

  • encapsulamento do estado de hash em uma estrutura ou classe
  • funções hash "add", que adicionam novos dados ao estado hash (adicione uma matriz de bytes ou um duplo, por exemplo)
  • uma função hash "finalize", para produzir a avalanche
  • encapsulamento do resultado do hash - no .net, você tem uma opção, um inteiro assinado de 32 bits.

Para obter mais informações sobre o uso de um resultado da função hash como um índice de tabela de hash, consulte as definições de formas universais de hash neste documento: Hash universal mais rápido de 64 bits usando multiplicações carry-less

Frank Hileman
fonte
3

Para usar AND enquanto mantém todos os bits, use o XOR também.

Por exemplo temp = (hash & 0xFFFF) ^ ( hash >> 16); index = (temp & 0xFF) ^ (temp >> 8);,.

Para este exemplo, não há módulo e todos os 32 bits de hashefeito em 8 bits index. No entanto, se é mais rápido que o DIV é algo que depende de muitos fatores e, em alguns casos, pode ser mais lento que o DIV (por exemplo, hash grande e índice pequeno).

Brendan
fonte
Isso sempre será mais rápido que o DIV / IDIV, no entanto, acho que não responde à minha pergunta - indexestará no intervalo [0..255]. Preciso de algo no intervalo [0..n-1], onde nestá o número de baldes.
James Ko
@ JamesKo Mas se você está implementando um dicionário, também controla o número de buckets (até certo ponto). Então, em vez de números primos, você pode escolher potências de dois. (Se isso seria realmente uma boa idéia, eu não posso te dizer.)
svick
@svick Para potências de 2, poderíamos fazer uma operação simples de máscara. Como mencionado na pergunta, estou procurando uma maneira barata de fazer isso com números primos, para que até os hashes mal distribuídos sejam acomodados.
James Ko
1

Você pode tirar vantagem do fato de que muitos números inteiros primos têm uma inversa multiplicativa modular. Veja este artigo . Você atendeu a uma das restrições ao tornar o índice do seu depósito principal e o módulo 2 ^ n, que são inerentemente relativamente primos.

O artigo descreve o algoritmo para encontrar um número tal que multiplicar por esse número e ignorar o estouro produzirá o mesmo resultado como se você tivesse dividido pelo tamanho do índice do bloco.

BobDalgleish
fonte