Dicionários (dict) e conjuntos (set) em Python são estruturas de dados fundamentais, valorizadas por sua eficiência e comportamento único. Este artigo explora os mecanismos internos que os tornam tão potentes, abordando questões como sua alta performance, a natureza de sua ordenação (ou falta dela), os requisitos para que objetos sejam utilizados como chaves ou elementos, a dependência da ordem de inserção e por que é desaconselhável modificar essas estruturas durante a iteração.

Alta Eficiência de Dicionários e Conjuntos em Python

Independentemente do número de elementos que um dicionário ou conjunto contém, as operações de busca, inserção e remoção tendem a ser extremamente rápidas, com um tempo de execução médio constante (O(1)), desde que a estrutura caiba na memória disponível. Essa performance notável é atribuída à sua implementação subjacente: tabelas hash.

Tabelas Hash em Dicionários

Uma tabela hash pode ser conceituada como um array esparso, ou seja, um array que geralmente possui muitos "espaços" vazios. Em Python, cada par chave-valor em um dicionário ocupa uma posição específica na tabela hash, denominada bucket ou célula. Cada bucket armazena referências para a chave e para o valor correspondente.

A homogeneidade no tamanho dos buckets permite que o acesso a qualquer um deles seja feito diretamente por um deslocamento. Para manter a eficiência, o interpretador Python se esforça para que aproximadamente um terço dos buckets permaneça vazio. Se essa proporção for ameaçada, a tabela hash existente é redimensionada e copiada para uma nova área de memória maior.

Para adicionar um objeto a uma tabela hash, o primeiro passo é calcular o seu valor de hash. Em Python, isso é feito através da função embutida hash().

Valores de Hash e Igualdade

A função hash() pode ser aplicada a todos os tipos de objetos imutáveis embutidos. Para objetos personalizados, a função chama o método mágico __hash__() da classe. Uma regra crucial para o funcionamento correto das tabelas hash é que, se dois objetos forem considerados iguais (a == b retorna True), seus valores de hash também devem ser iguais (hash(a) == hash(b)).

Por exemplo, embora 1 (inteiro) e 1.0 (float) tenham representações internas distintas, a expressão 1 == 1.0 é verdadeira, e, portanto, hash(1) deve ser igual a hash(1.0).

Detalhes de implementação do CPython revelam que, para objetos inteiros que se ajustam a uma palavra de máquina, o valor de hash é o próprio valor do inteiro. Para que os valores de hash sejam eficazes como índices de tabela, eles devem ser distribuídos uniformemente no espaço de índices. Idealmente, objetos semelhantes, mas não iguais, deveriam produzir hashes com diferenças significativas.

Para ilustrar a diferença entre hashes de objetos numericamente próximos, considere o seguinte exemplo:

import sys

# Determina o número máximo de bits para um inteiro do sistema
MAX_BITS = len(format(sys.maxsize, 'b'))

def comparar_hashes(obj1, obj2):
    """
    Calcula e compara os valores de hash binários de dois objetos,
    destacando as diferenças entre eles.
    """
    hash_obj1_bin = f"{hash(obj1):>0{MAX_BITS}b}"
    hash_obj2_bin = f"{hash(obj2):>0{MAX_BITS}b}"

    # Identifica as posições onde os bits são diferentes
    diferencas = ''.join('!' if b1 != b2 else ' ' for b1, b2 in zip(hash_obj1_bin, hash_obj2_bin))
    contagem_diferencas = f'Total de Diferenças: {diferencas.count("!")}'

    # Formata a saída para melhor legibilidade
    largura_cabecalho = max(len(repr(obj1)), len(repr(obj2)), 10)
    separador = '_' * (largura_cabecalho * 2 + MAX_BITS)

    return (
        f"Objeto 1: {repr(obj1):<{largura_cabecalho}} {hash_obj1_bin}\n"
        f"{' ':<{largura_cabecalho}} {diferencas} {contagem_diferencas}\n"
        f"Objeto 2: {repr(obj2):<{largura_cabecalho}} {hash_obj2_bin}\n"
        f"{separador}"
    )

print(comparar_hashes(1, 1.0))
print(comparar_hashes(1.0, 1.0001))
print(comparar_hashes(1.0001, 1.0002))
print(comparar_hashes(1.0002, 1.0003))

A partir do Python 3.3, os valores de hash para objetos dos tipos str, bytes e datetime incorporam um "sal" aleatório. Este sal é uma constante dentro de uma única execução do interpretador Python, mas é gerado de forma diferente a cada inicialização. Essa medida de segurança visa prevenir ataques de negação de serviço (DoS) que poderiam explorar colisões de hash previsíveis.

Algoritmo de Tabela Hash para Busca

Para recuperar o valor associado a uma chave (ex: meu_dicionario[chave_busca]), Python executa os seguintes passos:

