Algoritmos

Tabela hash: como achar um valor quase sem procurar

Capa do artigo Tabela hash: como achar um valor quase sem procurar
Leitura com foco

Entenda o contexto.
Leve para a prática.

Neste artigo
  1. Como funciona uma tabela hash?
  2. Exemplo de função hash passo a passo
  3. E se duas chaves caírem na mesma gaveta?
  4. Tabela hash em PHP, Python, C e Java
  5. Por que a tabela hash é tão rápida?
  6. Aí você pergunta: já usei tabela hash sem saber?
  7. Agora é com você!

Tabela hash (ou tabela de dispersão) é uma estrutura de dados que guarda pares de chave e valor e usa uma conta feita com a chave para descobrir em que posição o valor deve ficar. Por isso ela encontra um valor sem precisar procurar item por item.

No artigo sobre árvore binária, o desafio era inserir os valores 45, 25, 65, 10 e 30. A resposta: o 45 é a raiz, o 25 fica à esquerda dele e o 65 à direita. O 10 fica à esquerda do 25 e o 30 à direita do 25. As folhas são 10, 30 e 65, e o percurso em ordem mostra 10, 25, 30, 45 e 65. Bateu com o seu desenho?

Como funciona uma tabela hash?

Pense no armário de gavetas numeradas de uma secretaria, com gavetas de 0 a 7. Para guardar a ficha de alguém, você não escolhe a gaveta no olho: faz uma conta com o nome da pessoa, e o resultado diz o número da gaveta. Para achar a ficha depois, é só repetir a mesma conta com o mesmo nome e ir direto na gaveta certa. Sem abrir as outras!

História em quadrinhos em três quadros: diante de um armário com gavetas de 0 a 7, uma pessoa faz uma conta com o nome Bruno, que dá 6, guarda a ficha na gaveta 6 e depois repete a conta para achar a ficha direto
A tabela hash como armário de gavetas: a conta com o nome diz onde guardar e onde procurar.

Essa conta se chama função hash. Ela recebe a chave e devolve um número, que vira a posição dentro de um vetor.

  • Chave: o que você usa para procurar. No nosso exemplo, o nome da pessoa.
  • Valor: o que fica guardado. No nosso exemplo, o ramal do telefone.
  • Função hash: a conta que transforma a chave em posição.

Exemplo de função hash passo a passo

Vamos usar uma função bem simples: somar o código de cada letra da chave e pegar o resto da divisão pelo número de gavetas, que aqui é 8.

ChaveCódigos das letrasSomaResto da divisão por 8
Ana65 + 110 + 972720
Bruno66 + 114 + 117 + 110 + 1115186
Eva69 + 118 + 972844
O resto da divisão é o número da gaveta de cada chave.

Então a Ana vai para a gaveta 0, o Bruno para a 6 e a Eva para a 4. Para buscar o ramal do Bruno, o programa refaz a conta, chega no 6 e pronto!

E se duas chaves caírem na mesma gaveta?

Acontece, e tem nome: colisão. Com a nossa função, “Eva” e “Caio” dão o mesmo resultado: as somas 284 e 380 deixam resto 4 na divisão por 8. As duas chaves disputam a gaveta 4!

Uma solução bem comum é o encadeamento: cada gaveta guarda uma pequena lista. Quem cai na mesma gaveta entra na lista dela, e na hora de buscar o programa percorre só essa listinha, comparando as chaves. Lembra da lista encadeada? Olha ela aparecendo de novo!

Diagrama da tabela hash: a chave Bruno passa pela função hash, que calcula a gaveta 6, em uma tabela de oito gavetas com uma colisão na gaveta 4
Da chave à gaveta: a função hash calcula a posição, e duas chaves na mesma gaveta formam uma colisão.
Ver a animação da tabela hash, passo a passo
Animação de uma tabela hash com oito gavetas recebendo as chaves Ana, Bruno, Eva e Caio, com a colisão na gaveta 4 e a busca por Bruno e por Caio
A conta com a chave aponta a gaveta. Na colisão, a gaveta vira uma pequena lista.

Tabela hash em PHP, Python, C e Java

Veja em PHP:

<?php

class TabelaHash
{
    private array $gavetas;

    public function __construct(private int $tamanho = 8)
    {
        $this->gavetas = array_fill(0, $tamanho, []);
    }

    private function hash(string $chave): int
    {
        $soma = 0;

        foreach (str_split($chave) as $letra) {
            $soma += ord($letra); // soma o código de cada letra
        }

        return $soma % $this->tamanho; // o resto da divisão vira a posição
    }

    public function guardar(string $chave, string $valor): void
    {
        $posicao = $this->hash($chave);

        foreach ($this->gavetas[$posicao] as $i => [$chaveGuardada]) {
            if ($chaveGuardada === $chave) {
                $this->gavetas[$posicao][$i] = [$chave, $valor]; // chave repetida: troca o valor
                return;
            }
        }

        $this->gavetas[$posicao][] = [$chave, $valor];
    }

