Há muito tempo, comprei um livro de estruturas de dados da tabela de pechinchas por US $ 1,25. Nele, a explicação para uma função de hash dizia que ela deveria ser modificada por um número primo por causa da "natureza da matemática".

O que você espera de um livro de US $ 1,25?

Enfim, tive anos para pensar sobre a natureza da matemática e ainda não consigo descobrir.

A distribuição dos números é realmente mais uniforme quando há um número primo de baldes? Ou isso é um conto antigo de programador que todo mundo aceita porque todo mundo aceita?

Geralmente, uma função simples de hash funciona pegando as "partes componentes" da entrada (caracteres no caso de uma string) e multiplicando-as pelos poderes de alguma constante e adicionando-as em algum tipo inteiro. Portanto, por exemplo, um hash típico (embora não especialmente bom) de uma sequência pode ser:

(first char) + k * (second char) + k^2 * (third char) + ...

Então, se um punhado de strings, todas com o mesmo primeiro caractere, forem alimentadas, os resultados serão todos do mesmo módulo k, pelo menos até o tipo inteiro exceder.

[Como exemplo, o hashCode da string de Java é estranhamente semelhante a isso - ele faz a ordem inversa dos caracteres, com k = 31. Portanto, você obtém relações de módulo 31 entre seqüências que terminam da mesma maneira e relações de módulo 2 ^ 32 entre seqüências que são iguais, exceto no final. Isso não atrapalha seriamente o comportamento de hashtable.]

Uma hashtable funciona assumindo o módulo do hash sobre o número de buckets.

Em uma hashtable, é importante não produzir colisões para casos prováveis, pois as colisões reduzem a eficiência da hashtable.

Agora, suponha que alguém coloque um monte de valores em uma hashtable que tenha algum relacionamento entre os itens, como todos tendo o mesmo primeiro caractere. Esse é um padrão de uso bastante previsível, eu diria, portanto não queremos que ele produza muitas colisões.

Acontece que "devido à natureza da matemática", se a constante usada no hash e o número de buckets forem coprimes , as colisões serão minimizadas em alguns casos comuns. Se eles não são coprime, existem alguns relacionamentos bastante simples entre entradas para as quais as colisões não são minimizadas. Todos os hashes saem iguais ao fator comum, o que significa que todos caem no 1/1 dos baldes que têm esse valor modulado no fator comum. Você recebe n vezes mais colisões, onde n é o fator comum. Como n é pelo menos 2, eu diria que é inaceitável que um caso de uso bastante simples gere pelo menos o dobro de colisões do que o normal. Se algum usuário dividir nossa distribuição em buckets, queremos que seja um acidente estranho, não um uso previsível simples.

Agora, implementações de hashtable obviamente não têm controle sobre os itens colocados nelas. Eles não podem impedir que eles sejam relacionados. Portanto, a coisa a fazer é garantir que a constante e a contagem do balde sejam coprime. Dessa forma, você não depende apenas do "último" componente para determinar o módulo do bucket em relação a algum pequeno fator comum. Até onde eu sei, eles não precisam ser os melhores para conseguir isso, apenas coprime.

Mas se a função hash e a hashtable forem gravadas independentemente, a hashtable não saberá como funciona a função hash. Pode estar usando uma constante com pequenos fatores. Se você tiver sorte, pode funcionar de maneira completamente diferente e não linear. Se o hash for bom o suficiente, qualquer contagem de buckets será boa. Mas uma hashtable paranóica não pode assumir uma boa função de hash, portanto, use um número primo de buckets. Da mesma forma, uma função hash paranóica deve usar uma constante prime grande, para reduzir a chance de alguém usar vários buckets que, por acaso, possuem um fator comum com a constante.

Na prática, acho bastante normal usar uma potência de 2 como o número de baldes. Isso é conveniente e evita a necessidade de procurar ou pré-selecionar um número primo da magnitude certa. Portanto, você depende da função hash para não usar multiplicadores, o que geralmente é uma suposição segura. Mas você ainda pode obter comportamentos ocasionais de hash ruim com base em funções de hash como a acima, e a contagem principal de buckets pode ajudar ainda mais.