1. Primeiro, calcula-se o valor de hash de chave_busca usando hash(chave_busca).
2. As partes menos significativas desse hash são usadas como um índice para localizar um bucket inicial na tabela hash.
3. Se o bucket estiver vazio, a chave não existe no dicionário, e uma exceção KeyError é levantada.
4. Se o bucket não estiver vazio, ele contém um par chave_encontrada:valor_encontrado. Python verifica se chave_busca == chave_encontrada. Se for True, valor_encontrado é retornado.
5. Se chave_busca e chave_encontrada não corresponderem, ocorre uma colisão de hash. Isso acontece porque o algoritmo mapeia uma vasta gama de valores de hash para um número limitado de índices. Para resolver a colisão, o algoritmo usa outras partes do valor de hash ou um método de sondagem para encontrar um próximo bucket potencial.
6. O processo se repete a partir do passo 3 (verificando o novo bucket) até que a chave seja encontrada, um bucket vazio seja atingido (indicando que a chave não existe), ou o limite de sondagens seja excedido.

A adição de novos elementos ou a atualização de chaves existentes segue um processo similar. Ao encontrar um bucket vazio durante uma inserção, o novo elemento é colocado lá. Na atualização, o valor existente no bucket é substituído. Durante a inserção, se a tabela hash estiver muito cheia, uma realocação de memória e um redimensionamento podem ocorrer, o que pode alterar a distribuição dos hashes e, consequentemente, a localização dos elementos.

Embora esse algoritmo possa parecer complexo, na prática, mesmo em dicionários com milhões de elementos, a maioria das buscas ocorre sem colisões ou com apenas uma ou duas. A eficiência média é mantida devido à boa distribuição dos hashes.

Consequências da Implementação de Dicionários

1. Chaves Devem Ser "Hashable" (Hasháveis)

Para ser usada como chave em um dict (ou elemento em um set), um objeto deve atender a três requisitos:

1. Deve possuir um valor de hash que possa ser obtido através da função hash() e que permaneça constante durante toda a sua vida (ou seja, __hash__() deve retornar o mesmo valor se o objeto não for alterado).
2. Deve suportar teste de igualdade via método __eq__().
3. Se a == b for verdadeiro, então hash(a) == hash(b) também deve ser verdadeiro.

Por padrão, todos os objetos definidos pelo usuário são hasháveis, pois seus hashes são baseados em seu id() (endereço de memória) e, por padrão, cada instância é única (não igual a outras). Se você implementar um método __eq__() em sua classe e quiser que as instâncias sejam hasháveis, você deve também fornecer um __hash__() apropriado para garantir que a condição a == b implica hash(a) == hash(b) seja mantida. A falha em fazer isso pode levar a um comportamento imprevisível e quebrar completamente a funcionalidade do dicionário ou conjunto.

Por outro lado, se uma classe com um __eq__ personalizado for mutável, é melhor não implementar __hash__, tornando suas instâncias inaptas para serem chaves de dicionário, pois a mutabilidade do objeto implicaria que seu hash poderia mudar, o que é proibido.

Veja um exemplo de como uma implementação inconsistente de __hash__ pode causar problemas:

class ObjetoInconsistente:
    def __init__(self, valor):
        self.valor = valor

    def __hash__(self):
        # Implementação de hash que sempre retorna o mesmo valor para todas as instâncias
        return 42 # Um valor de hash fixo e arbitrário

    def __eq__(self, outro):
        # A igualdade é baseada no atributo 'valor'
        if not isinstance(outro, ObjetoInconsistente):
            return NotImplemented
        return self.valor == outro.valor

    def __repr__(self):
        return f"Obj({self.valor})"

# Criamos objetos que são diferentes, mas têm o mesmo hash e podem ser iguais dependendo do valor
obj_a = ObjetoInconsistente(1)
obj_b = ObjetoInconsistente(2)
obj_c = ObjetoInconsistente(1) # Este é igual a obj_a pelo seu valor

# Tentativa de adicionar em um dicionário
dicionario_problematico = {}
dicionario_problematico[obj_a] = "Primeiro"
dicionario_problematico[obj_b] = "Segundo"
dicionario_problematico[obj_c] = "Terceiro" # obj_c tem o mesmo valor de 'valor' que obj_a

print(f"Dicionário: {dicionario_problematico}")
print(f"Número de elementos: {len(dicionario_problematico)}")
# O resultado esperado é {'Obj(1)': 'Terceiro', 'Obj(2)': 'Segundo'}.
# obj_a e obj_c, apesar de instâncias diferentes, colidem no hash (ambos 42)
# e, por terem o mesmo 'valor', são considerados iguais por __eq__.
# Assim, obj_c sobrescreve o valor de obj_a. Se __hash__ não fosse fixo,
# obj_a e obj_c, por serem instâncias distintas, teriam hashes diferentes
# (baseados em seus IDs de memória padrão) e seriam chaves separadas.

Neste exemplo, ObjetoInconsistente(1) e ObjetoInconsistente(2) são tratados como chaves distintas, mas obj_a e obj_c, que são instâncias diferentes mas com o mesmo valor (e ambos têm o mesmo hash fixo de 42), colidem. O método __eq__ os considera iguais, então obj_c sobrescreve o valor associado a obj_a, mesmo sendo instâncias diferentes. Se o hash fosse baseado em id(self) como o padrão, obj_a e obj_c seriam tratados como chaves distintas.

