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

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

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, 22 \dots$$1, 12, 23 \dots$

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

resultaria em uma tabela de hash com valores no primeiro intervalo, etc. no segundo e assim por diante.$0, 12, 24 \dots$$1, 13, 25 \dots$

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.

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 $K=\{0,1,...,100\}$$m=12$$3$$12$$3$$3$

• As chaves serão hash no intervalo .$\{0,12,24,36,...\}$$0$
• As chaves serão hash no bucket .$\{3,15,27,39,...\}$$3$
• As chaves serão hash no balde .$\{6,18,30,42,...\}$$6$
• As chaves serão hash no bucket .$\{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 $K$$K$$m$$K$$3$$3$

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 /$4$$m$$4$$3m/4$$m/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.$K$$m$

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 $m$$K$$m$

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 $a+k\cdot b$$H(n)=n \bmod m$$b$$n$$b$

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 $11$$12$$11$$2$$3$$12$

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 , $a$$a + i^2$$i=1,2,\dots$

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 $p$$p$$3$

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 $p$$p$$i^2=c$$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\times k \mod m$$m$$a$$1\over m$$m=1009$$Pr\{h(x)=h(y), x\neq y\}=0.00099108027$

Esse esquema é conhecido como: Hashing Universal.