Quantos baldes de hash

Question

Se eu perceber que uma tabela hash (ou qualquer outra estrutura de dados construída sobre uma tabela hash) está enchendo, em que ponto você deve construir uma nova tabela com mais baldes. E dado n itens na tabela até agora, como você descobrir quantos baldes para usar no novo?

Então, digamos que eu tenho 100 baldes. Devo reorganizá-lo quando há 50 itens nele? 500? 5000? Ou eu deveria procurar o balde mais cheio ea chave sobre isso? Então, quando eu bater esse ponto de quão grande eu faço a nova tabela de hash?

Relacionado a isso, se você sabe de antemão aproximadamente quantos itens vai entrar, há uma maneira para calcular o número de baldes para obter um bom desempenho médio?

Eu sei que a verdadeira resposta depende de uma série de outras considerações como o quão importante é o tamanho vs. velocidade em um exemplo específico, mas eu estou procurando guildlines gerais.

Eu também sei que eu não deveria estar otimizar esse tipo de coisa, a menos boa profiling indicou que este é um gargalo. Eu só estou pensando em um projeto que usar um monte de tabelas de hash e se perguntou como abordar isso.

Answer 1

Uma boa regra do polegar (nem sempre ideal, assim, apenas uma regra do polegar) é re-hash de se o hashtable é preenchido até 80%. Isso significa que se você tem 100 baldes e 80 itens dentro, independentemente quantas colisão que você tinha antes, está ficando tempo para aumentar a capacidade.

Quanto você deve aumentá-la? Bem, também não há valor perfeito. solução mais simples é dobrar a capacidade de cada aumento. Então ele vai para 200, 400, 800 e assim por diante. Se você acha que isso é demais (depois de tudo o que vai saltar de memória de 8 MB a 16 MB quando o hashtable fica muito grande e você nunca pode encher a 16 MB), escolha um fator crescer mais pequenos. Pelo menos 1/3 é recomendável (crescente lo 100-133) eu diria que, talvez deixá-lo crescer em 50% de cada vez como um compromisso.

Note que tudo isso também depende de como colisões são tratadas. Uma simples maneira de lidar com eles (o meu favorito) é para armazenar os itens em uma lista ligada quando há uma colisão. Se 3 itens são colocados na mesma chave, ainda existem apenas até 3 compara a encontrá-lo. Desde lista ligada são muito ineficaz para pesquisa, você pode querer aumentar a capacidade anteriormente, por exemplo, se a capacidade de 60% é usado para manter o rápido hashtable. OTOH, você pode fazer algo mais sofisticado e manter estatísticas sobre o número de colisões. Contanto que você quase não têm quaisquer colisões (se você tiver uma boa função hash), não há necessidade de re-hash de em tudo, mesmo se 99% de sua capacidade está em uso. Além disso, se você lidar com colisões de forma sofisticada (por exemplo, cada nó é novamente uma tabela ordenada e você pode executar a busca binária dentro destes) a sua pesquisa ainda pode ser rápido o suficiente se a tabela é carregada a 200% (para você ter o dobro de itens como de capacidade). Nesse caso, você poderia manter estatísticas de quão grande a maior tabela ordenada e quando ele se torna maior do que, digamos, 8 entradas, você acha que isso está ficando muito lento e, em seguida, você re-hash.

Re-hashing é muito lento, por isso deve ser evitado sempre que possível. Assim, se você precisa re-de hash, não basta aumentar a capacidade muito pouco, caso contrário, você tem que re-hash de novo muito em breve ao adicionar mais itens. Então, quando você precisa re-hash tornar a capacidade significativamente maior do que o número de itens atualmente na tabela, tudo o resto é muito pouca capacidade.

Answer 2

De um modo geral, é olhar para o factor de carga (informalmente, já dito que) o qual é definido formalmente como a = n / N , isto é, a razão entre usados para baldes totais. Para que uma tabela hash para funcionar correctamente (ou, pelo menos, a razão sobre o seu desempenho em termos matemáticos), ele deve ser a <1.

Tudo o resto é realmente até testes empíricos: Se você ver que sua tabela hash não realizar uma boa partida em a> 0,5, em seguida, certifique-se de estadia sob esse valor. Este valor também depende do seu techique resolução colisão. Hash com encadeamento pode exigir outros fatores de carga que hashing com endereçamento aberto. No entanto, outro fator é o cache localidade. Se a sua mesa fica muito grande, não vai caber na memória principal. Desde o seu acesso para a matriz é aleatória, o carregamento do cache pode se tornar um gargalo.

Answer 3

Há tipicamente dois tipos de hashtables: aberto e fechado

.

Em um hashtable aberta você encontra o balde direito baseado no hash e, em seguida, construir uma lista de itens pendurado aquele balde.

Em um hashtable fechado encontrar o balde inicial usando o valor de hash, e se ele está ocupado você sonda para o próximo valor. No caso simplista você pode fazer isso olhando para a próxima balde livre, ou você pode criar um segundo valor hash do seu item e passo a que (embora você deve garantir que este é primo modulo do tamanho tabelas hash assim que você vai visitar todos os baldes).

Um hashtable aberto normalmente não é redimensionada. Você define o tamanho inicial para ser o que você sente é razoável para o problema. Como outros apontaram que você poderia redimensionar em uma hashtable aberto, mas o raciocínio sobre o desempenho desta estrutura de dados torna-se agora muito difícil. Se você redimensionar quando o comprimento de um determinado balde é L, então você pode acabar redimensionar em apenas itens L em toda a hashtable, que é muito ineficiente.

A hashtable fechado é redimensionado quando o fator de carga (no. De itens na hashtable / no. De baldes) atinge algum valor pré-definido. I tendem a usar 80%, mas o valor exato é improvável que seja muito crítico.

O benefício de uma tabela hash fechada é que a amortizado custo de inserção de um item é sempre O (1) (assumindo uma boa função hash). Inserção de um determinado item pode ser O (N), devido ao custo de redimensionamento, mas isso é feito muito raramente.

Answer 4

Depende do tipo de tabela hash você está construindo. Se você estiver usando uma matriz fixa a tabela hash com base (ao contrário de listas ligadas para baldes), você deve redimensionar a matriz ou quando a mesa está cheia ou quando você ter atingido uma contagem sonda max (dependendo se você se preocupam mais com a velocidade ou memória). Se você estiver usando listas ligadas, a memória não é tanto de uma preocupação, uma vez e não têm a sonda para espaços vazios, de modo redimensionamento não é tão grande de um negócio.

A chave com tabelas hash é o algoritmo de hash, não o número de baldes. Idealmente, você quer sempre no máximo um item em cada balde, para que você deve idealmente ser redimensionamento quando o número de itens na tabela hash = o número de baldes. Se os dados não é distribuído uniformemente, você está melhor com um algoritmo de hash melhor do que a melhor estratégia de redimensionamento.

Answer 5

Se você usar Linear Hashing, a própria tabela automaticamente cuida de redimensionamento, mantendo uma taxa de ocupação constante.