Questão FC483471
Acerca de hashing, julgue o item subsecutivo. Conforme a premissa do hashing uniforme simples, cada chave tem igual probabilidade de passar para qualquer das m posições por uma ope
Criptografia (TI - Segurança da Informação)
CEBRASPE (CESPE) · 2023
Acerca de hashing, julgue o item subsecutivo.
Conforme a premissa do hashing uniforme simples, cada chave tem igual probabilidade de passar para qualquer das m posições por uma operação de hash, independentemente da posição que qualquer outra chave tenha ocupado após o hash. No método de divisão para criar funções hash, é mapeada uma chave k para uma de m posições, tomando-se o resto da divisão de k por m, de modo que a função hash é h(k) = k mod m.
Mostrar resposta e comentário
Gabarito
Certo
Comentário do professor
A afirmação é correta porque resume duas ideias fundamentais do hashing. Primeiro, a hipótese de hashing uniforme simples assume que, para análise probabilística, cada chave tem a mesma probabilidade \(1/m\) de ser colocada em qualquer uma das \(m\) posições e essa alocação é independente da posição ocupada por outras chaves.
Segundo, o método da divisão é uma forma prática de construir uma função hash que mapeia uma chave \(k\) em um índice entre 0 e \(m-1\) tomando o resto da divisão: \(h(k)=k \bmod m\). Assim, cada chave produz um valor na faixa de \(m\) posições, atendendo ao enunciado.
Em análise teórica admite-se independência e uniformidade; na prática, a escolha de \(m\) influencia a qualidade da distribuição e a ocorrência de colisões.
Conteúdo do catálogo FC Concursos · Atualizado em