Explorando Hashmaps: Uma Visão Completa

Fala galera da programação, tudo beleza? Você já ouviu falar sobre Hashmap? Venha descubrir o poder dos Hashmaps. Vamos fazer uma abordagem completa sobre esta estrutura de dados essencial. Aprenda sobre funções de hash, eficiência e aplicações práticas.

 

Introdução

Na ciência da computação, um dos desafios mais comuns é a organização e recuperação eficiente de dados. Um dos conceitos mais poderosos para resolver esse problema é o hashmap, também conhecido como mapa de hash ou tabela de dispersão. Neste artigo, exploraremos profundamente o funcionamento, a aplicação e os benefícios dos hashmaps, com exemplos práticos para ilustrar seu uso.

 

O que é um Hashmap?

Um hashmap é uma estrutura de dados que mapeia chaves para valores. Ele opera com base em uma função de hash, que converte a chave em um índice na estrutura de dados. Este índice é então utilizado para armazenar e recuperar o valor associado àquela chave. A principal vantagem de um hashmap é a sua capacidade de realizar operações de busca, inserção e remoção em tempo constante, em média, quando a função de hash distribui uniformemente os valores na estrutura de dados.

 

Como Funciona um Hashmap?

O funcionamento básico de um hashmap pode ser dividido em algumas etapas simples:

1. Cálculo do Hash: Quando uma chave é passada para o hashmap, ela é submetida a uma função de hash, que gera um valor numérico único para aquela chave. Este valor é geralmente usado como um índice na estrutura de dados subjacente.
2. Indexação: O valor hash calculado é então usado para determinar onde na estrutura de dados o par chave-valor deve ser armazenado ou recuperado.
3. Tratamento de Colisões: Uma colisão ocorre quando duas chaves diferentes produzem o mesmo valor de hash. Existem várias técnicas para lidar com colisões, como encadeamento de listas, resolução de colisões por sondagem e hashing duplo.
4. Armazenamento e Recuperação: Após o tratamento de colisões, o par chave-valor é armazenado ou recuperado no local determinado pelo valor de hash.

 

Aplicações de Hashmaps

Os hashmaps são amplamente utilizados em uma variedade de contextos de programação, incluindo:

• Implementação de Dicionários e Conjuntos: Os hashmaps são ideais para implementar estruturas de dados associativas como dicionários e conjuntos, onde os elementos são armazenados e recuperados por chaves únicas.
• Cache de Dados: Hashmaps são frequentemente utilizados em sistemas de cache de dados para armazenar valores temporários que são acessados com frequência.
• Contagem de Ocorrências: Em análise de dados, os hashmaps são úteis para contar a ocorrência de elementos únicos em uma coleção de dados.
• Roteamento em Redes: Em sistemas de roteamento de redes, os hashmaps podem ser usados para armazenar informações sobre endereços IP e suas respectivas rotas.

 

Exemplos Práticos

Exemplo 1: Implementação de um Hashmap em Python

'''

Criado pelo Professor Giovani Da Cruz
https://giovanidacruz.com.br

'''
class Hashmap:
    def __init__(self):
        self.size = 10
        self.map = [None] * self.size

    def get_hash(self, key):
        return hash(key) % self.size

    def add(self, key, value):
        key_hash = self.get_hash(key)
        self.map[key_hash] = value

    def get(self, key):
        key_hash = self.get_hash(key)
        return self.map[key_hash]

# Uso do Hashmap
h = Hashmap()
h.add('a', 100)
h.add('b', 200)
print(h.get('a'))  # Saída: 100
print(h.get('b'))  # Saída: 200

Explicação:

Imagine um hashmap como uma grande caixa cheia de pequenas caixas numeradas. Cada vez que você coloca algo dentro da grande caixa, você dá a esse algo um número especial, chamado de “hash”. Esse número é como um endereço para encontrar a pequena caixa correspondente na grande caixa.

No exemplo em Python:

