3

Tenho de implementar uma tabela hash, também conhecida como tabela de espalhamento, no entanto minha inexperiência com essa estrutura de dados pode fazer com que ocorra muitas colisões na minha implementação. Gostaria de saber quais praticas devo abordar e como saber se minha tabela está bem espalhada.

1

1 Resposta 1

3

Uma tabela de espelhamento usa alguns slots para armazenar objetos de acordo com o hash, não o hash em si.

Colisões são esperadas, já que vários hashes podem ser armazenados no mesmo slot.

Uma das implementações internas do Java cria um array de slots baseado no número de elementos na tabela (mapa, no caso).

Como hashes não são nada mais que números, basicamente se faz uma conta e se determina que se o número do hash está num determinado intervalo ele vai parar numa posição do vetor.

Por exemplo, imagine que no seu sistema hashes podem assumir valores de 1..100. Você pode criar uma tabela com 10 posições de forma que se o hash de um elemento pertence ao conjunto [1..10], ele será colocado na primeira posição da tabela. E assim por diante.

Cada posição da tabela é na verdade uma lista de elementos. Quando há colisão na hora de incluir, você simplesmente adiciona o novo elemento na lista.

O problema é que na hora de recuperar, além de encontrar a posição na tabela, você tem que percorrer essa lista verificando se o elemento a ser retirado da tabela está naquela lista.

A implicação disso é que os algoritmos mais eficientes de hashing são aqueles que geram valores mais uniformemente distribuídos.

Além disso, uma implementação mais avançada pode verificar se existem muitos conflitos e aumentar dinamicamente a quantidade de posições na tabela de espelhamento, de forma a diminuir o número de colisões.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .