Por que um balde de hashtable leva um número privilegiado?
Tem uma função de hash
H (c) = c % n;
Quando n leva um número composto, o exemplo mais simples é levar 2^n, por exemplo, tomar 2^3 = 8, neste momento
H (11100 (binário)) = h (28) = 4
H (10100 (binário)) = h (20) = 4
Neste momento, o 4º bit de binário (da direita para a esquerda) de C "falhará", o que significa que, independentemente do valor que seja obtido no quarto bit de C, ele levará ao mesmo valor de H (c). Nesse momento, o quarto bit de C não participa da operação de H (c), portanto, H (c) não pode refletir completamente as características de C, aumentando a chance de conflito.
Ao tomar outros números compostos, alguns bits de C terão "falhado" em variar graus, resultando em conflitos em alguns aplicativos comuns.
No entanto, levar números primos pode basicamente garantir que cada bit de C participe da operação de H (c), reduzindo assim a chance de conflito em aplicações comuns. ．
(Opinião pessoal: às vezes a eficiência de não tomar números primos não é tão ruim ... mas é sem dúvida mais seguro levar números primos ...)
O exposto acima é o meu entendimento
Para acrescentar a isso, isso significa que, em aplicações comuns, alguns dados geralmente são semelhantes. É melhor usar números primos no momento. Por exemplo, os dados a serem armazenados estão em um estado compactado, como armazenar uma tabela que descreve o estado de pesquisa atual. Neste momento, a probabilidade de hash sem números primos é relativamente alta.
Se for um número inteiro distribuído aleatoriamente, o módulo de hash será o mesmo, desde que seja levado o suficiente, mas isso está obviamente fora de aplicação prática.
O que você disse é uma situação especial, porque quando um número privilegiado relativamente pequeno é selecionado, quando o grande número n grande é selecionado, ele só pode falhar em um certo bit do sistema N-dígito. Combinada com as características do sistema de computador, a representação de dígitos N geralmente não é crítica, enquanto o sistema de 2 dígitos comumente usado é mais crítico, portanto, os conflitos podem ser evitados.
De fato, usei alguns grandes números para testá -lo para armazenar uma matriz de adjacência compactada em binário. Quando o módulo é grande o suficiente, mesmo o número composto pode ter um efeito muito próximo do número primo, mas em algumas (várias dezenas) de números, a eficiência será severamente reduzida, portanto os números primos são relativamente seguros.
Você também pode fazer seus próprios experimentos, não escolher números inteiros aleatórios, mas considerar algumas aplicações comuns, usar números primos e números compostos para testar, examinando principalmente o fator de carregamento médio, e a conclusão que você obtém pode ser a mesma que o meu: os números compostos também são bons na maioria das vezes, mas o efeito é surpreendentemente ruim em alguns números compostos e quase todos os números primários têm bons resultados.
Pessoalmente, acho que, em um sentido mais geral, se você não tomar números primos, haverá algum perigo. O perigo ocorre quando o número não prior M = x*y é considerado selecionado e, se a chave do hash estiver relacionada a esse divisor x, será infeliz. Na pior das hipóteses, supõem que são múltiplos de x, então você pode imaginar que o resultado do hash é: 1 ~ y, não 1 ~ m. No entanto, se o tamanho do balde for selecionado como um número primo, não haverá problema.
Obrigado pela leitura, espero que isso possa ajudá -lo. Obrigado pelo seu apoio a este site!