Tabelas de dispersão (tabelas hash) armazenam elementos com base no valor absoluto de suaschaves e em técnicas
Tabelas de dispersão (tabelas hash) armazenam elementos com base no valor absoluto de suaschaves e em técnicas de tratamento de colisões. As funções de dispersão transformam chaves em endereçosbase da tabela, ao passo que otratamento de colisões resolve conflitos em casos em que mais de uma chave é mapeada para ummesmo endereço-base da tabela. Suponha que uma aplicação utilize uma tabela de dispersão com23 endereços-base (índices de 0 a 22) e empregue h(x) = x mod 23 como função de dispersão, em que xrepresenta a chave do elemento cujo endereço-base deseja-se computar. Inicialmente, essa tabela de dispersãoencontra-se vazia. Em seguida, a aplicação solicita uma seqüência de inserções de elementos cujas chavesaparecem na seguinte ordem: 44, 46, 49, 70, 27, 71, 90, 97, 95.Com relação à aplicação descrita, faça o que se pede a seguir. A Escreva, no espaço reservado, o conjunto das chaves envolvidas emcolisões. B Assuma que a tabela de dispersão trate colisões por meio deencadeamento exterior. Esboce a tabela de dispersão para mostrarseu conteúdo após a seqüência de inserções referida.
#ENADE
1 Resposta
Os conjuntos das chaves que podem ser envolvidas em colisões são:
45 e 95. 44 e 90.As chaves 45 e 95, e as chaves 44 e 90, apresentam a colisão direta já que caem na posição identificada como 3. A colisão direta acontece quando mesmo após a colisão os objetvos se movem na mesma reta.
A tabela de dispersão trata as colisões sobre aspectos especificos como a consideração de que quando uma nova chave entra na tabela e ela já foi ocupada os novos itens são considerados por uma lista de associação da posição.
Espero ter ajudado.
