Pular para o conteúdo
CodeMDD.io | Coding Tutorials

Como Usar uma Tabela Hash em Python

[

Como construir uma Tabela Hash em Python usando Test Driven Development (TDD)

Por Bartosz Zaczyński

Introdução

A tabela hash é uma estrutura de dados clássica que foi inventada há mais de meio século e continua sendo fundamental para a programação atual. Ela ajuda a resolver diversos problemas do mundo real, como indexação de tabelas de banco de dados, armazenamento em cache de valores calculados e implementação de conjuntos. Além disso, é frequentemente abordada em entrevistas de emprego, e o Python utiliza tabelas hash em diversos lugares para realizar pesquisas de nomes quase que instantaneamente.

Embora o Python já tenha uma tabela hash própria chamada dict, é útil entender como as tabelas hash funcionam nos bastidores. Em alguns casos, você pode até mesmo ser desafiado a construir uma tabela hash em um teste de programação. Neste tutorial, vamos percorrer o processo de implementação de uma tabela hash do zero, como se não existisse no Python. Ao longo do caminho, você enfrentará alguns desafios que irão introduzir conceitos importantes e dar uma ideia de por que as tabelas hash são tão rápidas.

Além disso, você terá uma experiência prática de desenvolvimento guiado por testes (TDD) e irá praticá-la ativamente enquanto constrói sua tabela hash passo a passo. Não é necessário ter experiência prévia com TDD, mas mesmo se você já tiver, não ficará entediado!

Visão Geral do Tutorial

Neste tutorial, você irá aprender:

  • Como uma tabela hash difere de um dicionário
  • Como implementar uma tabela hash do zero em Python
  • Como lidar com colisões de hash e outros desafios
  • Quais são as propriedades desejáveis de uma função de hash
  • Como a função hash() do Python funciona nos bastidores

Para começar, é útil ter familiaridade com dicionários do Python e conhecimento básico de programação orientada a objetos.

Antes de mergulharmos nos detalhes da implementação da tabela hash, vamos entender a estrutura dessa estrutura de dados em relação aos dicionários do Python.

Conhecendo a Estrutura de Dados Tabela Hash

Tabela Hash vs Dicionário

A tabela hash é uma estrutura de dados que permite armazenar e recuperar elementos usando uma função de hash para calcular o índice de um elemento em um vetor. Essa função de hash mapeia cada elemento para uma posição única no vetor, permitindo que a tabela hash seja eficiente na busca e recuperação de elementos.

O dicionário do Python, por outro lado, é uma implementação específica da tabela hash que utiliza o conceito de chave-valor. Ele permite que você associe um valor a uma chave, fornecendo uma maneira rápida e eficiente de recuperar o valor associado a uma determinada chave.

Então, podemos dizer que um dicionário do Python é uma tabela hash especializada em associação de chaves e valores.

Tabela Hash: Um Array com uma Função de Hash

Para criar uma tabela hash, primeiro você precisa de um vetor de tamanho fixo (também chamado de matriz) para armazenar os elementos. Cada elemento é inserido em uma posição do vetor com base no resultado da função de hash aplicada a ele.

A função de hash é responsável por mapear cada elemento para uma posição única no vetor. Isso é feito calculando uma soma de verificação ou um código hash exclusivo para cada elemento. O resultado da função de hash é então usado como o índice para armazenar o elemento no vetor.

A capacidade de uma tabela hash é determinada pelo tamanho do vetor. Um vetor maior pode acomodar mais elementos, mas ao aumentar o tamanho do vetor, você também aumenta a probabilidade de colisões de hash, que ocorrem quando dois elementos diferentes são mapeados para a mesma posição do vetor.

Para lidar com colisões de hash, existem várias estratégias, como sondagem linear e encadeamento separado. Essas estratégias são usadas para resolver conflitos de hash e garantir que todos os elementos possam ser armazenados corretamente na tabela hash.

Entendendo a Função de Hash

A função de hash é uma parte fundamental de uma tabela hash. Ela é responsável por mapear elementos para posições únicas no vetor da tabela hash.

O Python possui uma função de hash embutida chamada hash(), que é aplicada automaticamente a objetos quando eles são usados como chaves de dicionário. Essa função fornece um valor hash para cada objeto, que pode ser usado como índice para armazenamento e recuperação eficientes.

Vamos examinar em detalhes como a função de hash embutida do Python funciona.

Examinando a Função hash() do Python

A função hash() do Python é aplicada automaticamente a objetos quando eles são usados como chaves de dicionário. Ela retorna um valor hash inteiro exclusivo para cada objeto.

Podemos testar o comportamento da função hash() em diferentes tipos de objetos:

print(hash(42))  # Saída: 42
print(hash([1, 2, 3]))  # Gera um TypeError

Observe que a função hash() retorna um valor hash consistente para objetos do mesmo tipo. Portanto, se chamarmos a função hash() várias vezes para o mesmo objeto, o resultado será sempre o mesmo.

Aprofundando-se na Função hash() do Python

Embora a função hash() possa fornecer valores hash únicos para a maioria dos objetos do Python, nem todos os objetos são hashable por padrão.

Por exemplo, os objetos mutáveis, como listas ou dicionários, não são hashable porque eles podem ser alterados após a criação, o que comprometeria a integridade da tabela hash. No caso de objetos mutáveis, geralmente é necessário implementar uma função de hash personalizada.

A função hash() do Python também possui um limite superior para o valor hash que pode ser retornado. Quando um objeto gera um valor hash que é maior do que o limite superior, a função hash() realiza uma operação especial conhecida como truncamento do valor hash (hash truncation). Isso significa que a função hash() retorna um valor hash menor para o objeto.

Por exemplo, se tentarmos obter o valor hash de um número grande, vamos obter o período dessa função, o que significa que o valor hash irá repetir após um certo número de iterações.

Identificando Propriedades da Função de Hash

Ao criar uma tabela hash personalizada, uma das tarefas é projetar uma função de hash adequada. Existem algumas propriedades desejáveis que uma função de hash deve atender:

  1. Uniformidade: Uma boa função de hash deve espalhar os elementos de forma uniforme por toda a tabela hash, minimizando as colisões de hash.

  2. Determinismo: A função de hash deve retornar o mesmo valor hash para um determinado objeto sempre que for chamada.

  3. Eficiência: A função de hash deve ser computacionalmente eficiente para evitar atrasos no desempenho da tabela hash.

  4. Unicidade: Cada objeto deve ter um único valor hash para evitar colisões de hash. No entanto, é aceitável que dois objetos diferentes tenham o mesmo valor hash (colisão), desde que essa colisão seja resolvida adequadamente.

  5. Compatibilidade: A função de hash deve ser compatível com a igualdade de objetos. Isso significa que se dois objetos são considerados iguais de acordo com o operador de igualdade (==), então eles devem ter o mesmo valor hash.

Comparando a Identidade do Objeto com o seu Valor Hash

Em Python, você pode verificar se dois objetos são idênticos (ou seja, referem-se exatamente ao mesmo objeto na memória) comparando seus valores de identidade com o operador is. Essa comparação é feita verificando se os endereços de memória dos objetos são os mesmos.

Por outro lado, você pode comparar se dois objetos têm o mesmo valor hash usando o operador de comparação ==. Isso compara os valores hash dos objetos, não sua identidade.

Vamos comparar os valores de identidade e os valores hash de dois objetos:

print(a is b)  # Saída: True
print(hash(a) == hash(b))  # Saída: True

Embora os objetos a e b sejam idênticos em termos de identidade, eles também têm o mesmo valor hash porque seus conteúdos são iguais.

Criando sua Própria Função de Hash

Quando você precisa criar uma tabela hash personalizada, também pode criar uma função de hash personalizada para seus objetos. Isso é útil quando você deseja armazenar objetos personalizados em uma tabela hash.

Aqui está um exemplo de como criar uma função de hash simples para uma classe personalizada:

class Pessoa:
    def __init__(self, nome, idade):
        self.nome = nome
        self.idade = idade


    def __hash__(self):
        return hash(self.nome) + hash(self.idade)


    def __eq__(self, other):
        return self.nome == other.nome and self.idade == other.idade


alice = Pessoa("Alice", 25)
bob = Pessoa("Bob", 30)


print(hash(alice))  # Saída: 8342162412792912430
print(hash(bob))  # Saída: 7702438714384476138

Neste exemplo, a função __hash__() foi definida para calcular um valor hash para o objeto Pessoa com base no nome e idade. Assim, cada objeto Pessoa terá um valor hash único de acordo com sua combinação de nome e idade.

Também foi definido o método __eq__() para verificar se duas instâncias da classe Pessoa são iguais. Isso será útil ao lidar com colisões de hash em uma tabela hash personalizada.

Construindo um Protótipo de Tabela Hash em Python com TDD

Agora que entendemos a estrutura e a função de hash de uma tabela hash, podemos começar a implementar um protótipo de tabela hash em Python usando a técnica de desenvolvimento guiado por testes (TDD, na sigla em inglês).

O TDD é uma abordagem de desenvolvimento focada em escrever testes automatizados antes de escrever o código de produção. Isso ajuda a garantir que o código seja testável, que cada funcionalidade específica seja implementada corretamente e que todas as partes do código estejam integradas corretamente.

Vamos começar com um curso intensivo sobre TDD e, em seguida, passaremos para a implementação da classe HashTable (Tabela Hash).

Fazendo um Curso Intensivo sobre Desenvolvimento Guiado por Testes

O desenvolvimento guiado por testes (TDD) é uma técnica que envolve a criação de testes automatizados antes de escrever o código de produção. Essa abordagem ajuda a garantir que o código seja testado com antecedência e que todas as funcionalidades estejam corretas desde o início.

Existem três etapas principais no ciclo de desenvolvimento guiado por testes:

  1. Red: Escreva um teste automatizado que descreva o comportamento desejado da funcionalidade que você está implementando. O teste deve falhar no início, pois a funcionalidade ainda não foi implementada.

  2. Green: Escreva o código de produção mínimo necessário para fazer com que o teste passe. Não se preocupe em escrever código perfeito neste momento. O objetivo é fazer com que o código seja funcional e passe no teste.

  3. Refactor: Refatore o código de produção e o teste de forma a melhorar a qualidade, a legibilidade e a eficiência do código. Certifique-se de que os testes ainda passem após o refatoramento.

O ciclo Red-Green-Refactor é repetido várias vezes durante o processo de desenvolvimento guiado por testes. Isso ajuda a garantir uma alta qualidade de código e a reduzir a incidência de erros.

Agora que você tem uma ideia geral do que é o desenvolvimento guiado por testes, vamos aplicar essa técnica ao protótipo da tabela hash.

Definindo uma Classe Customizada HashTable

class HashTable:
    def __init__(self):
        self.size = 10
        self.data = [[] for _ in range(self.size)]


    def insert(self, key, value):
        pass


    def find(self, key):
        pass


    def delete(self, key):
        pass


    def update(self, key, value):
        pass


    def get_all(self):
        pass

Começaremos criando uma classe HashTable básica que conterá metódos para inserir, encontrar, deletar, atualizar e obter todos os elementos da tabela hash.

A tabela hash será inicializada com um tamanho fixo de 10, representado por uma matriz vazia chamada data.

Inserindo um Par Chave-Valor

Vamos escrever o primeiro teste para inserir um par chave-valor na tabela hash:

def test_insert():
    hash_table = HashTable()
    hash_table.insert("chave", "valor")


    assert hash_table.find("chave") == "valor"

Este teste verifica se a inserção de um par chave-valor na tabela hash foi bem-sucedida e se o valor pode ser recuperado corretamente usando a função find().

Agora, podemos implementar o método de inserção na classe HashTable:

def insert(self, key, value):
    index = self._hash_function(key)
    self.data[index].append((key, value))

A implementação do método de inserção simplesmente calcula o índice da posição do vetor usando uma função de hash interna chamada _hash_function(), que ainda precisa ser implementada. Em seguida, ela adiciona o par chave-valor fornecido no índice correto.

Encontrando um Valor pela Chave

Vamos escrever um teste para recuperar um valor da tabela hash usando uma chave:

def test_find():
    hash_table = HashTable()
    hash_table.insert("chave", "valor")


    assert hash_table.find("chave") == "valor"
    assert hash_table.find("outra chave") is None

Este teste verifica se é possível encontrar o valor associado a uma chave específica e se um valor não associado a uma chave é retornado como None.

Em seguida, podemos implementar o método find() na classe HashTable:

def find(self, key):
    index = self._hash_function(key)
    for k, v in self.data[index]:
        if k == key:
            return v
    return None

A implementação do método find() calcula o índice correspondente usando a função _hash_function() e, em seguida, procura o valor associado à chave no índice correto. Se a chave não for encontrada, o método retorna None.

Deletando um Par Chave-Valor

Vamos escrever um teste para deletar um par chave-valor da tabela hash:

def test_delete():
    hash_table = HashTable()
    hash_table.insert("chave", "valor")
    hash_table.insert("outra chave", "outro valor")
    hash_table.delete("chave")


    assert hash_table.find("chave") is None
    assert hash_table.find("outra chave") == "outro valor"

Este teste verifica se a exclusão de um par chave-valor da tabela hash foi bem-sucedida e se a chave é removida corretamente da tabela.

Agora, podemos implementar o método delete() na classe HashTable:

def delete(self, key):
    index = self._hash_function(key)
    self.data[index] = [(k, v) for k, v in self.data[index] if k != key]

A implementação do método delete() calcula o índice correspondente usando a função _hash_function() e, em seguida, percorre os elementos no índice correto verificando se a chave corresponde à chave fornecida. Se a chave não corresponder, o elemento é mantido; caso contrário, ele é removido.

Atualizando o Valor de um Par Chave-Valor Existente

Vamos escrever um teste para atualizar o valor de um par chave-valor existente na tabela hash:

def test_update():
    hash_table = HashTable()
    hash_table.insert("chave", "valor")
    hash_table.update("chave", "novo valor")


    assert hash_table.find("chave") == "novo valor"
    assert hash_table.find("outra chave") is None

Este teste verifica se a atualização do valor de um par chave-valor existente na tabela hash foi bem-sucedida e se a chave não existente retorna None.

Em seguida, podemos implementar o método update() na classe HashTable:

def update(self, key, value):
    index = self._hash_function(key)
    for i, (k, v) in enumerate(self.data[index]):
        if k == key:
            self.data[index][i] = (key, value)
            return

A implementação do método update() calcula o índice correspondente usando a função _hash_function() e, em seguida, percorre os elementos dentro do índice procurando por uma chave correspondente. Se a chave for encontrada, o valor é atualizado; caso contrário, nada acontece.

Obtendo Todos os Pares Chave-Valor

Vamos escrever um teste para recuperar todos os pares chave-valor da tabela hash:

def test_get_all():
    hash_table = HashTable()
    hash_table.insert("chave1", "valor1")
    hash_table.insert("chave2", "valor2")
    hash_table.insert("chave3", "valor3")


    all_items = hash_table.get_all()
    assert len(all_items) == 3
    assert ("chave1", "valor1") in all_items
    assert ("chave2", "valor2") in all_items
    assert ("chave3", "valor3") in all_items

Este teste verifica se todos os elementos da tabela hash podem ser recuperados corretamente usando o método get_all().

Agora, podemos implementar o método get_all() na classe HashTable:

def get_all(self):
    return [item for sublist in self.data for item in sublist]

A implementação do método get_all() simplesmente retorna uma lista plana de todos os elementos da tabela hash.

Usando Cópia Defensiva

Usar cópia defensiva é uma prática recomendada ao lidar com estruturas de dados mutáveis, como listas, em tabelas hash. Isso evita que as alterações feitas por referência nos valores armazenados na tabela hash afetem a integridade dos dados.

Vamos escrever um teste para verificar se a cópia defensiva está sendo usada nos valores retornados:

def test_defensive_copy():
    hash_table = HashTable()
    hash_table.insert("chave", [1, 2, 3])
    values = hash_table.get_all()


    values[0][0] = 42


    assert hash_table.find("chave") == [1, 2, 3]

Este teste verifica se as alterações feitas por referência nos valores recuperados não afetam os valores armazenados na tabela hash.

Podemos adicionar cópia defensiva ao método get_all() na classe HashTable:

def get_all(self):
    return [list(item) for sublist in self.data for item in sublist]

A implementação do método get_all() agora retorna uma cópia da lista de elementos para garantir que as alterações feitas por referência não afetem os valores armazenados na tabela hash.

Obtendo as Chaves e Valores

Vamos escrever testes para recuperar apenas as chaves e apenas os valores da tabela hash:

def test_get_keys_values():
    hash_table = HashTable()
    hash_table.insert("chave1", "valor1")
    hash_table.insert("chave2", "valor2")
    hash_table.insert("chave3", "valor3")


    all_keys = hash_table.get_keys()
    all_values = hash_table.get_values()


    assert len(all_keys) == 3
    assert "chave1" in all_keys
    assert "chave2" in all_keys
    assert "chave3" in all_keys


    assert len(all_values) == 3
    assert "valor1" in all_values
    assert "valor2" in all_values
    assert "valor3" in all_values

Esses testes verificam se todas as chaves e valores da tabela hash podem ser recuperados corretamente usando os métodos get_keys() e get_values().

Agora, podemos implementar os métodos get_keys() e get_values() na classe HashTable:

def get_keys(self):
    return [k for sublist in self.data for k, v in sublist]


def get_values(self):
    return [v for sublist in self.data for k, v in sublist]

A implementação dos métodos get_keys() e get_values() simplesmente retorna uma lista plana de todas as chaves e valores da tabela hash.

Relatando o Comprimento da Tabela Hash

Vamos escrever um teste para verificar se o comprimento da tabela hash pode ser retornado corretamente:

def test_length():
    hash_table = HashTable()
    hash_table.insert("chave1", "valor1")
    hash_table.insert("chave2", "valor2")
    hash_table.insert("chave3", "valor3")


    assert len(hash_table) == 3

Este teste verifica se o comprimento da tabela hash é igual ao número de elementos inseridos.

Em seguida, podemos adicionar a implementação do método __len__() na classe HashTable:

def __len__(self):
    count = 0
    for sublist in self.data:
        count += len(sublist)
    return count

A implementação do método __len__() percorre todos os elementos nas sublistas da tabela hash e conta quantos elementos existem no total.

Tornando a Tabela Hash Iterável

Vamos escrever um teste para verificar se a tabela hash pode ser iterada corretamente:

def test_iteration():
    hash_table = HashTable()
    hash_table.insert("chave1", "valor1")
    hash_table.insert("chave2", "valor2")
    hash_table.insert("chave3", "valor3")


    all_items = [item for item in hash_table]


    assert len(all_items) == 3
    assert ("chave1", "valor1") in all_items
    assert ("chave2", "valor2") in all_items
    assert ("chave3", "valor3") in all_items

Este teste verifica se todos os elementos da tabela hash podem ser iterados corretamente.

Podemos adicionar a implementação do método __iter__() na classe HashTable:

def __iter__(self):
    return iter(self.get_all())

A implementação do método __iter__() simplesmente retorna um iterador a partir dos elementos da tabela hash.

Representando a Tabela Hash em Texto

Vamos escrever um teste para verificar se a tabela hash pode ser representada corretamente como uma string:

def test_representation():
    hash_table = HashTable()
    hash_table.insert("chave1", "valor1")
    hash_table.insert("chave2", "valor2")
    hash_table.insert("chave3", "valor3")


    representation = str(hash_table)


    assert "chave1: valor1" in representation
    assert "chave2: valor2" in representation
    assert "chave3: valor3" in representation

Este teste verifica se a representação da tabela hash como uma string contém todas as chaves e valores corretos.

Podemos adicionar a implementação do método __str__() na classe HashTable:

def __str__(self):
    return "\n".join([f"{k}: {v}" for sublist in self.data for k, v in sublist])

A implementação do método __str__() retorna uma string que contém a chave e o valor de cada elemento da tabela hash formatados corretamente.

Testando a Igualdade de Tabelas Hash

Vamos escrever um teste para verificar se a igualdade entre tabelas hash pode ser verificada corretamente:

def test_equality():
    hash_table1 = HashTable()
    hash_table1.insert("chave1", "valor1")
    hash_table1.insert("chave2", "valor2")


    hash_table2 = HashTable()
    hash_table2.insert("chave2", "valor2")
    hash_table2.insert("chave1", "valor1")


    hash_table3 = HashTable()
    hash_table3.insert("chave1", "valor1")
    hash_table3.insert("chave3", "valor3")


    assert hash_table1 == hash_table2
    assert hash_table1 != hash_table3

Este teste verifica se a igualdade entre tabelas hash pode ser verificada corretamente. Duas tabelas hash são consideradas iguais apenas se tiverem as mesmas chaves e valores, independentemente da ordem em que foram inseridas.

Podemos adicionar a implementação do método __eq__() na classe HashTable:

def __eq__(self, other):
    return self.data == other.data

A implementação do método __eq__() compara as listas internas data das tabelas hash para verificar se são iguais.

Resolvendo Colisões de Código Hash

Até agora, nossa implementação da tabela hash é bastante básica e pode causar colisões de código hash, que ocorrem quando dois elementos diferentes são mapeados para a mesma posição do vetor.

Vamos explorar duas estratégias para resolver colisões de código hash: sondagem linear e encadeamento separado.

Encontrando Chaves Colididas por Sondagem Linear

Vamos escrever um teste para verificar se é possível encontrar chaves colididas usando a sondagem linear:

def test_linear_probing():
    hash_table = HashTable()
    hash_table.insert("chave1", "valor1")
    hash_table.insert("chave2", "valor2")
    hash_table.insert("chave3", "valor3")
    hash_table.insert("chave4", "valor4")


    assert hash_table.find("chave1") == "valor1"
    assert hash_table.find("chave2") == "valor2"
    assert hash_table.find("chave3") == "valor3"
    assert hash_table.find("chave4") == "valor4"

Este teste verifica se é possível encontrar chaves colididas usando a técnica de sondagem linear.

Podemos adicionar a implementação da sondagem linear na função _hash_function() da classe HashTable:

def _hash_function(self, key):
    index = hash(key) % self.size
    while self.data[index] and self.data[index][0] != key:
        index = (index + 1) % self.size
    return index

A implementação da sondagem linear é feita dentro da função _hash_function(). Ela continua verificando a próxima posição do vetor até encontrar um espaço vazio ou uma chave que corresponda à chave fornecida. Quando uma posição vazia é encontrada, a função retorna essa posição. Quando uma chave correspondente é encontrada, a função retorna a posição dessa chave. Isso garante que as colisões de hash sejam resolvidas usando a técnica de sondagem linear.

Redimensionando Automaticamente a Tabela Hash

Vamos escrever um teste para verificar se a tabela hash é redimensionada automaticamente quando necessário:

def test_resize():
    hash_table = HashTable()
    hash_table.insert("chave1", "valor1")
    hash_table.insert("chave2", "valor2")
    hash_table.insert("chave3", "valor3")
    hash_table.insert("chave4", "valor4")
    hash_table.insert("chave5", "valor5")
    hash_table.insert("chave6", "valor6")
    hash_table.insert("chave7", "valor7")


    assert hash_table.size == 20
    assert len(hash_table) == 7

Este teste verifica se a tabela hash é redimensionada automaticamente quando a carga (load factor) excede um limite. Neste caso, a tabela hash é redimensionada para um tamanho maior.

Podemos adicionar a funcionalidade de redimensionamento automático na função _hash_function() da classe HashTable:

def _hash_function(self, key):
    index = hash(key) % self.size
    while self.data[index] and self.data[index][0] != key:
        index = (index + 1) % self.size
    if len(self) >= self.size * 0.7:  # Redimensiona a tabela hash quando a carga (load factor) excede 70%
        self._resize()
    return index


def _resize(self):
    self.size = self.size * 2
    new_data = [[] for _ in range(self.size)]
    for sublist in self.data:
        for k, v in sublist:
            index = hash(k) % self.size
            new_data[index].append((k, v))
    self.data = new_data

A função _hash_function() agora verifica se a contagem de elementos na tabela hash excede 70% do tamanho atual. Se isso acontecer, a função _resize() é chamada para redimensionar a tabela hash para um tamanho maior. A função _resize() duplica o tamanho da tabela hash e redistribui os elementos existentes para as novas posições do vetor.

Isolando Chaves Colididas com Encadeamento Separado

Vamos escrever um teste para verificar se é possível isolar chaves colididas usando o encadeamento separado (separate chaining):

def test_separate_chaining():
    hash_table = HashTable()
    hash_table.insert("chave1", "valor1")
    hash_table.insert("chave2", "valor2")
    hash_table.insert("chave3", "valor3")
    hash_table.insert("chave4", "valor4")
    hash_table.insert("chave5", "valor5")
    hash_table.insert("chave6", "valor6")
    hash_table.insert("chave7", "valor7")


    assert hash_table.find("chave1") == "valor1"
    assert hash_table.find("chave2") == "valor2"
    assert hash_table.find("chave3") == "valor3"
    assert hash_table.find("chave4") == "valor4"
    assert hash_table.find("chave5") == "valor5"
    assert hash_table.find("chave6") == "valor6"
    assert hash_table.find("chave7") == "valor7"

Este teste verifica se é possível isolar chaves colididas usando a técnica de encadeamento separado.

Podemos adicionar a implementação do encadeamento separado na função _hash_function() da classe HashTable:

def _hash_function(self, key):
    index = hash(key) % self.size
    while self.data[index] and self.data[index][0] != key:
        index = (index + 1) % self.size
    return index


def insert(self, key, value):
    index = self._hash_function(key)
    self.data[index].append((key, value))

Neste caso, não há alterações na função _hash_function(), mas a função insert() na classe HashTable foi atualizada para adicionar o novo par chave-valor à posição do vetor correspondente, mesmo se houver outros pares chave-valor já presentes.

Mantendo a Ordem de Inserção em uma Tabela Hash

Até agora, a tabela hash que construímos não mantém a ordem de inserção dos elementos. Vamos adicionar essa funcionalidade usando um dicionário Python interno para rastrear a ordem de inserção.

Vamos escrever um teste para verificar se a ordem de inserção é mantida corretamente:

def test_insertion_order():
    hash_table = HashTable()
    hash_table.insert("chave1", "valor1")
    hash_table.insert("chave2", "valor2")
    hash_table.insert("chave3", "valor3")


    assert list(hash_table.get_keys()) == ["chave1", "chave2", "chave3"]
    assert list(hash_table.get_values()) == ["valor1", "valor2", "valor3"]
    assert list(hash_table.get_all()) == [("chave1", "valor1"), ("chave2", "valor2"), ("chave3", "valor3")]

Este teste verifica se a ordem de inserção dos elementos é mantida corretamente na tabela hash.

Podemos adicionar a funcionalidade de manter a ordem de inserção na classe HashTable:

from collections import OrderedDict


class HashTable:
    def __init__(self):
        self.size = 10
        self.data = [[] for _ in range(self.size)]
        self.order_dict = OrderedDict()


    def _hash_function(self, key):
        index = hash(key) % self.size
        while self.data[index] and self.data[index][0] != key:
            index = (index + 1) % self.size
        return index


    def insert(self, key, value):
        index = self._hash_function(key)
        self.data[index].append((key, value))
        self.order_dict[key] = value


    def get_keys(self):
        return self.order_dict.keys()


    def get_values(self):
        return self.order_dict.values()


    def get_all(self):
        return self.order_dict.items()

A nova implementação inclui um dicionário Python interno chamado order_dict que é usado para rastrear a ordem de inserção dos elementos. O dicionário order_dict é atualizado a cada inserção, garantindo que a ordem de inserção seja mantida ao recuperar as chaves, os valores ou todos os elementos da tabela hash.

Usando Chaves Hasháveis

Uma tabela hash só pode ser usada com chaves hasháveis. Objetos que são hasháveis são aqueles cuja implementação da função __hash__() retorna um valor hash exclusivo e são imutáveis.

Vamos escrever um teste para verificar se somente chaves hasháveis podem ser usadas na tabela hash:

def test_hashable_keys():
    hash_table = HashTable()
    hash_table.insert(42, "valor")
    hash_table.insert("chave", "valor")


    assert hash_table.find(42) == "valor"
    assert hash_table.find("chave") == "valor"

Este teste verifica se a tabela hash pode ser usada com chaves hasháveis de diferentes tipos.

Atualmente, a implementação da nossa tabela hash aceita qualquer tipo de chave, mas não garante que a chave seja hashável. Vamos adicionar a verificação da hashabilidade da chave na função _hash_function():

def _hash_function(self, key):
    if not isinstance(key, Hashable):
        raise TypeError("Chaves não hasháveis não são permitidas")
    index = hash(key) % self.size
    while self.data[index] and self.data[index][0] != key:
        index = (index + 1) % self.size
    return index

A nova implementação verifica se a chave fornecida é do tipo hashável usando a função isinstance() e depois lança um TypeError se a chave não for hashável.

Conclusão

Neste tutorial, você aprendeu como construir uma tabela hash do zero usando Python e o conceito de desenvolvimento guiado por testes (TDD). Começamos entendendo a estrutura e a função de hash da tabela hash e, em seguida, passamos pela implementação passo a passo de todas as funcionalidades principais de uma tabela hash, incluindo inserção, recuperação, exclusão, atualização, obtenção dos elementos e redimensionamento automático da tabela hash. Também lidamos com desafios, como colisões de hash, usando sondagem linear e encadeamento separado.

Ao longo do processo, você praticou TDD, escrevendo testes automatizados antes de implementar o código de produção. Isso ajudou você a manter um alto nível de qualidade de código e a garantir que suas funcionalidades estejam corretas.

A tabela hash é uma estrutura de dados poderosa e versátil que desempenha um papel fundamental em muitas aplicações de programação. Agora que você entende como ela funciona em um nível mais profundo, você pode aproveitar ao máximo essa estrutura de dados e aplicá-la em seus próprios projetos.

Continue praticando o desenvolvimento guiado por testes e explorando outras estruturas de dados para expandir seu conhecimento e habilidades em Python!