    public function buscar(string $chave): ?string
    {
        $posicao = $this->hash($chave);

        foreach ($this->gavetas[$posicao] as [$chaveGuardada, $valor]) {
            if ($chaveGuardada === $chave) {
                return $valor;
            }
        }

        return null; // a chave não existe
    }
}

$ramais = new TabelaHash();
$ramais->guardar('Ana', '2101');
$ramais->guardar('Bruno', '2102');
$ramais->guardar('Eva', '2103');

echo $ramais->buscar('Bruno'), PHP_EOL; // 2102
echo $ramais->buscar('Eva'), PHP_EOL;   // 2103

Em Python:

class TabelaHash:
    def __init__(self, tamanho=8):
        self.tamanho = tamanho
        self.gavetas = [[] for _ in range(tamanho)]

    def _hash(self, chave):
        soma = 0

        for letra in chave:
            soma += ord(letra)  # soma o código de cada letra

        return soma % self.tamanho  # o resto da divisão vira a posição

    def guardar(self, chave, valor):
        gaveta = self.gavetas[self._hash(chave)]

        for item in gaveta:
            if item[0] == chave:
                item[1] = valor  # chave repetida: troca o valor
                return

        gaveta.append([chave, valor])

    def buscar(self, chave):
        gaveta = self.gavetas[self._hash(chave)]

        for chave_guardada, valor in gaveta:
            if chave_guardada == chave:
                return valor

        return None  # a chave não existe


ramais = TabelaHash()
ramais.guardar("Ana", "2101")
ramais.guardar("Bruno", "2102")
ramais.guardar("Eva", "2103")

print(ramais.buscar("Bruno"))  # 2102
print(ramais.buscar("Eva"))    # 2103

E em C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TAMANHO 8

struct Item {
    const char *chave;
    int valor;
    struct Item *proximo;
};

struct Item *gavetas[TAMANHO];

int hash(const char *chave) {
    int soma = 0;

    for (int i = 0; chave[i] != '\0'; i++) {
        soma += (unsigned char) chave[i]; // soma o código de cada letra
    }

    return soma % TAMANHO; // o resto da divisão vira a posição
}

void guardar(const char *chave, int valor) {
    int posicao = hash(chave);

    for (struct Item *item = gavetas[posicao]; item != NULL; item = item->proximo) {
        if (strcmp(item->chave, chave) == 0) {
            item->valor = valor; // chave repetida: troca o valor
            return;
        }
    }

    struct Item *novo = malloc(sizeof(struct Item));

    if (novo == NULL) {
        return; // sem memória
    }

    novo->chave = chave;
    novo->valor = valor;
    novo->proximo = gavetas[posicao]; // entra no início da lista da gaveta
    gavetas[posicao] = novo;
}

int buscar(const char *chave) {
    for (struct Item *item = gavetas[hash(chave)]; item != NULL; item = item->proximo) {
        if (strcmp(item->chave, chave) == 0) {
            return item->valor;
        }
    }

    return -1; // a chave não existe
}

int main(void) {
    guardar("Ana", 2101);
    guardar("Bruno", 2102);
    guardar("Eva", 2103);

    printf("%d\n", buscar("Bruno")); // 2102
    printf("%d\n", buscar("Eva"));   // 2103

    for (int i = 0; i < TAMANHO; i++) {
        while (gavetas[i] != NULL) {
            struct Item *proximo = gavetas[i]->proximo;
            free(gavetas[i]); // em C, você devolve a memória de cada item
            gavetas[i] = proximo;
        }
    }

    return 0;
}

E em Java:

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class TabelaHash {
        private final int tamanho;
        private final List<List<String[]>> gavetas = new ArrayList<>();

        TabelaHash(int tamanho) {
            this.tamanho = tamanho;
            for (int i = 0; i < tamanho; i++) {
                gavetas.add(new ArrayList<>());
            }
        }

        private int hash(String chave) {
            int soma = 0;
            for (char letra : chave.toCharArray()) {
                soma += letra; // soma o código de cada letra
            }
            return soma % tamanho; // o resto da divisão vira a posição
        }

        void guardar(String chave, String valor) {
            List<String[]> gaveta = gavetas.get(hash(chave));
            for (String[] item : gaveta) {
                if (item[0].equals(chave)) {
                    item[1] = valor; // chave repetida: troca o valor
                    return;
                }
            }
            gaveta.add(new String[] {chave, valor});
        }

        String buscar(String chave) {
            for (String[] item : gavetas.get(hash(chave))) {
                if (item[0].equals(chave)) {
                    return item[1];
                }
            }
            return null; // a chave não existe
        }
    }

    public static void main(String[] args) {
        TabelaHash ramais = new TabelaHash(8);
        ramais.guardar("Ana", "2101");
        ramais.guardar("Bruno", "2102");
        ramais.guardar("Eva", "2103");
        System.out.println(ramais.buscar("Bruno")); // 2102
        System.out.println(ramais.buscar("Eva"));   // 2103
    }
}

Observe que guardar e buscar seguem o mesmo roteiro: calcular a posição com a função hash e olhar só aquela gaveta. E repare em um detalhe do guardar: se a chave já existe, o valor é trocado, porque em uma tabela hash cada chave aparece uma vez só.

