Capítulo 13: Generics (Generic[T]), Tabelas Hash, Conjuntos (set) e Dicionários (dict)

Especialização em Sistemas com Python & POO com Type Hints • Capítulo 13

---

🗺️ Mapa Conceitual do Tópico

flowchart TD
    subgraph HASH_ENGINE["Arquitetura de Tabelas Hash do CPython"]
        HASH_FUNC["Função hash(obj) & Método __hash__()\nContrato de Imutabilidade & Igualdade Estrutural (__eq__)"]
        COMPACT_DICT["Dicionário Compacto (PEP 468)\nPreservação de Ordem de Inserção & Economia de 25% na Heap"]
        SET_ALGEBRA["Conjuntos Matemáticos (set & frozenset)\nUnião (|) · Interseção (&) · Diferença (-) em Tempo O(1)"]
    end

    subgraph GENERICS["Programação Genérica em Python"]
        PEP695["Python 3.12+ (PEP 695): Sintaxe Nativa\nclass Repositorio[T]: · def processar[T](item: T)"]
        CLASSIC_GEN["Sintaxe Clássica (PEP 484)\nTypeVar('T') · Generic[T] · Variância (Covariante / Invariante)"]
    end

    subgraph COLLECTIONS["Coleções Especializadas (collections)"]
        DEFAULTDICT["defaultdict: Fábricas Automáticas de Chaves"]
        COUNTER["Counter: Frequência Estatística & Histograma"]
    end

    HASH_ENGINE --> COLLECTIONS
    HASH_ENGINE --> GENERICS
    GENERICS --> PROD["Estruturas de Dados Tipadas para Microsserviços e Big Data"]

    style HASH_ENGINE fill:#ede7f6,stroke:#512da8,stroke-width:2px
    style GENERICS fill:#e1f5fe,stroke:#0288d1,stroke-width:2px
    style COLLECTIONS fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px

---

🗄️ 1. A Mecânica das Tabelas Hash no CPython

Tanto dict quanto set em Python repousam sobre tabelas hash de alta performance que oferecem tempo de busca, inserção e remoção médio constante $O(1)$.

O Contrato de Hashability

Para que um objeto possa ser inserido em um set ou usado como chave de um dict, ele deve ser Hashable:

1. Deve implementar __hash__() e retornar um número inteiro fixo durante toda a sua existência.
2. Deve implementar __eq__() de modo que se a == b, obrigatoriamente hash(a) == hash(b).
3. Objetos mutáveis nativos (list, dict, set) NÃO são hashable (TypeError: unhashable type: 'list'), pois sua mutação alteraria o bucket da tabela hash, corrompendo a integridade da busca.

A Estrutura Compacta do Dicionário (PEP 468)

Desde o Python 3.6/3.7, o CPython armazena dicionários separando os índices hash de uma tabela esparsa de um array contíguo e denso que armazena os pares (hash, chave, valor):

• Garante preservação determinística da ordem de inserção.
• Reduz o consumo de memória RAM entre 20% e 25% comparado a implementações antigas.

---

🔢 2. Álgebra de Conjuntos (set e frozenset)

O tipo set (mutável) e frozenset (imutável e hashable) fornecem operações completas da teoria dos conjuntos matemáticos com sintaxe nativa de operadores sobrecarregados:

Operação Matemática	Operador Python	Método Equivalente	Significado Conceitual
União	A \| B	A.union(B)	Elementos presentes em $A$, em $B$ ou em ambos.
Interseção	A & B	A.intersection(B)	Apenas os elementos comuns a $A$ e $B$.
Diferença	A - B	A.difference(B)	Elementos que estão em $A$, mas NÃO estão em $B$.
Diferença Simétrica	A ^ B	A.symmetric_difference(B)	Elementos presentes em $A$ ou $B$, mas não em ambos.
Subconjunto	A <= B	A.issubset(B)	Verifica se todo elemento de $A$ pertence a $B$.
Superconjunto	A >= B	A.issuperset(B)	Verifica se $A$ contém todos os elementos de $B$.

permissoes_admin: set[str] = {"read", "write", "delete", "audit"}
permissoes_usuario: set[str] = {"read", "comment"}

# Verificação instantânea de privilégios em O(1):
privilegios_exclusivos = permissoes_admin - permissoes_usuario

---

📖 3. Recursos Modernos de Dicionários (PEP 584)

O Python 3.9 introduziu os operadores de mesclagem e atualização de dicionários:

• Operador de União (|): Cria um novo dicionário combinando dois mapeamentos: config = defaults | customizado.
• Operador de Atualização In-Place (|=): Atualiza o dicionário existente: sessao |= novos_dados.

Utilitários do Módulo collections

• defaultdict(factory): Inicializa chaves ausentes automaticamente via função de fábrica (ex.: defaultdict(list)), eliminando o clássico if chave not in d: d[chave] = [].
• Counter(iteravel): Tabela de frequência estatística com métodos especializados como .most_common(N).

---

🧬 4. Generics: A Revolução da PEP 695 no Python 3.12+

Antes do Python 3.12, criar uma classe ou função genérica exigia importar TypeVar e Generic do módulo typing. A PEP 695 introduziu uma sintaxe nativa na gramática da linguagem, alinhando o Python ao TypeScript, Rust e C#:

Comparativo Sintático: PEP 484 vs PEP 695 (Python 3.12+)

# SINTAXE CLÁSSICA (Legada / Python 3.5 a 3.11):
from typing import TypeVar, Generic

T = TypeVar("T")

class FilaLegada(Generic[T]):
    def enfileirar(self, item: T) -> None: ...

# SINTAXE MODERNA NATIVA (Python 3.12+ / PEP 695):
class FilaModerna[T]:
    def __init__(self) -> None:
        self._itens: list[T] = []

    def enfileirar(self, item: T) -> None:
        self._itens.append(item)

    def desenfileirar(self) -> T:
        if not self._itens:
            raise IndexError("Fila vazia.")
        return self._itens.pop(0)

# Funções Genéricas com Type Parameters Diretos:
def primeiro_elemento[T](colecao: list[T]) -> T | None:
    return colecao[0] if colecao else None

A nova sintaxe do Python 3.12 elimina a poluição de variáveis de tipo no escopo global e melhora drasticamente o desempenho de inicialização do interpretador.