MAC0323 2017: EP10 - limites para o fator de carga

Salve,

No EPs relacionados a hashing temos um limite alfaInf inferior e um limite alfaSup superior para o fator de carga (alfa = n/m).
Em hashing com encadeamento (separatechaining) os limites indicam o comprimento médio mínimo e máximo das listas.
Em hashing com sondagem linear (linear probing) os limites indicam a ocupação mínima e máxima da tabela.

Bem, no EP10, o que acontece se para valores de k, alfaInf e alfaSup tivermos que PRIMES[k]*alfaInf < PRIMES[k-1]*alfaSup?
Para tornar a discussão mais concreta, o que pode ocorrer se k == 6, alfaInf == 5, alfaSup = 10?

Re: EP10 - limites para o fator de carga

por João Pedro Miguel de Moura - terça-feira, 30 mai. 2017, 19:10

Se nestes valores de k, alfaInf e alfaSup o valor de n/m for menor que alfaInf, a função delete() chamará resize() para diminuir o número de listas.

Mas ao terminar o resize() o fator de carregamento já terá superado o alfaSup, então o resize() teria que ser chamado novamente. vice e versa.

exemplo:

PRIMES[6] = 509, PRIMES[5] = 251

para n = 2544, com k = 6, n/m = 4,99 que é menor que alfaInf. Então devo chamar resize().

O novo fator de carregamento n/m = 2544/251 = 10,13 que é maior que alfaSup, então eu deveria chamar resize() novamente.

Seria isso?

Re: EP10 - limites para o fator de carga

por José Coelho de Pina - segunda-feira, 5 jun. 2017, 17:23

Oi João,

Desculpe pela demora.

É isso mesmo. A chamada de resize() só trará trabalho de copiar coisas de um lado para o outro, mas não terá efeito algum.

Quando no início do semestre fizemos o resize() de uma pilha, dobramos o tamanho da pilha quando ela estava cheia e dividimos o tamanho pela metade quando ficava com ocupação de menos de 25%.
Isso garantia que o consumo de tempo (amortizado) de pop() e push() fosse constante.

Precisamos ser cuidadosos ao escolher os valores para redimensionamento.