Por que a tabela hash é tão rápida?

EstruturaComo encontra um valorComparações em 1.000.000 de itens
Vetor sem ordemOlha item por itemAté 1.000.000
Vetor ordenado, com busca bináriaCorta pela metade a cada passoAté 20
Tabela hashCalcula a posição e vai diretoPoucas, se as chaves estiverem bem espalhadas
Comparação entre as formas de busca que vimos até aqui.

Mas ATENÇÃO: isso só vale quando a função hash espalha bem as chaves. Se todas caírem na mesma gaveta, a busca vira uma busca item por item dentro dela. A documentação do Python faz o mesmo aviso sobre os dicionários: as operações são rápidas no caso médio, e no pior caso, quando todas as chaves resultam no mesmo hash, o tempo passa a crescer junto com a quantidade de itens.

E tem um preço: a tabela hash não guarda as chaves em ordem de tamanho. Se você precisa dos valores em ordem crescente, quem resolve é a árvore binária de busca. Cada estrutura tem a sua hora!

Aí você pergunta: já usei tabela hash sem saber?

Muito provavelmente! O manual do PHP diz que os arrays da linguagem são, na verdade, tabelas hash ordenadas. E o dicionário do Python também trabalha com o hash das chaves. Veja em PHP:

<?php

$ramais = ['Ana' => '2101', 'Bruno' => '2102'];
$ramais['Eva'] = '2103';

echo $ramais['Bruno'], PHP_EOL; // 2102

E em Python:

ramais = {"Ana": "2101", "Bruno": "2102"}
ramais["Eva"] = "2103"

print(ramais["Bruno"])  # 2102

E em Java, a classe pronta é a HashMap, que a documentação descreve como uma implementação de mapa baseada em tabela hash:

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> ramais = new HashMap<>();
        ramais.put("Ana", "2101");
        ramais.put("Bruno", "2102");
        ramais.put("Eva", "2103");
        System.out.println(ramais.get("Bruno")); // 2102
    }
}

Toda vez que você escreve $ramais['Bruno'], acontece por baixo dos panos o que você acabou de aprender: uma conta com a chave e um pulo direto para a posição. Quem diria… Agora você sabe o que está por trás!

Agora é com você!

No papel: em qual gaveta a nossa função hash coloca a chave Bia? Os códigos das letras são B = 66, i = 105 e a = 97. Ela colide com alguém do exemplo? Depois confira no código, mostrando na tela o resultado da função hash para “Bia”.

E um desafio maior: crie o método remover, que apaga uma chave da tabela. Pense antes de digitar: em qual gaveta procurar? Tente sozinho, sem pedir a resposta pronta para ninguém. Você consegue!

Com a tabela hash fechamos a trilha de estruturas de dados: lista encadeada, fila, árvore binária e tabela hash. Se você acompanhou e fez os desafios, já tem uma base firme para seguir em frente. No próximo artigo começamos outra trilha, a de orientação a objetos na prática, com os princípios SOLID. Até lá!

Confiança Sempre!!!

Fontes:

Compartilhe este artigo

Sobre quem escreve

Walmir Silva

Olá! Sou Walmir, engenheiro de software com MBA em Engenharia de Software e o cérebro por trás do GrowthCode e autor do livro "Além do Código".

Se você acha que programação é apenas sobre escrever código, prepare-se para expandir seus horizontes. Aqui, nós vamos além do código e exploramos as interseções fascinantes entre tecnologia, negócios, artes e filosofia.

Você está em busca de crescimento na carreira? Quer se destacar em um mercado competitivo? Almeja uma vida mais rica em conhecimento e realização? Então você chegou ao lugar certo. No GrowthCode, oferecemos insights profundos, estratégias comprovadas e um toque de sabedoria filosófica para catalisar seu crescimento pessoal e profissional.

Ver todos os artigos →

Continue a conversa

Compartilhe sua perspectiva

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Guardamos o IP e o navegador de quem comenta por 6 meses, para barrar spam e porque o Marco Civil da Internet pede a guarda dos registros de acesso por esse prazo. Veja como tratamos seus dados.

Encontre sua próxima resposta

O que você quer aprender?

Preferências de cookies

Os cookies opcionais começam desligados. Você pode mudar a escolha a qualquer momento por esta tela.

NecessáriosSempre ativos

Guardam a sua escolha de cookies e o código do registro dela, e mantêm o site funcionando. Não são usados para publicidade.

Contam visitas e mostram como o site é usado: Google Analytics e Microsoft Clarity, carregados pelo Google Tag Manager.

Exibem anúncios do Google AdSense sem personalização. Os cookies desta categoria limitam a repetição dos anúncios e medem o resultado deles.

Usa a sua navegação para escolher anúncios e formar públicos de anúncio: anúncios do Google escolhidos pelos seus interesses e os indicadores do Google no Analytics. Desligado, os anúncios aparecem sem personalização. Depende de Publicidade.

Também é possível bloquear cookies nas configurações do navegador. Detalhes na Política de privacidade.