Please enable JavaScript.
Coggle requires JavaScript to display documents.
C++ - Coggle Diagram
C++
Hashing
Conceito
Dicionários baseados em tabelas hash
Função Hash
Mapeia chave para posição na tabela
Exemplos
h(K) = K mod m
Para strings: soma dos valores ordinais
Propriedades Desejáveis
Distribuição uniforme
Cálculo eficiente
Load factor α = n/m
Resolução de Colisões
Open Hashing (Encadeamento Separado)
Cada célula contém uma lista ligada
Load Factor
Sucesso: 1 + α/2
Falha: α
Closed Hashing (Endereçamento Aberto)
Linear Probing
Procura próxima célula vazia
Problema: formação de clusters
Double Hashing
Segunda função hash reduz clusters
Operações
Busca, inserção e deleção: O(1) na média
Comparação com Árvores Balanceadas
Hashing: O(1), mas sem ordenação
Árvores balanceadas: O(log n) e mantém ordenação
Sets
Conceito
Conjunto é uma coleção não ordenada de elementos distintos
Representações
Vetor de bits
Listas
Operações Básicas
Verificação de pertinência
União de conjuntos
Interseção de conjuntos
Dictionaries
Conceito
Estrutura de dados para busca, inserção e remoção
Relação com Busca
Solução para busca em contexto dinâmico
Implementações Comuns
Arrays
Hashing
Árvores balanceadas