Adotar o princípio de que "tudo tem que ser primordial" é, tanto quanto eu conheço, uma condição suficiente, mas não necessária, para uma boa distribuição das hashtables. Ele permite que todos interoperem sem precisar assumir que os outros seguiram a mesma regra.

[Editar: há outro motivo mais especializado para usar um número primo de caçambas, ou seja, se você lidar com colisões com sondagem linear. Em seguida, você calcula um passo a partir do código de hash e, se esse passo for um fator da contagem de buckets, você só poderá fazer análises (bucket_count / stride) antes de voltar para onde começou. O caso que você mais deseja evitar é stride = 0, é claro, que deve ter uma caixa especial, mas para evitar também uma caixa especial bucket_count / stride igual a um número inteiro pequeno, você pode simplesmente fazer o bucket_count ser primo e não se importar com o que passo é fornecido, não é 0.]

A primeira coisa que você faz ao inserir / recuperar da tabela de hash é calcular o hashCode para a chave especificada e, em seguida, encontrar o intervalo correto aparando o hashCode no tamanho da hashTable executando hashCode% table_length. Aqui estão duas 'declarações' que você provavelmente já leu em algum lugar

1. Se você usar uma potência de 2 para table_length, encontrar (hashCode (key)% 2 ^ n) é tão simples e rápido quanto (hashCode (key) & (2 ^ n -1)). Mas se sua função de calcular o hashCode para uma determinada chave não for boa, você definitivamente sofrerá com o agrupamento de muitas chaves em alguns buckets de hash.
2. Mas se você usar números primos para table_length, os hashCodes calculados poderão mapear para os diferentes buckets de hash, mesmo se você tiver uma função hashCode um pouco estúpida.

E aqui está a prova.

Se suponha que sua função hashCode resulte nos seguintes códigos hash, entre outros {x, 2x, 3x, 4x, 5x, 6x ...}, todos eles serão agrupados em apenas m número de buckets, em que m = table_length / GreatestCommonFactor (comprimento_tabela, x). (É trivial verificar / derivar isso). Agora você pode executar um dos seguintes procedimentos para evitar o armazenamento em cluster

Certifique-se de não gerar muitos códigos de hash múltiplos de outro código de hash como em {x, 2x, 3x, 4x, 5x, 6x ...}. Mas isso pode ser um pouco difícil se a sua hashTable tiver milhões de entradas. Ou simplesmente faça m igual ao comprimento da tabela, tornando GreatestCommonFactor (comprimento da tabela, x) igual a 1, ou seja, tornando o comprimento da tabela coprime com x. E se x pode ser praticamente qualquer número, verifique se o comprimento da tabela é um número primo.

From - http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Explicação bastante clara, com fotos também.

Editar: Como um resumo, os números primos são usados ​​porque você tem a melhor chance de obter um valor único ao multiplicar valores pelo número primo escolhido e somar todos eles. Por exemplo, dada uma string, multiplicar cada valor de letra pelo número primo e, em seguida, somar todos, fornecerá seu valor de hash.

Uma pergunta melhor seria: por que exatamente o número 31?

tl; dr

index[hash(input)%2]resultaria em uma colisão para metade de todos os hashes possíveis e uma faixa de valores. index[hash(input)%prime]resulta em uma colisão de <2 de todos os hashes possíveis. A fixação do divisor ao tamanho da tabela também garante que o número não possa ser maior que a tabela.

Primes são usados ​​porque você tem boas chances de obter um valor exclusivo para uma função hash típica que usa o módulo P. de polinômios. Digamos que você use essa função hash para cadeias de comprimento <= N e tenha uma colisão. Isso significa que 2 polinômios diferentes produzem o mesmo valor de módulo P. A diferença desses polinômios é novamente um polinômio do mesmo grau N (ou menos). Ele não tem mais que N raízes (é aqui que a natureza da matemática se mostra, uma vez que essa afirmação é verdadeira apenas para um polinômio sobre um campo => número primo). Portanto, se N for muito menor que P, é provável que você não tenha uma colisão. Depois disso, o experimento provavelmente pode mostrar que 37 é grande o suficiente para evitar colisões para uma tabela de hash de seqüências de caracteres com comprimento de 5 a 10 e é pequeno o suficiente para ser usado nos cálculos.

