Colisões de Hash
As funções de hash não são perfeitas; por vezes, dados completamente diferentes podem produzir o mesmo valor de hash. Isto quebra a relação de mapeamento um-para-um entre os valores de entrada e o resultado do hash. Como consequência, diferentes cadeias de caracteres podem gerar o mesmo valor de hash, ou um par de números pode partilhar o mesmo hash. As colisões de hash podem causar problemas de segurança, bem como afetar o desempenho, dependendo do contexto em que ocorrem. Por exemplo, uma função de hash simples que mapeia um par de inteiros para um valor de hash pode mapear muitos pares (a, b) para o mesmo resultado:
A seguir, encontram-se vários exemplos de pares
(a, b) que resultam no mesmo valor de hash:- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
- …
Portanto, se tivermos uma lista de pares criada especificamente para ter o mesmo hash, surgirão muitas colisões, tornando a pesquisa de um valor ou a verificação de se um par
(a, b) está presente na lista bastante ineficiente ou até errada (dependendo da implementação).As colisões de hash também podem ser uma fonte de vulnerabilidades de segurança. As passwords dos utilizadores costumam ser armazenadas como hashes por razões de segurança (para evitar que as passwords sejam expostas mesmo em caso de invasão à base de dados). Se a função de hash não for adequada e gerar muitas colisões, os invasores podem aceder a uma conta sem sequer descobrir a palavra-passe correta. Se o hash de uma password aleatória coincidir com o hash da password original, o sistema assume que é o mesmo utilizador.
Uma boa função de hash consegue minimizar ao máximo as colisões. As funções de hash pré-existentes costumam funcionar bem para entradas aleatórias. No entanto, se os dados de entrada tiverem um tipo muito específico, ou se o problema exigir algo em particular, poderá ser necessário implementar uma função de hash personalizada.
Desafio: Verificar Colisões
Dada uma função de hash
h que mapeia um par de inteiros (a, b) para um número inteiro, pretende-se avaliar se a função h é suficientemente boa. O programa deve verificar se há colisões e deve imprimir Yes caso não haja colisões, ou No caso contrário. A função de hash está definida como:Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 10 000), que representa o número de pares.Nas
n linhas seguintes, são fornecidos pares de inteiros separados por espaço: (0 ≤ ≤ ). É garantido que estes pares são exclusivos.Saída
O programa deve imprimir
Yes se a função h(a, b) for adequada para os dados fornecidos e não ocorrerem colisões, ou No caso contrário.Exemplos
Entrada | Saída |
3
0 4
1 5
2 9 | Yes |
2
0 0
0 1
542313474 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB