Hoje vamos iniciar uma nova série de posts aqui no blog onde vamos conhecer como algumas estruturas de dados funcionam, e para começar, vamos falar da hash table ou hash map.
| Algoritmo | Média | Pior cenário |
|---|---|---|
| Espaço | O(n) | O(n) |
| Busca | O(1) | O(n) |
| Inserção | O(1) | O(n) |
| Exclusão | O(1) | O(n) |
Essa estrutura de dados foi inventada em 1953 e consiste basicamente em uma tabela do tipo key/value. Para calcular a key de um determinado registro usamos uma função chamada de hash function ou hash code.
Idealmente essa função irá gerar uma única key para cada objeto que vamos tentar armazenar nessa estrutura de dados.
Quando a hash function não consegue fazer isso, ou seja, gera a mesma key para mais de um objeto, chamamos isso de hash collision ou colisão de hash.
Para que essa colisão não faça com que um novo objeto sobreponha um objeto que já está alocado na estrutura de dados, o value da hash table, também conhecido como slot ou bucket, é normalmente um array ou uma linked list (vamos falar dessa estrutura no futuro), pois dessa forma podemos armazenar mais de um objeto por key.
Na imagem acima, a solução utilizada para resolver o problema de colisão foi com uma linked list.
E como podemos implementar essa estrutura de dados em Go?
Isso vou explicar em um vídeo no inicio da próxima semana. Por isso se inscreva no nosso canal do Youtube para não ficar de fora do que está rolando por lá também!!!
Deixem suas dúvidas nos comentários.
Até a próxima!
Excelentes conteúdos sobre a linguagem go! Parabéns! 👏👏👏