A função hash é utilizada para inserir ou buscar um elemento, mas podem ocorrer colisões quando a função hash produz o mesmo endereço para chaves diferentes.
-
p=MM − 1xMM−2x ... xMM−N+1=
-
∏i=1NMM−i+1=(M−N)!MNM!
-
Assinalar a alternativa que explica corretamente o que a imagem acima representa:
A
A probabilidade p de se inserir N itens consecutivos sem colisão em uma tabela de tamanho M.
B
Resolve o uso ineficiente do espaço de armazenamento.
C
A probabilidade de ocorrer colisão ao se inserir M itens aleatórios em uma tabela de tamanho N.
D
Uma estratégia eficiente para tratamento de colisões.
E
Uma função de transformação que mapeia chaves em inteiros dentro do intervalo [0..M − 1], onde N é o tamanho da tabela.