Apenas para fornecer um ponto de vista alternativo, existe este site:

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

Que afirma que você deve usar o maior número possível de buckets, em vez de arredondar para um número principal de buckets. Parece uma possibilidade razoável. Intuitivamente, certamente posso ver como seria melhor um número maior de buckets, mas não consigo argumentar matemático sobre isso.

Primes são números únicos. Eles são únicos, pois o produto de um primo com qualquer outro número tem a melhor chance de ser único (não tão único quanto o próprio primo, é claro), devido ao fato de um primo ser usado para compô-lo. Esta propriedade é usada nas funções de hash.

Dada uma sequência "Samuel", você pode gerar um hash exclusivo, multiplicando cada um dos dígitos ou letras constituintes por um número primo e somando-os. É por isso que primos são usados.

No entanto, o uso de números primos é uma técnica antiga. A chave aqui para entender que, desde que você possa gerar uma chave suficientemente única, você também pode passar para outras técnicas de hash. Clique aqui para obter mais informações sobre este tópico sobre http://www.azillionmonkeys.com/qed/hash.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Depende da escolha da função hash.

Muitas funções de hash combinam os vários elementos nos dados, multiplicando-os com alguns fatores, modulando a potência de dois correspondentes ao tamanho da palavra da máquina (esse módulo é livre, apenas deixando o cálculo exceder).

Você não deseja nenhum fator comum entre um multiplicador para um elemento de dados e o tamanho da tabela de hash, porque pode acontecer que variar o elemento de dados não espalhe os dados por toda a tabela. Se você escolher um primo para o tamanho da tabela, esse fator comum é altamente improvável.

Por outro lado, esses fatores são geralmente compostos de números primos ímpares, portanto você também deve estar seguro usando potências de dois para sua tabela de hash (por exemplo, o Eclipse usa 31 quando gera o método Java hashCode ()).

Suponha que o tamanho da sua tabela (ou o número do módulo) seja T = (B * C). Agora, se o hash da sua entrada for como (N * A * B), em que N pode ser qualquer número inteiro, sua saída não será bem distribuída. Como toda vez que n se tornar C, 2C, 3C etc., sua saída começará a se repetir. ou seja, sua saída será distribuída apenas nas posições C. Observe que C aqui é (T / HCF (tamanho da tabela, hash)).

Esse problema pode ser eliminado com o HCF 1. Os números primos são muito bons para isso.

Outra coisa interessante é quando T é 2 ^ N. Isso fornecerá a saída exatamente igual a todos os N bits inferiores do hash de entrada. Como todo número pode ser representado potências de 2, quando tomarmos o módulo de qualquer número com T, subtraímos todas as potências do número 2 do formulário, que são> = N, portanto, sempre emitindo número de padrão específico, dependendo da entrada . Esta também é uma má escolha.

Da mesma forma, T como 10 ^ N também é ruim por razões semelhantes (padrão na notação decimal de números em vez de binário).

Portanto, os números primos tendem a fornecer melhores resultados distribuídos, portanto, são uma boa opção para o tamanho da tabela.

Copiando da minha outra resposta https://stackoverflow.com/a/43126969/917428 . Veja para mais detalhes e exemplos.

Acredito que isso tenha a ver com o fato de os computadores funcionarem na base 2. Pense em como a mesma coisa funciona na base 10:

• 8% 10 = 8
• 18% 10 = 8
• 87865378% 10 = 8

Não importa qual é o número: contanto que termine com 8, seu módulo 10 será 8.

Escolher um número grande o suficiente, sem potência de dois, garantirá que a função hash seja realmente uma função de todos os bits de entrada, em vez de um subconjunto deles.

Gostaria de acrescentar algo à resposta de Steve Jessop (não posso comentar, pois não tenho reputação suficiente). Mas encontrei algum material útil. Sua resposta é de grande ajuda, mas ele cometeu um erro: o tamanho do balde não deve ser uma potência de 2. Vou apenas citar o livro "Introdução ao algoritmo", de Thomas Cormen, Charles Leisersen, et al., Na página 263:

