Aceitável confiar em ints aleatórios sendo únicos?

Cuidado com o paradoxo de aniversário .

Suponha que você esteja gerando uma sequência de valores aleatórios (uniformemente, independentemente) de um conjunto de tamanho N (N = 2 ^ 32 no seu caso).

Em seguida, a regra geral do paradoxo de aniversário indica que, depois de ter gerado sobre sqrt (N) valores, há pelo menos 50% de chance de que uma colisão tenha ocorrido, ou seja, que haja pelo menos dois valores idênticos na sequência gerada.

Para N = 2 ^ 32, sqrt (N) = 2 ^ 16 = 65536. Então, depois de gerar cerca de 65k identificadores, é mais provável que dois deles colidam do que não! Se você gerar um identificador por segundo, isso aconteceria em menos de um dia; Escusado será dizer que muitos protocolos de rede operam muito mais rápido do que isso.

É amplamente aceito que os números aleatórios sejam únicos se esses números tiverem bits suficientes. Existem protocolos criptográficos em que a repetição de um número aleatório interrompe toda a segurança. E enquanto não houver vulnerabilidades sérias no gerador de números aleatórios sendo usado, isso não foi um problema.

Um dos algoritmos para gerar UUIDs gerará efetivamente um ID com 122 bits aleatórios e assumirá que será único. E dois dos outros algoritmos contam com um valor de hash truncado para 122 bits sendo único, que tem aproximadamente o mesmo risco de colisões.

Portanto, existem padrões que dependem de 122 bits para tornar um ID aleatório único, mas 32 bits definitivamente não são suficientes. Com IDs de 32 bits, leva apenas cerca de 2¹⁶ IDs antes que o risco de uma colisão atinja 50%, pois com 2¹⁶ IDs haverá cerca de 2³¹ pares, cada um dos quais poderia ser uma colisão.

Até 122 bits são menos do que eu recomendaria em qualquer novo design. Se seguir alguma padronização for importante para você, use os UUIDs. Caso contrário, use algo maior que 122 bits.

A função hash SHA1 com uma saída de 160 bits não é mais considerada segura, o que é em parte porque 160 bits não são suficientes para garantir a exclusividade das saídas. Funções hash modernas têm saídas de 224 a 512 bits. IDs gerados aleatoriamente devem ter como alvo os mesmos tamanhos para garantir exclusividade com uma boa margem de segurança.

Eu chamaria isso de má prática. Número aleatório gera simplesmente não cria números únicos, eles apenas criam números aleatórios. É provável que uma distribuição aleatória inclua alguns duplicados. Você pode tornar essa circunstância aceitavelmente improvável adicionando um elemento de tempo. Se você obtiver a hora atual do relógio do sistema em milissegundos. Algo parecido com isto:

parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))

Vai um longo caminho. Obviamente, para garantir verdadeiramente a exclusividade, você precisa usar o UUID / GUID. Mas eles podem ser caros para gerar, o acima é provavelmente suficiente, como a única possibilidade de sobreposição, é se a geração aleatória tivesse uma duplicata no mesmo milissegundo.

Depende tanto da probabilidade de falha quanto das conseqüências do fracasso.

Eu me lembro de um debate entre pessoas de software e hardware onde as pessoas de hardware consideravam que um algoritmo com uma pequena probabilidade de resultados errados (algo como 1 falha em 100 anos) era aceitável, e o pessoal do software achava isso anátema. Descobriu-se que o pessoal de hardware calculava rotineiramente as taxas de falha esperadas, e estava muito acostumado com a ideia de que tudo daria respostas erradas ocasionalmente, por exemplo. devido a perturbações causadas por raios cósmicos; Eles acharam estranho que o pessoal de software esperasse 100% de confiabilidade.

Claro, você tem probabilidades muito baixas de dois inteiros aleatórios de 32 bits sendo sequenciais, mas não é completamente impossível. A decisão de engenharia apropriada é baseada no que as consequências das colisões seriam, uma estimativa do volume de números que você está gerando, o tempo de vida sobre o qual a unicidade é necessária & o que acontece se um usuário mal-intencionado começar a tentar causar colisões.

Pode ser aceitável assumir que números aleatórios serão únicos, mas você precisa ter cuidado.

Supondo que seus números aleatórios são igualmente distribuídos, a probabilidade de uma colisão é aproximadamente (n ² / 2) / k onde n é o número de números aleatórios gerados e k é o número de possíveis valores que um número "aleatório" pode suportar.

