Eu acredito que será mais útil se eu explicar HashMaps em inglês.

O que é um HashMap?

Um HashMap é uma estrutura de dados que é capaz de mapear certas chaves para certos valores. As chaves e valores podem ser qualquer coisa. Por exemplo, se eu estivesse fazendo um jogo, eu poderia vincular cada nome de usuário a uma lista de amigos, representada por uma Lista de Strings.

Por que usar um HashMap?

HashMaps são muito mais rápidos para recuperar dados do que arrays e listas vinculadas. Um array ordenado poderia encontrar um valor particular em O(log n) com pesquisa binária. Entretanto, um HashMap pode verificar se ele contém uma chave em particular no O(1). Todas as chaves devem ser únicas.

Como os HashMaps funcionam?

HashMaps usam um array em segundo plano. Cada elemento no array é outra estrutura de dados (geralmente uma lista ligada ou uma árvore de busca binária). O HashMap usa uma função na chave para determinar onde colocar o valor da chave no array. Por exemplo, se o meu HashMap aceita Strings…possíveis funções de hash podem ser:

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

O valor retornado irá determinar o índice no qual o valor vai para o array.

Mas espere! Há um problema!

É possível que o valor retornado esteja fora dos limites do array. Portanto, devemos moderar o valor retornado pelo comprimento dos arrays.

return Math.abs(number%hashMapArray.length);

Collisions:

Não é possível que múltiplas chaves façam a função hash gerar o mesmo índice? Sim. Por exemplo, se usamos a primeira função hash mostrada acima em um mapa hash de strings…quaisquer duas Strings que comecem com a mesma letra terão o mesmo índice de array.

>

A isto se chama colisão.

>

Como lidamos com colisões?

Uma técnica de manipulação de colisões é chamada de encadeamento. Como cada elemento no array é uma lista ligada (ou estrutura de dados similar), múltiplas chaves que têm o mesmo valor de hash serão colocadas na mesma lista ligada ou “balde”. Depois disso, o mapa hash é capaz de recuperar valores calculando o código hash com a função hash, e pesquisando a lista ligada em particular para ver se ela contém um valor com a mesma chave.

Uma boa função hash deve ser escrita para evitar colisões.

Vantagens para Encadeamento:

-Array cannot overflow

-Dados podem ser facilmente removidos

Desvantagens para Encadeamento:

-Mai sofrer um golpe de performance se os baldes contiverem listas muito longas ligadas.

O número total de entradas para o número de baldes é chamado de fator de carga. Se o fator de carga for muito baixo, muito espaço é desperdiçado. Se o fator de carga for muito alto, a vantagem do hashing é perdida. Um bom compromisso no fator de carga é .75