1. Inicialização do Hashmap:
   • Primeiro, criamos uma grande caixa (que chamamos de map) com espaço para 10 pequenas caixas dentro dela.
2. Adição de itens:
   • Quando queremos adicionar algo à grande caixa, usamos uma fórmula especial (a função get_hash) para calcular o número (o hash) que vai identificar a pequena caixa onde vamos guardar esse algo.
   • Por exemplo, se quisermos guardar o número 1, a fórmula nos dá o número 3. Então colocamos o número 1 dentro da pequena caixa número 3.
3. Recuperação de itens:
   • Quando queremos encontrar o número 1 novamente, usamos a mesma fórmula para calcular onde ele está. A fórmula nos dá o número 3, então sabemos que o número 1 está na pequena caixa número 3.

Em resumo, o hashmap é como uma grande caixa com muitas pequenas caixas numeradas. Você coloca coisas dentro usando números especiais (hashes) e depois pode encontrá-las rapidamente usando esses números especiais. É uma maneira eficiente de guardar e encontrar coisas!

 

Exemplo 2: Uso de Hashmap em Contagem de Ocorrências

'''

Criado pelo Professor Giovani Da Cruz
https://giovanidacruz.com.br

'''
def count_occurrences(arr):
    occurrence_map = {}
    for item in arr:
        if item in occurrence_map:
            occurrence_map[item] += 1
        else:
            occurrence_map[item] = 1
    return occurrence_map

# Uso do Hashmap para contar ocorrências
arr = [1, 2, 3, 1, 2, 1, 3, 4, 5]
print(count_occurrences(arr))  # Saída: {1: 3, 2: 2, 3: 2, 4: 1, 5: 1}

Explicação

Imagine que você tem uma caixa cheia de números escritos em pequenos pedaços de papel. Você quer saber quantas vezes cada número aparece nessa caixa. Aqui está o que acontece:

1. Definição da Função count_occurrences:
   • Esta função conta o número de vezes que cada número aparece na caixa.
   • Para fazer isso, ela usa uma caixa (que chamamos de occurrence_map) para registrar quantas vezes cada número aparece.
2. Loop Através da Caixa de Números:
   • A função percorre cada número na caixa um por um.
   • Para cada número, ela verifica se já o viu antes. Se sim, ela adiciona 1 ao número de vezes que o número já apareceu na caixa. Se não, ela começa a contar a partir de 1.
3. Retorno do Resultado:
   • Depois de contar todas as ocorrências, a função retorna a caixa de ocorrências completa.
4. Uso da Função:
   • Finalmente, é dada à função uma caixa de números (por exemplo, [1, 2, 3, 1, 2, 1, 3, 4, 5]).
   • A função conta quantas vezes cada número aparece e imprime o resultado.

Então, a função count_occurrences é como um assistente que conta quantas vezes cada número aparece em uma caixa cheia de números. É útil quando você precisa saber com que frequência certos números aparecem em uma lista.

Ou seja, para este nosso exemplo:

Número 1: Apareceu 3 Vezes;
Número 2: Apareceu 2 Vezes;
Número 3: Apareceu 2 Vezes;
Número 4: Apareceu 1 Vez;
Número 5: Apareceu 1 Vez.

 

Agora vamos ver os exemplos na linguagem Go.

Exemplo 1: Implementação de um Hashmap em Go

/******************************************************************************

Criado pelo Professor Giovani Da Cruz
htttp://giovanidacruz.com.br

*******************************************************************************/
package main

import (
    "fmt"
    "hash/fnv"
)

type Hashmap struct {
    size    int
    mapData map[int]interface{}
}

func NewHashmap(size int) *Hashmap {
    return &Hashmap{
        size:    size,
        mapData: make(map[int]interface{}),
    }
}

func (h *Hashmap) getHash(key string) int {
    hfunc := fnv.New32a()
    hfunc.Write([]byte(key))
    return int(hfunc.Sum32()) % h.size
}

func (h *Hashmap) Add(key string, value interface{}) {
    keyHash := h.getHash(key)
    h.mapData[keyHash] = value
}

