Considere uma tabela de hash de tamanho m=1000 e a função de hash usando o método da multiplicação com A=(raiz5-1) / 2. Calcule os valores de hash das chaves 61, 62, 63, 64 e 65.

Passo 1

A questão quer que a gente use o método da multiplicação para hash numa tabela de tamanho m=1000, com A=(raiz5-1)/2, e calcule h(k) para k=61,62,63,64,65. Vamos precisar aplicar a fórmula do método da multiplicação: extrair a parte fracionária de kA, multiplicar por m e então tomar o piso.

Passo 2

Primeiro, determinamos o valor de A:
A = raiz5 - 12 approx 0,6180339885

Passo 3

A fórmula geral do método da multiplicação é:
h(k) = llfloor m times kArrfloor
onde kA é a parte fracionária de kA.

Passo 4

Agora aplicamos para cada chave:
Para k=61:
61times A approx 37,7000733 implies 61A=0,7000733 implies h(61)=lfloor1000times0,7000733rfloor=700
Para k=62:
62times A approx 38,3181073 implies 62A=0,3181073 implies h(62)=lfloor1000times0,3181073rfloor=318
Para k=63:
63times A approx 38,9361413 implies 63A=0,9361413 implies h(63)=lfloor1000times0,9361413rfloor=936
Para k=64:
64times A approx 39,5541753 implies 64A=0,5541753 implies h(64)=lfloor1000times0,5541753rfloor=554
Para k=65:
65times A approx 40,1722093 implies 65A=0,1722093 implies h(65)=lfloor1000times0,1722093rfloor=172

Resposta

h(61)=700, h(62)=318, h(63)=936, h(64)=554, h(65)=172

Exercícios relacionados