Ao usar o método de divisão, geralmente evitamos certos valores de m. Por exemplo, m não deve ser uma potência de 2, pois se m = 2 ^ p, então h (k) é apenas os bits de p de ordem mais baixa de k. A menos que saibamos que todos os padrões de bits p de ordem inferior são igualmente prováveis, é melhor projetar a função hash para depender de todos os bits da chave. Como o Exercício 11.3-3 pede para você mostrar, escolher m = 2 ^ p-1 quando k é uma sequência de caracteres interpretada na raiz 2 ^ p pode ser uma má escolha, porque permutar os caracteres de k não altera seu valor de hash.

Espero que ajude.

Para uma função de hash, não é apenas importante minimizar as colisões em geral, mas também tornar impossível permanecer com o mesmo hash enquanto persegue alguns bytes.

Digamos que você tenha uma equação: (x + y*z) % key = xcom 0<x<keye 0<z<key. Se a chave for um número principal, n * y = a chave será verdadeira para todos os n em N e falsa para todos os outros números.

Um exemplo em que chave não é um exemplo primordial: x = 1, z = 2 e chave = 8 Como a chave / z = 4 ainda é um número natural, 4 se torna uma solução para nossa equação e, neste caso (n / 2) * y = chave é verdadeira para cada n em N. A quantidade de soluções para a equação praticamente dobrou porque 8 não é primo.

Se nosso atacante já sabe que 8 é a solução possível para a equação, ele pode alterar o arquivo de 8 para 4 e ainda obter o mesmo hash.

Eu li o popular site wordpress vinculado em algumas das respostas populares acima na parte superior. Pelo que entendi, gostaria de compartilhar uma observação simples que fiz.

Você pode encontrar todos os detalhes no artigo aqui , mas suponha que o seguinte seja verdadeiro:

• Usar um número primo nos dá a "melhor chance" de um valor único

Uma implementação geral de hashmap deseja que duas coisas sejam únicas.

• Código hash exclusivo para a chave
• Índice exclusivo para armazenar o valor real

Como obtemos o índice exclusivo? Tornando o tamanho inicial do contêiner interno também excelente. Então, basicamente, o prime está envolvido porque possui essa característica única de produzir números únicos que acabamos usando para identificar objetos e encontrar índices dentro do contêiner interno.

Exemplo:

key = "chave"

valor = "valor" uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

mapeia para o ID exclusivo

Agora queremos um local único para o nosso valor - para que

uniqueId % internalContainerSize == uniqueLocationForValue, assumindo internalContainerSizetambém é um primo.

Sei que isso é simplificado, mas espero ter uma ideia geral.

"A natureza da matemática" em relação aos módulos de potência principal é que eles são um componente de um campo finito . Os outros dois blocos de construção são uma operação de adição e multiplicação. A propriedade especial dos módulos primos é que eles formam um campo finito com as operações "regulares" de adição e multiplicação, apenas levadas ao módulo. Isso significa que toda multiplicação mapeia para um módulo inteiro diferente do primo, assim como todas as adições.

Os módulos principais são vantajosos porque:

• Eles oferecem mais liberdade ao escolher o multiplicador secundário no hash secundário, todos os multiplicadores, exceto 0, acabam visitando todos os elementos exatamente uma vez
• Se todos os hashes forem menores que o módulo, não haverá colisões.
• Os números primos aleatórios se misturam melhor que a potência de dois módulos e compactam as informações de todos os bits, não apenas de um subconjunto

No entanto, eles têm uma grande desvantagem, exigem uma divisão de números inteiros, que leva muitos (~ 15-40) ciclos, mesmo em uma CPU moderna. Com cerca de metade do cálculo, pode-se garantir que o hash esteja muito bem misturado. Duas operações de multiplicação e xorshift se misturam melhor que um moudulus principal. Em seguida, podemos usar qualquer tamanho de tabela de hash e a redução de hash mais rápida, fornecendo 7 operações no total para potência de 2 tamanhos de mesa e cerca de 9 operações para tamanhos arbitrários.

Recentemente, observei muitas das implementações mais rápidas da tabela de hash e a maioria delas não usa módulos principais.

Esta questão foi mesclada à pergunta mais apropriada: por que as tabelas de hash devem usar matrizes de tamanho primordial e não a potência de 2. Para as funções de hash, há muitas boas respostas aqui, mas, para a pergunta relacionada, por que algumas tabelas de hash críticas à segurança , como a glibc, use matrizes de tamanho primário, ainda não há nenhuma.

