Profa.
Pauliane Cardoso
CENTRO UNIVERSITÁRIO DE GOIATUBA
CURSO GESTÃO DA TECNOLOGIA DA INFORMAÇÃO
Disciplina: ESTRUTURA DE DADOS APLICADO À BIG
Data: 28 / 08 / 2024
DATA Período: 4°
Professor(a): Pauliane Cardoso Alves Ferreira
CONCEITOS BÁSICOS DE ESTRUTURAS DE DADOS - HASH
As tabelas hash são uma estrutura de dados que permite armazenar pares de
chave-valor de maneira eficiente, facilitando a inserção, busca e remoção de elementos.
Estrutura Básica
1. Chave e Valor: Cada elemento na tabela hash é armazenado como um par de
chave e valor. A chave é única e é usada para acessar o valor correspondente.
2. Array Interno: A tabela hash utiliza um array (ou vetor) para armazenar os
pares chave-valor. O tamanho desse array é denominado de "tamanho da tabela"
ou "capacidade".
Função Hash
A função hash é um componente crucial das tabelas hash. Ela transforma uma chave em
um índice no array. As características de uma boa função hash incluem:
• Determinística: A mesma chave deve sempre gerar o mesmo índice.
• Distribuição Uniforme: Deve gerar índices que estejam uniformemente
distribuídos ao longo do array, minimizando colisões.
• Rápida: A computação do índice deve ser rápida para garantir eficiência.
Colisões
Colisões ocorrem quando duas chaves diferentes geram o mesmo índice. Existem várias
técnicas para lidar com colisões:
1. Encadeamento (Chaining): Cada posição no array é um ponteiro para uma lista
encadeada (ou outra estrutura) que armazena todos os pares chave-valor que
colidiram. Assim, se houver uma colisão, o novo par é adicionado à lista.
2. Endereçamento Aberto: Quando ocorre uma colisão, a tabela procura a
próxima posição disponível no array. Existem várias estratégias para isso, como:
Profa. Pauliane Cardoso
• Linear Probing: A busca se move sequencialmente.
• Quadratic Probing: A busca utiliza um incremento quadrático.
• Double Hashing: Usa uma segunda função hash para determinar o
próximo índice.
Operações Básicas
• Inserção: Para inserir um par chave-valor, a função hash é aplicada à chave para
determinar o índice. Se não houver colisão, o par é inserido. Se houver, utiliza-se
a técnica de resolução de colisão.
• Busca: Para buscar um valor, a chave é passada pela função hash, e o índice
resultante é verificado. Se a chave estiver presente, o valor correspondente é
retornado.
• Remoção: A remoção também utiliza a função hash. Se a chave estiver presente,
o par é removido; caso contrário, pode-se retornar um erro ou um valor nulo.
Redimensionamento
Quando a tabela hash se torna muito cheia (geralmente quando a carga ultrapassa 70-
80%), ela pode ser redimensionada. Isso envolve criar um novo array maior e reinserir
todos os pares chave-valor usando a função hash, o que ajuda a manter a eficiência.
Exemplo: Contagem de Palavras
Vamos usar um dicionário para contar a frequência de palavras em uma frase, esse
exemplo demonstra como as tabelas hash (através de dicionários) facilitam operações de
busca e inserção de forma eficiente.
# Frase de exemplo
texto = "a tabela hash é uma estrutura de dados eficiente e a tabela hash é muito
utilizada"
# Criação do dicionário para contagem
contagem = {}
# Contando as palavras
for palavra in [Link]():
# Remove pontuação e coloca em minúsculas
palavra = [Link]().lower()
# Atualiza a contagem
if palavra in contagem:
contagem[palavra] += 1
Profa. Pauliane Cardoso
else:
contagem[palavra] = 1
# Exibindo os resultados
for palavra, quantidade in [Link]():
print(f"'{palavra}': {quantidade}")
Explicação:
1. Texto: Definimos uma string que contém várias palavras.
2. Dicionário contagem: Usamos um dicionário para armazenar a frequência de
cada palavra.
3. Loop: Iteramos sobre cada palavra, removendo pontuação e convertendo para
minúsculas.
4. Atualização do Dicionário: Se a palavra já estiver no dicionário, aumentamos
sua contagem; caso contrário, inicializamos com 1.
5. Resultado: Por fim, imprimimos a contagem de cada palavra.
Vantagens:
• Tempo médio de busca, inserção e remoção é O(1).
• Boa performance para operações em grandes conjuntos de dados.
Desvantagens:
• O desempenho pode degradar para O(n) em situações de muitas colisões.
• A escolha da função hash é crítica.
• O uso de memória pode ser ineficiente se a tabela não for bem dimensionada.