Por que é melhor usar um número primo como um mod em uma função de hash?

58

Se eu tenho uma lista de valores-chave de 1 a 100 e quero organizá-los em uma matriz de 11 intervalos, fui ensinado a formar uma função mod

H=kmod 11

Agora todos os valores serão colocados um após o outro em 9 linhas. Por exemplo, no primeiro intervalo, haverá . No segundo, haverá etc.0,11,221,12,23

Digamos que eu decidi ser um garoto mau e usar um não primo como minha função de hash - pegue 12. Usando a função Hashing

H=kmod 12

resultaria em uma tabela de hash com valores no primeiro intervalo, etc. no segundo e assim por diante.0,12,241,13,25

Essencialmente, eles são a mesma coisa. Não reduzi colisões e não espalhei melhor as coisas usando o código hash do número primo e não consigo ver como isso é benéfico.

CodyBugstein
fonte
Pergunta relevante, por que usamos o xor na função hash stackoverflow.com/questions/5889238/… #
shuva

Respostas:

63

Considere o conjunto de chaves e uma tabela de hash em que o número de buckets é . Como é um fator , as chaves que são múltiplos de serão divididas em hash para baldes que são múltiplos de :m = 12 3 12 3 3K={0,1,...,100}m=1231233

  • As chaves serão hash no intervalo .0{0,12,24,36,...}0
  • As chaves serão hash no bucket .3{3,15,27,39,...}3
  • As chaves serão hash no balde .6{6,18,30,42,...}6
  • As chaves serão hash no bucket .9{9,21,33,45,...}9

Se é distribuído uniformemente (ou seja, todas as chaves em têm a mesma probabilidade de ocorrer), então a escolha de não é tão crítica. Mas, o que acontece se não for distribuído uniformemente? Imagine que as chaves com maior probabilidade de ocorrência são os múltiplos de . Nesse caso, todos os buckets que não sejam múltiplos de ficarão vazios com alta probabilidade (o que é realmente ruim em termos de desempenho da tabela de hash).K m K 3 3KKmK33

Essa situação é mais comum do que parece. Imagine, por exemplo, que você esteja acompanhando os objetos com base em onde eles estão armazenados na memória. Se o tamanho da palavra do computador for de quatro bytes, você usará chaves de hash com múltiplos de . Escusado será dizer que escolher como um múltiplo de seria uma escolha terrível: você teria baldes de completamente vazios e todas as suas chaves colidiriam nos baldes de restantes .m 4 3 m / 4 m / 44m43m/4m/4

Em geral:

Cada chave em que compartilha um fator comum com o número de buckets será dividida em hash em um bucket que é múltiplo desse fator.mKm

Portanto, para minimizar as colisões, é importante para reduzir o número de factores comuns entre e os elementos de . Como isso pode ser alcançado? Escolhendo para ser um número com poucos fatores: um número primo .K mmKm

Mario Cervera
fonte
Acabei de ver que minha consulta está alinhada com a sua resposta. Você acha que a função hash na minha consulta é válida?
overexchange
@overexchange: respondi à sua pergunta. Esta resposta também pode ser do seu interesse.
Mario Cervera
por que é que a escolha de m só importa se K está distorcido? não é verdade que teremos desempenho pior com m ruim, mesmo que K seja distribuído uniformemente?
Vorou
Depende do que você quer dizer com "bad ". Se você quer dizer "pequeno em comparação com o número de elementos na tabela de hash" (ou seja, alto fator de carga ), o desempenho será baixo. No entanto, se você quer dizer "não primo", esse fato não é tão importante se todas as chaves forem igualmente prováveis, porque elas serão distribuídas uniformemente na tabela de hash. A pergunta em si fornece um exemplo. m
Mario Cervera
16

Se uma colisão é menos provável usando números primos depende da distribuição de suas chaves.

Se muitas de suas chaves tiverem o formato sua função hash for , essas chaves direcionadas para um pequeno subconjunto dos buckets se if dividir . Portanto, você deve minimizar o número de , o que pode ser alcançado escolhendo um primo.H ( n ) = n mod m b n ba+kbH(n)=nmodmbnb

Se, por outro lado, você gosta de ter de a baldes e sabe que as diferenças que são múltiplos de são mais prováveis ​​do que as diferenças que são múltiplos de e , você pode escolher para sua aplicação muito especial.12 11 2 3 121112112312

frafl
fonte
11
Mas se minhas chaves não tiverem o formato então não importa? Isso está certo? ma+k×bm
CodyBugstein
11
@lmray, se suas chaves são distribuídas uniformemente, não importa. Caso contrário, dependerá da distribuição de precisão para que seja importante ou não. mmm
APROGRAMMER #
Acabei de reverter a última edição, esqueci que . 12>11
frafl
3
Você quis dizer que "vá para um pequeno subconjunto dos baldes se divide "? mbm
Mikhail Dubov
8

Se isso tem impacto (também) depende de como você trata as colisões. Ao usar algumas variantes de hash aberto , o uso de números primos garante que slots vazios sejam encontrados desde que a tabela esteja suficientemente vazia.

Tente mostrar o seguinte, por exemplo:

Suponha que desejamos inserir um elemento que use hashes para endereçar e resolver colisões, tentando as posições posteriormente para .a + i 2 i = 1 , 2 , aa+i2i=1,2,

Mostre que este procedimento sempre gera uma posição vazia se a tabela de hash for do tamanho , um primo maior que e pelo menos metade de todas as posições estiverem livres.p 3pp3

Dica: Use o fato de que o módulo de anel da classe de resíduos é um campo se for primo e, portanto, tem no máximo soluções.p i 2 = c 2ppi2=c2

Rafael
fonte
2

Se a sua função hash tiver a forma onde é primo e é escolhido aleatoriamente, a probabilidade de duas chaves distintas serem hash no mesmo intervalo é de . Portanto, para , que é muito pequeno.h(k)=a×kmodmma1mm=1009Pr{h(x)=h(y),xy}=0.00099108027

Esse esquema é conhecido como: Hashing Universal.

saadtaame
fonte