Geralmente o poder de 2 mesas é muito mais rápido. Lá o caro h % n => h & bitmask, onde a máscara de bits pode ser calculada via clz("contar zeros à esquerda") do tamanho n. Uma função de módulo precisa fazer a divisão inteira que é cerca de 50x mais lenta que a lógica and. Existem alguns truques para evitar um módulo, como usar o https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ , mas geralmente as tabelas de hash rápidas usam o poder de 2, e as tabelas de hash seguras usam números primos.

Por quê então?

A segurança nesse caso é definida por ataques à estratégia de resolução de colisões, que na maioria das tabelas de hash são apenas pesquisas lineares em uma lista vinculada de colisões. Ou com as tabelas lineares de endereçamento mais rápido, pesquisa linear diretamente na tabela. Portanto, com o poder de 2 tabelas e algum conhecimento interno da tabela, por exemplo, o tamanho ou a ordem da lista de chaves fornecida por alguma interface JSON, você obtém o número de bits corretos usados. O número de unidades na máscara de bits. Isso geralmente é menor que 10 bits. E por 5 a 10 bits, é trivial colisões de força bruta, mesmo com as funções de hash mais fortes e lentas. Você não tem mais a segurança total de suas funções de hash de 32 bits ou 64 bits. E o objetivo é usar funções de hash pequenas e rápidas, não monstros como murmúrios ou até sifás.

Portanto, se você fornecer uma interface externa à sua tabela de hash, como um resolvedor de DNS, uma linguagem de programação, ... você quer se preocupar com as pessoas que gostam de abusar desses serviços. Normalmente, é mais fácil para essas pessoas encerrar seu serviço público com métodos muito mais fáceis, mas aconteceu. Então as pessoas se importavam.

Portanto, as melhores opções para evitar ataques de colisão são:

1) usar tabelas primárias, porque então

• todos os 32 ou 64 bits são relevantes para encontrar o bucket, não apenas alguns.
• a função de redimensionamento da tabela de hash é mais natural do que apenas o dobro. A melhor função de crescimento é a sequência de fibonacci e os primos aproximam-se mais do que dobrar.

2) use medidas melhores contra o ataque real, juntamente com potência rápida de 2 tamanhos.

• conte as colisões e aborte ou durma nos ataques detectados, que são números de colisões com uma probabilidade <1%. Como 100 com tabelas de hash de 32 bits. Isto é o que, por exemplo, o dns resolvedor de djb faz.
• converta a lista vinculada de colisões em árvore com pesquisa O (log n) e não O (n) quando um ataque de colisão é detectado. Isto é o que, por exemplo, o java faz.

Existe um mito generalizado de que funções hash mais seguras ajudam a impedir esses ataques, o que está errado, como expliquei. Não há segurança apenas com bits baixos. Isso funcionaria apenas com tabelas de tamanho primo, mas usaria uma combinação dos dois métodos mais lentos, hash lento e módulo primário lento.

As funções de hash para tabelas de hash precisam principalmente ser pequenas (para serem inlináveis) e rápidas. A segurança pode vir apenas da prevenção da pesquisa linear nas colisões. E não usar funções hash trivialmente ruins, como aquelas insensíveis a alguns valores (como \ 0 ao usar multiplicação).

O uso de sementes aleatórias também é uma boa opção, as pessoas começaram com isso primeiro, mas com informações suficientes da tabela, mesmo uma semente aleatória não ajuda muito, e linguagens dinâmicas geralmente tornam trivial obter a semente por outros métodos, como ela é armazenada em locais de memória conhecidos.

function eratosthenes(n) {

    function getPrime(x) {
        var middle = (x-(x%2))/2;
        var arr_rest = [];
        for(var j=2 ; j<=middle;j++){
            arr_rest.push(x%j);
        }

        if(arr_rest.indexOf(0) == -1) {
            return true
        }else {
            return false
        }

    }
    if(n<2)  {
        return []
    }else if(n==2){
        return [2]
    }else {
        var arr = [2]
        for(var i=3;i<n;i++) {
            if(getPrime(i)){
                arr.push(i)
            }
        }
    }

    return arr;
}