Tabela de Dispersão

Nesta unidade do curso, iremos estudar as tabelas de dispersão (hash table). Pense em uma busca que não demora, que não precisa de caminhadas longas por uma lista ou descidas por uma árvore. Imagine que você pode encontrar qualquer dado em um instante, de forma quase mágica. Essa é a promessa de uma tabela de dispersão.

Vamos explorar o conceito de função de hash, que é o coração dessa estrutura, e aprenderemos a lidar com as colisões. Ao final, você terá em mãos uma das ferramentas mais rápidas e eficientes para a manipulação de grandes volumes de dados desde dicionários de programação até caches de navegador e bancos de dados.

Problematização

Você está desenvolvendo um RPG retrô com restrições severas de memória, limitando seu catálogo mestre de itens a um array de apenas 10 slots (índices de 0 a 9).

No entanto, o jogo tem muito mais do que 10 itens no total, e cada um tem um ID inteiro único (a chave).

Coleção de itens coletados no jogo
Item	ID (chave)
Poção de Vida	12
Amuleto Raro	18
Espada Longa	21
Armadura de Bronze	3
Armadura de Ouro	15

O desafio é como mapear IDs maiores que 9 (12, 22, 13) para um array com slots numerados de 0 a 9, e ainda assim conseguir encontrá-los rapidamente?

Proposta de solução

A ideia é usar uma função que transforma qualquer ID em um número entre 0 e 9, reaproveitando o mesmo espaço de forma controlada.

Essa função é o módulo (resto da divisão):

\[h(id) = id\bmod 10\]

Como o divisor é $10$, os únicos valores de resto possíveis são os números de 0 a 9, como desejamos.

Se liga! O resto da divisão de qualquer inteiro pelo inteiro $m$ está no intervalo $[0,m-1]$.

Aplicando a função aos nossos itens:

$h(12) = 12 \bmod 10 = 2$
$h(18) = 18 \bmod 10 = 8$
$h(21) = 21 \bmod 10 = 1$
$h(3)\,\,\,= 3\,\,\,\bmod 10 = 3$
$h(15) = 15 \bmod 10 = 5$

Dessa maneira, nosso vetor resultante seria:

0	1	2	3	4	5	6	7	8	9
❌	Espada Longa	Poção de Vida	Armadura de Bronze	❌	Armadura de Ouro	❌	❌	Amuleto Raro	❌

Agora, para verificar se o jogador possui o Amuleto Raro, basta aplicar novamente a mesma função: $h(18) = 18 \bmod 10 = 8$. Sem precisar percorrer todo o array, o jogo já sabe que o item (se existir) estará na posição $8$.

Se liga! Essa técnica permite economizar memória e acessar elementos em tempo constante, O(1).

Um questionamento comum acontece quando a função retorna o mesmo valor para duas chaves distintas. Por exemplo, com uma chave $25$, teremos $f(25)=25\bmod 10=5$, mas a posição $5$ já está ocupada e o vetor não está totalmente preenchido. Nesse caso, dizemos que ocorreu uma colisão.

Colisões são indesejáveis! Precisamos de funções bem definidas para evitar esse tipo de problema.

Se liga! A função que escolhemos anteriormente é chamada de função de hash. Existem várias versões, mas a que mostramos é uma das mais simples.

Nesta unidade, você aprendeu

✅ o que é uma tabela de dispersão

✅ onde uma tabela de dispersão é usada

✅ como é controlada a entrada na tabela de dispersão

# O que é uma tabela de dispersão ? > Pense na principal característica que a torna eficiente. 1. [ ] Uma estrutura que armazena elementos de forma sequencial. 1. [x] Uma estrutura que mapeia chaves a posições em um vetor usando uma função de hash. 1. [ ] Um tipo especial de árvore binária balanceada. 1. [ ] Um vetor ordenado que permite busca binária. # Qual é a principal função da função de hash em uma tabela de dispersão? > Ela define como os elementos são distribuídos. 1. [ ] Ordenar as chaves em ordem crescente. 1. [x] Converter uma chave em um índice válido da tabela. 1. [ ] Calcular o número total de colisões. 1. [ ] Garantir que não haja duplicatas. # O que o operador módulo faz no cálculo do hash? > Ele define o intervalo possível de posições. 1. [x] Retorna o resto da divisão da chave por um número fixo. 1. [ ] Retorna o quociente da divisão inteira. 1. [ ] Multiplica a chave pelo tamanho do vetor. 1. [ ] Subtrai a chave de 10. # Dado o hash $h(k) = k \bmod 9$, qual é o valor de $h(21)$? > Basta aplicar a operação de módulo. 1. [ ] 0 1. [x] 3 1. [ ] 2 1. [ ] 9 # O que caracteriza uma colisão em uma tabela de dispersão? > É quando duas chaves competem pelo mesmo espaço. 1. [ ] Quando duas chaves possuem o mesmo endereço. 1. [x] Quando duas chaves diferentes são mapeadas para o mesmo índice. 1. [ ] Quando uma chave é removida da tabela. 1. [ ] Quando o vetor está completamente vazio. # Quais são consequências de uma função de hash mal projetada? > Pense nos efeitos diretos sobre desempenho e armazenamento. - [x] Aumento do número de colisões. - [x] Desempenho pior nas buscas. - [ ] Redução automática do tamanho da tabela. - [ ] Melhoria na aleatoriedade das chaves. # Qual é a complexidade média de acesso a um elemento em uma tabela de dispersão bem implementada? > A eficiência é o principal atrativo dessa estrutura. 1. [x] O(1) 1. [ ] O(log n) 1. [ ] O(n) 1. [ ] O(n log n) # Qual das opções descreve melhor uma função de hash simples? > Baseie-se no exemplo do texto. 1. [ ] Uma função que ordena as chaves antes de armazená-las. 1. [ ] Uma função que soma todos os dígitos da chave. 1. [x] Uma função que calcula o resto da divisão da chave pelo tamanho do vetor. 1. [ ] Uma função que gera um número aleatório. # Quais aplicações reais fazem uso de tabelas de dispersão? > Elas aparecem em vários contextos computacionais. - [x] Dicionários em linguagens de programação. - [x] Caches de navegadores. - [x] Índices de bancos de dados. - [ ] Árvores de decisão para IA.

De volta ao topo