A escolha de um tamanho adequado para uma tabela de Hash

Question

Se eu tiver um conjunto de chaves de 1000, o que é um tamanho adequado para a minha mesa Hash, e como é que determinado?

Answer 1

Depende do fator de carga (o ponto "por cento cheio" onde a tabela vai aumentar seu tamanho e re-distribuir seus elementos). Se você sabe que tem exatamente 1.000 entradas, e esse número nunca vai mudar, você pode apenas definir o fator de carga para 1,0 e o tamanho inicial para 1000 para a máxima eficiência. Se você não tinham certeza do tamanho exato, você pode deixar o fator de carga em seu padrão de 0,75 e definir o seu tamanho inicial para 1334 (tamanho esperado / LF) para realmente bom desempenho, a um custo de memória extra.

Você pode usar o seguinte construtor para definir o fator de carga:

Hashtable(int initialCapacity, float loadFactor) 

Answer 2

Você precisa levar em consideração a função hash também.

Uma regra sugere fazer o tamanho da tabela de cerca do dobro, para que haja espaço para se expandir, e esperamos manter o número de colisões de pequeno porte.

Outra regra de ouro é assumir que você está fazendo algum tipo de hashing módulo relacionado, em seguida, volta o seu tamanho de mesa para o próximo maior número primo, e o uso que número primo como o valor do módulo.

Que tipo de coisas você está hash? Mais detalhes devem gerar um melhor aconselhamento.

Answer 3

Há alguma discussão desses fatores na documentação para Hashtable

Answer 4

Deixe-o crescer. Com este tamanho, o tratamento automático é bom. Para além de que, o tamanho de 2 x + 1 é uma fórmula simples. Os números primos são também uma espécie de bom, mas assim que o conjunto de dados atinge um determinado tamanho, a implementação de hash pode decidir refazer e crescer na tabela.

Suas chaves estão impulsionando a eficácia e são espero que o suficiente distinta.

A linha inferior: Faça a pergunta tamanho quando você tem problemas, tais como tamanho ou desempenho lento, além de que: não se preocupe

Answer 5

Duas vezes é bom.

Você não tem um grande conjunto de chaves. Não se preocupe com as discussões difíceis sobre sua implementação HashTable, e ir para 2000.

Answer 6

Eu gostaria de reiterar o que https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany dito acima. 1000 não parece ser um grande hash para mim. Eu tenho usado um monte de hashtables sobre que tamanho em java sem ver muito em termos de problemas de desempenho. E eu quase nunca muck com o fator tamanho ou carga.

Se você executar um profiler em seu código e determinou que o hashtable é o seu problema, então por todos os meios começar ajustes. Caso contrário, eu não diria que você tem um problema até que você esteja certo.

Depois de tudo, na maior parte do código, o problema de desempenho não é onde você pensa que é. Eu tento não antecipar.