Esses dois números são números primos suficientemente grandes. Por favor, leia o artigo na tabela de hash na Wikipedia para mais informações.
Boris Pavlović
Respostas:
140
1231 e 1237 são apenas dois números primos arbitrários (suficientemente grandes) . Quaisquer outros dois grandes números primos serviriam bem.
Por que primos?
Suponha por um segundo que escolhemos números compostos (não primos), digamos 1000 e 2000. Ao inserir booleanos em uma tabela hash, verdadeiro e falso iriam para o balde 1000 % Nresp 2000 % N(onde Né o número de baldes).
Agora observe que
1000 % 8 mesmo balde que 2000 % 8
1000 % 10 mesmo balde que 2000 % 10
1000 % 20 mesmo balde que 2000 % 20
....
em outras palavras, isso levaria a muitas colisões .
Isso ocorre porque a fatoração de 1000 (2 3 , 5 3 ) e a fatoração de 2000 (2 4 , 5 3 ) têm muitos fatores comuns. Assim, os números primos são escolhidos, uma vez que é improvável que tenham quaisquer fatores comuns com o tamanho do balde.
Por que grandes primos. 2 e 3 não serviriam?
Ao calcular códigos hash para objetos compostos, é comum adicionar os códigos hash para os componentes. Se valores muito pequenos forem usados em um conjunto hash com um grande número de depósitos, há o risco de acabar com uma distribuição desigual de objetos.
As colisões importam? Os booleanos simplesmente têm dois valores diferentes?
Os mapas podem conter booleanos junto com outros objetos. Além disso, como apontado por Drunix, uma maneira comum de criar funções hash de objetos compostos é reutilizar as implementações de código hash dos subcomponentes, caso em que é bom retornar grandes números primos.
Suponho que sejam suficientemente grandes. Para obter um mdc maior que 1, você precisaria de pelo menos 2*1231 = 2462baldes. As colisões são um problema em tal situação?
aioobe,
2
No entanto, é interessante que eles não sejam realmente "bastante grandes", considerando o que pode caber em um int. Suponho que sejam grandes o suficiente para funcionar bem com o JDK Hashtable, mas ainda pequenos o suficiente para minimizar os custos de cálculo.
Thilo,
2
Sim, ele me surpreendeu muito que eles não são que grande. Mas você acredita que há um custo maior com primos maiores?
aioobe,
3
@Thilo, você precisaria de um múltiplo de 1231 * 1237 = 1.522.747 baldes antes de colidirem, o que é bastante grande
aberração da catraca
2
Eu diria que levar a colisões com a contagem de baldes não é realmente um problema com booleano, mas mais a construção comum de como obtemos o hascode de um objeto composto, ou seja, multiplicando os hashcodes dos componentes com algumas constantes e somando-os.
Drunix,
2
Além de tudo o que foi dito acima, também pode ser um pequeno ovo de páscoa dos desenvolvedores:
verdadeiro: 1231 => 1 + 2 + 3 + 1 = 7
7 - é um número da sorte nas tradições europeias;
falso: 1237 => 1 + 2 + 3 + 7 = 13
13 (também conhecido como a dúzia do Diabo) - número do azar.
Respostas:
1231 e 1237 são apenas dois números primos arbitrários (suficientemente grandes) . Quaisquer outros dois grandes números primos serviriam bem.
Por que primos?
Suponha por um segundo que escolhemos números compostos (não primos), digamos 1000 e 2000. Ao inserir booleanos em uma tabela hash, verdadeiro e falso iriam para o balde
1000 % Nresp2000 % N(ondeNé o número de baldes).Agora observe que
1000 % 8mesmo balde que2000 % 81000 % 10mesmo balde que2000 % 101000 % 20mesmo balde que2000 % 20em outras palavras, isso levaria a muitas colisões .
Isso ocorre porque a fatoração de 1000 (2 3 , 5 3 ) e a fatoração de 2000 (2 4 , 5 3 ) têm muitos fatores comuns. Assim, os números primos são escolhidos, uma vez que é improvável que tenham quaisquer fatores comuns com o tamanho do balde.
Por que grandes primos. 2 e 3 não serviriam?
Ao calcular códigos hash para objetos compostos, é comum adicionar os códigos hash para os componentes. Se valores muito pequenos forem usados em um conjunto hash com um grande número de depósitos, há o risco de acabar com uma distribuição desigual de objetos.
As colisões importam? Os booleanos simplesmente têm dois valores diferentes?
Os mapas podem conter booleanos junto com outros objetos. Além disso, como apontado por Drunix, uma maneira comum de criar funções hash de objetos compostos é reutilizar as implementações de código hash dos subcomponentes, caso em que é bom retornar grandes números primos.
Perguntas relacionadas:
fonte
2*1231 = 2462baldes. As colisões são um problema em tal situação?Além de tudo o que foi dito acima, também pode ser um pequeno ovo de páscoa dos desenvolvedores:
7 - é um número da sorte nas tradições europeias;
13 (também conhecido como a dúzia do Diabo) - número do azar.
fonte