Questão 2287099

• Banca: FGV
• Órgão: AL-MT
• Ano: 2013
• Provas: FGV - 2013 - AL-MT - Analista de Sistemas - Banco de Dados
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Estrutura de Dados; Hashing

No Hash extensível, considerando d como sendo a profundidade global do diretório, o tamanho do bucket será:

• A. 2^d endereços.
• B. 2^{d – 1} endereços.
• C. d² endereços.
• D. (d + 1)² endereços.
• E. (d² – 1)/2 endereços.

Gabarito: A

Comentários

• Hash Extensível

   

  O hash extensível usa um diretório dinâmico de registros que armazena uma tabela, onde cada registro contém um ponteiro para balde (tabela que armazena os registros) e cada balde tem um número fixo de itens. Aplicando-se a função nas chaves obteremos um número binário. Desse número devemos escolher uma quantidade de bits que fará a diferenciação entre os índices a serem armazenados no diretório. A esse número de bits escolhidos damos o nome de profundidade global (d) que especificará o número de linhas da tabela (diretório), que será 2d.

   

  http://www.ecnsoft.net/wp-content/plugins/downloads-manager/upload/UFSC%20-%20Hash%20Extensivel.pdf

• Hashing extensível: neste tipo de hashing é mantido um vetor de 2d endereços de buckets, onde d é chamado de profundidade global, que funciona como um tipo de diretório. O valor inteiro correspondente aos primeiros d bits de um valor hash é utilizado como índice de um vetor para determinar uma entrada no diretório e o endereço naquela entrada determina o bucket no qual os registros correspondentes serão armazenados. Uma profundidade local d', armazenada em cada bucket, especifica o número de bits no qual os conteúdos dos buckets são baseados.

   

  http://www.inf.unioeste.br/~olguin/4458-semin/G2-monografia.pdf