Faz sentido redimensionar uma tabela de hash? E quando?

Question

Minha implementação da tabela de hash tem uma função para redimensionar a tabela quando a carga atingir cerca de 70%. Minha tabela de hash é implementada com encadeamento separado para colisões.

Faz sentido redimensionar a tabela de hash em qualquer momento ou devo deixá -lo como é? Caso contrário, se eu aumentar o tamanho (quase o dobro, na verdade eu sigo isto: http://planetmath.org/encyclopedia/goodhashtableprimes.html) Quando a carga é de 70%, devo redimensioná -la quando a carga fica 30% ou menos?

Answer 1

Você está escrevendo a tabela de hash para uso de uso geral ou existe um objetivo específico para isso? Sugiro não redimensionar menor para uma implementação geral. Isso manterá sua mesa simples e impedirá que a memória se debate em condições em que a tabela é preenchida e esvaziada com frequência. Se você acabar correndo para uma condição em que a tabela de hash precisará ser reduzida em tamanho, estenda -a naquele momento.

Answer 2

As tabelas de hash não precisam ter comprimentos de número principal se você tiver uma função de hash de boa qualidade (ver aqui). Você pode torná -los poderes de dois, o que acelera substancialmente os cálculos de índice.

Por que isso é relevante para a pergunta? Porque quando você encolher um poder de dois hashtable, você pode deixar todas as entradas na metade inferior onde estão e simplesmente anexar a lista vinculada no slot i (da metade superior) para a lista vinculada no slot i - n/2.

Answer 3

Se a memória for barata, deixe -a em paz. Se a memória for cara, redimensione com a histerise, como você sugeriu. Quando terminar, perfil o resultado para garantir que ele tenha um bom desempenho e não tenha feito algo bobo.

Answer 4

Primeira idéia: a única razão para o crescimento de uma hashtable é porque o desempenho de hashtable diminui se houver muitas colisões. Crescer a tabela quando sua carga excede 70% é uma boa regra para impedir que isso aconteça, mas é apenas uma regra do polegar. Muito melhor é acompanhar o número de colisões e aumentar apenas a hashtable se eles excederem um determinado limite ou uma vez que uma determinada taxa de colisão for atingida. Afinal, por que você deseja cultivar uma hashtable carregada em 90%, mas ainda não tem uma única colisão? Não teria vantagem.

Segunda idéia: a única razão para diminuir uma hashtable é salvar a memória, mas a diminuição pode aumentar o número de colisões e, assim, diminuir o desempenho da pesquisa. Esta é uma velocidade clássica versus comércio de memória e por que você deve resolvê -lo? Deixe para quem estiver usando seu código. Apenas nunca encolhem por conta própria, mas oferecem um método de encolhimento. Se o baixo uso da memória for um requisito, quem estiver usando seu código pode chamar o encolher regularmente. Se o desempenho máximo, se for um requisito, quem estiver usando seu código nunca deve ligar para o Shrink. Todo mundo pode usar algum tipo de heurística para decidir se e quando ligar para o encolhimento.

Terceira idéia: Ao crescer ou diminuir, sempre cresça/encolhem de tal maneira que, após a operação, um determinado fator de carga é garantido. Por exemplo, quando cresce, sempre cresça para que depois o fator de carga seja de 50% e, ao diminuir, sempre encolher de tal maneira que depois o fator de carga seja de 70%. Obviamente, isso não diz nada sobre o número de colisões; portanto, adicionar um elemento imediatamente após o crescimento/encolhimento pode fazer com que a hashtable cresça novamente, mas isso é inevitável, pois simular o efeito de um crescimento/encolhimento geralmente é muito caro. O encolhimento também será chamado de uma vez que nenhuma modificação adicional for planejada, portanto, deve salvar a memória do que evitar ter que crescer novamente no futuro.

Última ideia: para todas as decisões que você tomar, você tornará a hashtable melhor para alguns casos de uso e pior para outros. Se você souber como sua hashtable será usada, isso não será um problema. No entanto, se você não, e geralmente não, por que tomar essas decisões? Apenas delegue -os. Permita que o usuário do seu código personalize todos os pequenos detalhes, por exemplo, quanto crescer ou encolher, permitindo que todos esses fatores sejam definidos quando sua hashtable estiver sendo criada ou permitindo que sua hashtable tenha funções de delegado (funções de retorno de chamada que você sempre pode perguntar quando não tem certeza do que fazer). Dessa forma, todos os usuários do seu código podem personalizar seu código, mesmo em tempo de execução, para qualquer cenário de uso necessário.