2. Alto Consumo de Memória

Devido à natureza esparsa das tabelas hash, os dicionários consomem uma quantidade considerável de memória. Se você precisa armazenar um grande volume de registros, usar uma lista de tuplas ou namedtuples pode ser uma opção mais eficiente em termos de espaço do que uma lista de dicionários. A economia de memória ocorre por duas razões: a ausência da sobrecarga da tabela hash e a não necessidade de armazenar os nomes dos campos em cada elemento, como seria o caso em dicionários.

Em tipos personalizados, o atributo especial __slots__ pode ser utilizado para otimizar o armazenamento de atributos de instância, alterando-o de um dicionário para uma estruutra mais compacta baseada em tuplas.

3. Busca de Chave Rápida

A implementação dos dicts ilustra um clássico trade-off entre espaço e tempo: a custo de um maior consumo de memória, os dicionários oferecem acesso extremamente rápido a seus elementos, independentemente do tamanho da estrutura (desde que ela se ajuste à memória principal).

4. Ordem de Chaves Pela Ordem de Inserção

A partir do Python 3.7 (e por característica de implementação desde o CPython 3.6), a ordem das chaves em um dicionário é garantida como a ordem de inserção. No entanto, é importante entender que operações internas, como redimensionamento da tabela hash, podem potencialmente realocar os elementos. Apesar disso, a ordem observável para o usuário é mantida.

Considere o exemplo a seguir, onde dicionários são criados a partir dos mesmos dados, mas com ordens de inserção variadas. Embora a ordem das chaves seja garantida pela inserção, os dicionários ainda são considerados iguais se contiverem os mesmos pares chave-valor, independentemente da ordem interna de seus elementos quando comparados:

AVENTUREIROS = [
    (89, 'Monkey D. Luffy'),
    (79, 'Roronoa Zoro'),
    (69, 'Nami'),
    (59, 'Usopp'),
    (49, 'Sanji')
]

# Dicionário 1: Ordem original de inserção
dicionario1 = dict(AVENTUREIROS)
print('dicionario1 chaves:', list(dicionario1.keys()))

# Dicionário 2: Ordem por ID (chave numérica)
# Note que, se a ordem dos dados de entrada já está ordenada,
# a ordem de inserção no dicionário refletirá isso.
dicionario2 = dict(sorted(AVENTUREIROS))
print('dicionario2 chaves:', list(dicionario2.keys()))

# Dicionário 3: Ordem alfabética por nome (valor da tupla)
dicionario3 = dict(sorted(AVENTUREIROS, key=lambda x: x[1]))
print('dicionario3 chaves:', list(dicionario3.keys()))

# Apesar das ordens de criação e das chaves serem apresentadas em ordens diferentes
# devido ao sorted(), os dicionários são logicamente iguais em conteúdo.
assert dicionario1 == dicionario2 and dicionario2 == dicionario3

5. Adicionar Novas Chaves Pode Alterar a Ordem das Chaves Existentes (Internamente)

Sempre que uma nova chave é adicionada a um dicionário, o interpretador Python pode decidir redimensionar o dicionário. Esse processo envolve a criação de uma nova e maior tabela hash e a reinserção de todos os elementos existentes nela. Durante essa reinserção, novas colisões de hash podem ocorrer, potencialmente alterando a ordem interna na qual os elementos são armazenados na nova tabela. Embora a ordem de inserção seja mantida como garantia para o usuário a partir do Python 3.7, é crucial entender que a reorganização interna ainda ocorre.

Portanto, é fortemente desaconselhável modificar um dicionário (adicionar ou remover chaves) enquanto se está iterando sobre ele. Essa prática pode levar a chaves sendo ignoradas ou a um comportamento imprevisível. A abordagem recomendada é realizar essas operações em duas etapas: primeiro, iterar para identificar as modificações necessárias e armazená-las (por exemplo, em um novo dicionário ou lista de chaves a serem removidas); em seguida, aplicar essas modificações ao dicionário original após a iteração. Em Python 3, os métodos .keys(), .items() e .values() retornam "visualizações" (views) que se comportam de forma semelhante a conjuntos, refletindo o estado atual do dicionário.

Implementação e Consequências dos Conjuntos (Set)

A implementação de set e frozenset também se baseia em tabelas hash, mas, diferentemente dos dicionários, elas armazenam apenas referências aos elementos, sem os valores associados. Antes da introdução dos sets em Python, era comum usar dicionários com valores fictícios para simular conjuntos.

As consequências da implementação de conjuntos são análogas às dos dicionários:

1. Os elementos de um conjunto devem ser hasháveis.
2. Conjuntos têm um alto consumo de memória devido à sua natureza esparsa.
3. A verifiacção de existência de um elemento em um conjunto é extremamente eficiente (tempo médio O(1)).
4. A ordem dos elementos em um conjunto depende da ordem em que foram adicionados (a partir do Python 3.7).
5. Adicionar ou remover elementos pode, internamente, reorganizar os elementos existentes no conjunto devido a operações de redimensionamento da tabela hash subjacente.