# 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.&#x20;

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

60 nesse cenário seria o _hash value_.&#x20;

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

\[20, 40, 100] -> (20 + 40 + 100) % 100 = 60.&#x20;

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á.&#x20;

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.&#x20;

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

<figure><img src="https://3099726359-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FPoUhR6ITF2wdty5CdTAc%2Fuploads%2FsjfSjHJH5yVhWa5pe7hY%2Fhashmap_intro.002.png?alt=media&#x26;token=8eedfd39-b5c2-4137-998a-efcd400ea68f" alt=""><figcaption></figcaption></figure>

A medida que o número de chaves aumenta, colisões se tornam inevitáveis de acordo com o [pigeonhole principle](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Hash_table#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.&#x20;