func (h *Hashmap) Get(key string) interface{} {
    keyHash := h.getHash(key)
    return h.mapData[keyHash]
}

func main() {
    h := NewHashmap(10)
    h.Add("a", 1)
    h.Add("b", 2)
    fmt.Println(h.Get("a")) // Saída: 1
    fmt.Println(h.Get("b")) // Saída: 2
}

Explicação:

• Definição do Hashmap:
  • Definimos uma estrutura Hashmap, que contém dois campos: size, que é o tamanho do hashmap, e mapData, que é o mapa real onde os dados serão armazenados.
• Criação de um Novo Hashmap:
  • A função NewHashmap cria uma nova instância de Hashmap com um tamanho especificado. Inicializa o mapa interno (mapData) com a função make.
• Cálculo do Hash:
  • O método getHash calcula o hash de uma chave. Em Go, usamos o tamanho da chave (comprimento de key) e o dividimos pelo tamanho do hashmap (size).
• Adição de um Par Chave-Valor:
  • O método Add adiciona um par chave-valor ao hashmap. Calcula o hash da chave e usa esse valor para acessar o mapa interno e atribuir o valor correspondente.
• Recuperação de um Valor:
  • O método Get recupera um valor associado a uma chave. Ele calcula o hash da chave e usa esse valor para acessar o mapa interno e retornar o valor correspondente.
• Uso do Hashmap:
  • No main, criamos uma nova instância de Hashmap, adicionamos pares chave-valor e depois os recuperamos usando a função Get. Os valores recuperados são então impressos na tela.

Este exemplo demonstra como usar um hashmap em Go para armazenar e recuperar dados por meio de chaves.

 

Exemplo 2: Uso de Hashmap em Contagem de Ocorrências

package main

import "fmt"

func CountOccurrences(arr []int) map[int]int {
    occurrenceMap := make(map[int]int)
    for _, item := range arr {
        occurrenceMap[item]++
    }
    return occurrenceMap
}

func main() {
    arr := []int{1, 2, 3, 1, 2, 1, 3, 4, 5}
    fmt.Println(CountOccurrences(arr)) // Output: map[1:3 2:2 3:2 4:1 5:1]
}

Explicação:

• Contagem de Ocorrências:
  • A função CountOccurrences recebe uma lista de números (arr) e retorna um mapa que conta quantas vezes cada número aparece na lista.
• Criação do Mapa de Ocorrências:
  • Dentro da função CountOccurrences, criamos um mapa vazio chamado occurrenceMap para armazenar as ocorrências dos números.
• Contagem de Ocorrências:
  • Iteramos sobre a lista de números. Para cada número, verificamos se ele já está no mapa de ocorrências. Se sim, incrementamos o valor correspondente; se não, inicializamos com 1.
• Retorno do Mapa de Ocorrências:
  • Após contar todas as ocorrências, retornamos o mapa de ocorrências completo.
• Uso da Função:
  • No main, criamos uma lista de números e chamamos a função CountOccurrences passando essa lista como argumento. A função conta as ocorrências e imprime o resultado.

Este exemplo mostra como usar um hashmap em Go para contar quantas vezes cada número aparece em uma lista de números.

 

Conclusão

Os hashmaps são uma ferramenta poderosa e versátil em ciência da computação, oferecendo uma maneira eficiente de organizar e acessar dados. Com seu desempenho rápido e flexibilidade, os hashmaps são uma escolha popular para uma variedade de problemas de programação. Ao compreender os princípios subjacentes dos hashmaps e suas aplicações práticas, os desenvolvedores podem aproveitar ao máximo essa estrutura de dados em seus projetos.

 

Beleza pessoal? Espero que possa ajudar!

 

Dúvidas ou sugestões? Deixe o seu comentário!

 

Um abraço e até o próximo post. Valeu!

 

#Hashmap

#EstruturasDeDados

#Programação

#LinkedInLearning

#GiovaniDaCruz