Tabela de hash: devo aumentar a contagem de elementos em colisões?

Question

No momento, minhas tabelas de hash contam o número de cada elemento inserido na tabela de hash. Eu uso essa contagem, com o tamanho total da tabela de hash, para calcular o fator de carga e, quando atingir 70%, refazia -o.

Eu estava pensando que talvez eu deva contar apenas os elementos inseridos com preenchimento um slot vazio em vez de todos eles. Porque o método de colisão que estou usando é um encadeamento separado. A carga fatorial continua aumentando, mas se houver algumas colisões deixando muitos slots vazios na tabela de hash.

Você provavelmente está pensando que, se eu tiver tantas colisões, talvez não esteja usando o melhor método de hash. Mas esse não é o ponto, estou usando um dos algoritmos Know Hashing por aí, testei três deles nos meus dados de amostra e selecionei quem produziu menos colisões.

Minha pergunta ainda permanece. Devo continuar contando todos os elementos inseridos, ou apenas os que preenchem um slot vazio na tabela de hash?

Answer 1

A reformulação tem como objetivo reduzir a probabilidade de colisões, ignorando sistematicamente as colisões para decidir quando rehash parecem derrotamento.

O melhor pode ser se você mantivesse a cada entrada o valor original do hash completo (uma colisão, é claro, é determinada pelo módulo de hash do seu tamanho atual) e contou apenas as colisões que se devem à operação do módulo - reconhecendo implicitamente que, se uma colisão deve-se a valores de hash completos idênticos para itens diferentes, não há nada que a rehinging possa fazer para ajudar (a menos que "reformular" você também implica mudar para uma função de hash diferente, mas não se parece que é isso que você quer dizer aqui ;-).

Manter os valores completos de hash também significa refazer mais barato, pois você não precisa executar a função de hash novamente (quão relevante é isso depende de quão caro sua função de hash é calcular, é claro).