Índice:

• A função de dispersão (hash)
• Inserção
• Lidando com colisões: Linear Probing
• Lidando com colisões: Hashing duplo

A hashtable é uma implementação do dicionário, que por meio de uma função de dispersão consegue dispôr os elementos na lista de forma "aleatória", mantendo a complexidade temporal da pesquisa em O(1).

A ideia é que, usando um array, a função de dispersão defina a posição do elemento sendo inserido. Como essa posição é calculada em (O(1)), a pesquisa usando a mesma chave vai chamar a função de dispersão e acessar direto o endereço do elemento no array, em tempo constante.

A função de dispersão precisa levar em conta o tamanho do array, caso contrário ela pode usar somente parte do array (o que levaria a mais colisões) ou fazer inserções em endereços que estão fora da área de memória.

Uma função de dispersão comum seria h(x) = x%tamanhoDoArray.

Considere um array de tamanho 12:

Vamos inserir alguns números. 23, 178, 38 e 56. Ficamos assim:

Como a posição do número no array vai depender do resto da divisão dele por 12, você pode esperar que haja uma distribuição uniforme ao longo do array.

Mas vez ou outra o resultado da função hash pra um elemento vai ser uma posição que já está ocupada, e temos que resolver isso de alguma forma.

Vamos pegar o exemplo do item 2 e adicionar o número 14.

Ooops, ocupado. Há duas formas mais comuns de lidar com colisões:

Uma forma simples de resolver o problema das colisões é armazenar os itens numa sequência (lista, array). Você pode desde o início usar um array de listas ligadas, por exemplo. No meu caso, eu criei um objeto "Elemento" que vai armazenar o valor do elemento e uma referência para o próximo elemento naquele endereço, caso haja um.

Vejamos:

Dessa forma, nosso algoritmo de pesquisa vai precisar iterar sobre todos os elementos ligados ao primeiro do índice, para conferir se o item buscado não está lá.

Endereçamento é um método onde arranjamos o elemento em outra posição no array, e pode ser feito tradicionalmente de duas formas:

Linear probing consiste em deslocar o elemento para o índice seguinte. Retomando o exemplo da imagem do item 3:

E então nossa busca precisa passar por todos os espaços preenchidos até achar um elemento vazio.

Mas há um problema aí. Vamos considerar o seguinte: Inserimos o número 26 na tabela, que também depois da função de hashing acaba caindo no índice 2. Depois, por algum motivo, removemos o elemento 14.

Até aí tudo bem, NÉ?. Mas vamos fazer uma pesquisa pelo número 26:

O "buraco" que deixamos ao remover o número 14 faz com que não consigamos chegar no 26, que foi posto na "mesma posição" mas que agora não pode ser acessado. Você pode até dizer que é só procurarmos no resto do array, mas isso torna a complexidade temporal da busca O(N), fazendo com que nossa implementação vire basicamente uma lista ligada:

A solução pra o problema do buraco é, quando fizermos uma remoção, utilizarmos um símbolo, que indica que ali é um espaço vazio, mas que o próximo elemento deve ser conferido também. Coleguinha chama esse símbolo de "AVAILABLE".

Ufa! Temos uma tabela hash com linear probing funcional. O objeto AVAILABLE simboliza que aquele índice pode ser passado numa pesquisa, mas que também está disponível (no inglês, available) para inserção.

Porém, eu não gosto dessa abordagem. Pra usar ela, o tipo do atributo que usamos como chave para nossos valores na table precisa ser Object, e isso não é tão limpo: generalizar o tipo de todo um conjunto pra satisfazer uma condição excepcional.

........ COMO EU AINDA NÃO CITEI TAMANHO MÁXIMO DO ARRAY, É BOM DEIXAR ESSA PARTE PRA MAIS PRA FRENTE.

.....TAMBÉ LEMBRAR DE CITAR QUE É NECESSÁRIO CHECAR O ELEMENTO DO INDÍCE ATUAL CONTRA O SIMBOLO AVAILABLE.

Acho mais interesante usarmos a seguinte opção: O nosso "available" será um número que não poderemos usar. O ideal pra isso é o número máximo que o tipo do atributo da chave suportar. Como uso int, nosso símbolo de available será o número 2 147 483 647. Em java, podemos acessar esse valor por meio de

Integer.MAX_VALUE

Logo, nosso exemplo ficaria assim:

Vamos adicionar mais alguns elementos:

Note que a tabela é circular.

Talvez você tenha sacado que há um problema: Com o tempo, a busca degenera. Imagine que, se você sempre trata a colisão deslocando um elemento pra direita, a busca pode precisar checar todos os elementos seguintes até achar a chave pesquisada, ou mesmo simplesmente constatar que ela não está na tabela.

Pra evitar isso, precisamos garantir que o array não fique muito cheio, sempre mantendo o preenchimento abaixo de 50% aumentando o tamanho.

------ imagem

Uma segunda função hash, que encontra uma posição pra um elemento caso haja uma colisão. ...................

• Há alguma variedade nas funções de dispersão? Se sim, qual?
• Colocar a função de busca utilizando encadeamento