Você não coloca um número em astronomicamente improvável, então vamos considerar 1 em 2 ³⁰ (aproximadamente em um bilhão). Vamos dizer ainda que você gera 2 ³⁰ pacotes (se cada pacote representa cerca de um kilobyte de dados, isso significa cerca de um terabyte de dados totais, grandes, mas não inimagináveis). Nós achamos que precisamos de um número aleatório com pelo menos 2 ⁸⁹ valores possíveis.

Primeiramente, seus números aleatórios precisam ser grandes o suficiente. Um número aleatório de 32 bits pode ter no máximo 2 ³² valores possíveis. Para um servidor ocupado que não está nem perto o suficiente.

Em segundo lugar, seu gerador de números aleatórios precisa ter um estado interno suficientemente grande. Se o seu gerador de números aleatórios tiver apenas um estado interno de 32 bits, não importa quão grande seja o valor gerado a partir dele, você só obterá no máximo 2 ³² valores possíveis.

Em terceiro lugar, se você precisar que os números aleatórios sejam únicos entre as conexões, e não apenas dentro de uma conexão, seu gerador de números aleatórios precisa ser bem propagado. Isto é especialmente verdadeiro se o seu programa for reiniciado com freqüência.

Em geral, os geradores de números aleatórios "regulares" nas linguagens de programação não são adequados para tal uso. Os geradores de números aleatórios fornecidos por bibliotecas de criptografia geralmente são.

embutido em algumas das respostas acima é a suposição de que o gerador de números aleatórios é de fato 'plano' - que a probabilidade de quaisquer dois números serem o próximo gerado é a mesma.

Isso provavelmente não é verdade para a maioria dos geradores de números aleatórios. A maioria usa algum polinômio de alta ordem aplicado repetidamente a uma semente.

Dito isto, existem muitos sistemas que dependem deste esquema, geralmente com o UUID. Por exemplo, cada objeto e ativo no Second Life tem um UUID de 128 bits, gerado aleatoriamente, e eles raramente colidem.

Muitas pessoas já deram respostas de alta qualidade, mas eu gostaria de acrescentar alguns pequenos pontos: primeiro, o ponto do @nomadictype sobre o paradoxo do aniversário é excelente . p>

Outro ponto: a aleatoriedade não é tão simples de gerar e definir quanto as pessoas podem imaginar. (Na verdade, existem testes estatísticos de aleatoriedade disponíveis).

Com isso dito, é importante estar ciente da Falácia do Jogador , que é uma falácia estatística em que as pessoas assuma que eventos independentes de alguma forma influenciam uns aos outros. Os eventos aleatórios são geralmente estatisticamente independentes um do outro - ou seja, se você gerar aleatoriamente um "10", isso não mudará sua probabilidade futura de gerar mais "10" s no mínimo. (Talvez alguém possa criar uma exceção a essa regra, mas eu esperaria que esse seria o caso de praticamente todos os geradores de números aleatórios).

Então, minha resposta é que, se você puder assumir que uma sequência suficientemente longa de números aleatórios era única, eles não seriam números aleatórios, porque isso seria um padrão estatístico claro. Além disso, isso implicaria que cada novo número não é um evento independente porque se você gerar, por exemplo, um 10, isso significaria que a probabilidade de gerar 10s futuros seria 0% (não poderia acontecer), mais isso significaria que você aumentaria as chances de obter um número diferente de 10 (ou seja, quanto mais números você gerasse, maior a probabilidade de cada um dos números restantes se tornarem).

Mais uma coisa a considerar: a chance de ganhar a Powerball de jogar um único jogo é, no meu entender, aproximadamente 1 em 175 milhões. No entanto, as chances de ganhar alguém são consideravelmente maiores do que isso. Você está mais interessado nas chances de alguém "ganhar" (ou seja, ser uma duplicata) do que na probabilidade de qualquer número em particular "vencer" / ser uma duplicata.

Não importa quantos bits você usa - você NÃO PODE garantir que dois números "aleatórios" serão diferentes. Em vez disso, eu sugiro que você use algo como o endereço IP ou outro endereço de rede do computador e um número seqüencial, de preferência um número seqüencial HONKIN 'BIG - 128 bits (obviamente não assinados) soa como um bom começo, mas 256 seria melhor.

Não, claro que não. A menos que o usuário esteja usando amostras sem substituição, existe uma chance - embora pequena - de duplicação.