Hashmap

Hash Function

Uma hash function é uma função que pode converter um valor de tamanho arbitrário para um de tamanho fixo (geralmente um inteiro de 32 bits). O resultado dessa função é chamado de hash value.

Por exemplo, uma hash function pode ser somar os itens de um array de inteiros e pegar o resto da divisão por 100.

[10, 50, 100] -> (10 + 50 + 100) % 100 = 60

60 nesse cenário seria o hash value.

Nessa hash function, duas entradas diferentes podem ter o mesmo resultado. Exemplo:

[20, 40, 100] -> (20 + 40 + 100) % 100 = 60.

Mais de um input tendo o mesmo output em uma hash function é chamado de hash collision.

Uma boa hash function possui os seguintes atributos:

• É fácil calcular a hash function (a função tem baixa complexidade de tempo)

• A chance de colisão é muito baixa

• Todos os valores possíveis são usados de forma aproximadamente igual

Hash Tables

Às vezes, nós queremos associar uma chave a um valor, por exemplo, nós queremos associar o nome de um aluno a sua média geral, para isso, utilizamos hashmaps (ou hash tables). Tal estrutura de dados é muito útil para resolver diversos problemas, e ela funciona de um jeito bem interessante.

Existe um array de tamanho fixo, e nós queremos associar um valor a uma chave. Para isso, precisamos usar uma hash function para obter o hash value da chave. Esse hash value será o índice em que o nosso valor estará.

Sempre que quisermos acessar esse valor, basta usarmos a hash function na chave novamente, pois a hash function sempre retornará a mesma hash value para o mesmo input.

Vamos ver um exemplo, pense numa hash function f(x) = len(x) % 6:

A medida que o número de chaves aumenta, colisões se tornam inevitáveis de acordo com o pigeonhole principle. O que fazer, então? Não seria interessante para a gente perder o valor armazenado na nossa estrutura de dados, então o que podemos fazer é salvar uma estrutura de dados dinâmica em cada índice, assim, só precisamos acrescentar o valor que tem o mesmo hash value nesta estrutura. Esse método é chamado Separate Chaining, e geralmente utiliza-se uma Linked List.

Cada linguagem de programação possui uma implementação de hashmap, por exemplo, no Python temos o Dictionary. Então, você provavelmente não vai ter que implementar sua própria hashmap, a menos que você queira, mas ainda assim é interessante saber como ela funciona.