Como usar Hash Table em Python
[
Construa uma Tabela Hash em Python com TDD
por Bartosz Zaczyński (estrutura de dados, intermediário)
Introdução
Inventada há mais de meio século, a tabela hash é uma estrutura de dados clássica que tem sido fundamental para a programação. Até hoje, ela ajuda a resolver muitos problemas da vida real, como indexar tabelas de banco de dados, armazenar valores computados em cache ou implementar conjuntos. Ela é frequentemente mencionada em entrevistas de emprego e o Python usa tabelas hash em diversos lugares para tornar as pesquisas de nomes quase instantâneas.
Embora o Python já possua sua própria implementação de tabela hash chamada dict, é útil entender como as tabelas hash funcionam nos bastidores. Pode ser que você precise implementar uma tabela hash como parte de uma avaliação de programação. Este tutorial o guiará pelos passos de implementação de uma tabela hash do zero, como se não houvesse uma implementação nativa no Python. Ao longo do caminho, você enfrentará alguns desafios que introduzirão conceitos importantes e lhe darão uma ideia do porquê as tabelas hash são tão rápidas.
Além disso, você terá uma introdução prática e detalhada sobre desenvolvimento orientado a testes (TDD) e a praticará ativamente ao construir a tabela hash, seguindo passo a passo. Você não precisa ter experiência prévia com TDD, mas também não ficará entediado mesmo se já tiver.
Tópicos abordados neste tutorial
Neste tutorial, você 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 desejadas de uma função de hash
- Como a função
hash()do Python funciona nos bastidores
Para acompanhar este tutorial, é útil estar familiarizado com os dicionários do Python e ter conhecimentos básicos sobre programação orientada a objetos.
1. Conheça a estrutura de dados da tabela hash
1.1. Tabela hash vs. dicionário
Embora tenham propósitos semelhantes, uma tabela hash e um dicionário no Python têm algumas diferenças fundamentais:
- Em uma tabela hash, os elementos são armazenados em uma matriz e são acessados por meio de uma função de hash.
- Em um dicionário, os elementos são armazenados em uma tabela de dispersão, onde cada elemento é armazenado em um determinado local calculado com base em uma função de dispersão.
No Python, os dicionários (dict) são implementados usando uma estrutura de tabela hash. Portanto, eles compartilham muitos conceitos fundamentais com tabelas hash, como a utilização de funções de hash para localização eficiente de elementos.
1.2. Tabela hash: uma matriz com uma função de hash
Em sua implementação mais básica, uma tabela hash é uma matriz em que os elementos são armazenados nas posições calculadas a partir de um valor de chave. Essa posição é determinada por uma função de hash, que mapeia o valor da chave para um índice na matriz.
No Python, as tabelas hash são implementadas internamente como uma matriz de ponteiros para pares chave-valor. Cada elemento é armazenado em um determinado índice da matriz com base na saída da função de hash aplicada à chave correspondente.
2. Entenda a função de hash
Uma função de hash é uma função que mapeia um valor de entrada para um valor hash, que é um número inteiro. No contexto das tabelas hash, a função de hash é usada para calcular o índice onde um elemento será armazenado na matriz.
2.1. Examine a função de hash incorporada do Python
No Python, você pode obter o valor hash de um objeto usando a função hash(). Essa função retorna um número inteiro que representa o valor hash de um objeto específico.
Por exemplo, você pode obter o valor hash de uma string da seguinte maneira:
hash_value = hash("python")2.2. Se aprofunde na função de hash do Python
Por trás dos panos, a função hash() chama uma função de hash específica para cada tipo de objeto. Essa função é fornecida pela implementação do Python para cada tipo de objeto.
A função de hash de um objeto é responsável por gerar um número inteiro (hash) com base no valor do objeto. Esse número é usado para calcular a posição do objeto na tabela hash.
2.3. Identificar as propriedades da função de hash
Uma função de hash ideal deve possuir as seguintes propriedades:
- Eficiência: a função deve ser rápida, pois é chamada frequentemente ao inserir, pesquisar e excluir elementos da tabela hash.
- Uniformidade: a função deve distribuir os elementos uniformemente na matriz subjacente da tabela hash.
- Determinismo: a função deve retornar o mesmo valor hash para o mesmo valor de entrada em diferentes momentos.
- Minimização de colisões: a função deve minimizar as colisões de hash, ou seja, diferentes valores de entrada devem gerar diferentes valores hash sempre que possível.
2.4. Comparar a identidade de um objeto com seu hash
Ao trabalhar com tabelas hash, é importante entender a diferença entre a identidade do objeto e seu valor hash. A identidade do objeto é única e não muda durante a vida útil do objeto. O valor hash de um objeto, por outro lado, é gerado pela função de hash e pode mudar ao longo do tempo.
No Python, você pode verificar se dois objetos têm a mesma identidade usando o operador is ou id():
obj1 = "python"obj2 = "python"
print(obj1 is obj2) # Trueprint(id(obj1) == id(obj2)) # TrueNo entanto, a comparação de valores hash só é útil quando você deseja verificar se dois objetos são iguais em termos de seus valores hash, mas não em termos de sua identidade. Isso pode ser feito usando o operador de igualdade (==):
obj1 = "python"obj2 = "python"
print(hash(obj1) == hash(obj2)) # True2.5. Crie sua própria função de hash
Em determinadas situações, você pode precisar criar sua própria função de hash personalizada. Esta função deve seguir as propriedades desejadas de uma função de hash ideal mencionadas anteriormente.
Uma função de hash personalizada pode ser definida como qualquer função que mapeia um valor de entrada para um valor hash. Para objetos imutáveis, essa função pode ser implementada de maneira relativamente direta. No entanto, para objetos mutáveis, você precisará tomar cuidado para garantir que a função de hash não permita que o objeto mude após o cálculo do valor hash.
3. Construa um protótipo de tabela hash em Python com TDD
Para construir uma tabela hash funcional, é importante testar cada funcionalidade individualmente. O desenvolvimento orientado a testes permite que você crie seus testes antes de implementar as funcionalidades, garantindo que as mesmas funcionem corretamente.
3.1. Faça um curso intensivo de desenvolvimento orientado a testes
Test-driven development (Desenvolvimento Orientado a Testes - TDD) é uma abordagem de desenvolvimento de software em que você escreve testes automatizados antes de implementar o código funcional. Esses testes guiam o processo de desenvolvimento e garantem que o código funcione como esperado.
Para implementar uma tabela hash, é recomendável ter uma compreensão básica de TDD e como criá-lo. Você pode aprender mais sobre TDD no curso “Write Better Python Code With Pytest”.
3.2. Defina uma classe HashTable personalizada
A primeira etapa para construir uma tabela hash é definir uma classe que será responsável por armazenar os elementos e realizar as operações essenciais, como inserção, pesquisa, exclusão e atualização de pares chave-valor.
class HashTable: def __init__(self): self.size = 10 self.keys = [None] * self.size self.values = [None] * self.sizeNa classe HashTable, inicializamos duas listas vazias, keys e values, com um tamanho inicial de 10.
3.3. Inserir um par chave-valor
Para inserir um par chave-valor na tabela hash, você precisa calcular o índice usando a função de hash e armazenar o par nas listas keys e values nos respectivos índices.
def insert(self, key, value): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: self.values[index] = value return index = self.rehash(index) self.keys[index] = key self.values[index] = valueSe o índice obtido pela função de hash já estiver ocupado, você deve lidar com a colisão de hash. Neste exemplo, usamos uma técnica chamada linear probing para encontrar o próximo índice disponível. Caso a chave já esteja presente na tabela, apenas atualizamos o valor.
3.4. Encontre um valor pela chave
Para encontrar um valor pela chave na tabela hash, basta obter o índice usando a função de hash e retornar o valor na lista values no índice correspondente.
def get(self, key): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: return self.values[index] index = self.rehash(index) return NoneSe a chave não estiver presente na tabela hash, retornamos None.
3.5. Excluir um par chave-valor
Para excluir um par chave-valor da tabela hash, você deve encontrar o índice correspondente à chave usando a função de hash e definir os elementos keys e values no índice como None.
def delete(self, key): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: self.keys[index] = None self.values[index] = None return index = self.rehash(index)3.6. Atualizar o valor de um par existente
Para atualizar o valor de um par chave-valor existente na tabela hash, você deve encontrar o índice correspondente à chave usando a função de hash e atribuir o novo valor à lista values no índice correspondente.
def update(self, key, value): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: self.values[index] = value return index = self.rehash(index)Se a chave não estiver presente na tabela hash, essa função não fará nada.
3.7. Obtenha os pares chave-valor
Para obter todos os pares chave-valor da tabela hash, você pode percorrer ambas as listas keys e values e retornar apenas os elementos que não sejam None.
def items(self): items = [] for i in range(self.size): if self.keys[i] is not None: items.append((self.keys[i], self.values[i])) return items3.8. Utilize cópia defensiva
Ao retornar os pares chave-valor, é importante utilizar uma cópia defensiva para evitar que os valores sejam alterados acidentalmente fora da tabela hash.
def items(self): items = [] for i in range(self.size): if self.keys[i] is not None: items.append((self.keys[i], self.values[i].copy())) return items3.9. Obtenha as chaves e os valores
Para obter apenas as chaves e valores da tabela hash, você pode percorrer as respectivas listas keys e values e retornar somente os elementos diferentes de None.
def keys(self): keys = [] for i in range(self.size): if self.keys[i] is not None: keys.append(self.keys[i]) return keys
def values(self): values = [] for i in range(self.size): if self.keys[i] is not None: values.append(self.values[i]) return values3.10. Consulte o tamanho da tabela hash
Para saber o tamanho atual da tabela hash, você pode percorrer a lista de chaves e contar a quantidade de elementos diferentes de None.
def length(self): count = 0 for i in range(self.size): if self.keys[i] is not None: count += 1 return count3.11. Torne a tabela hash iterável
Se você quiser utilizar a tabela hash em um laço for ou desejar verificar se um determinado elemento está presente nela, é necessário torná-la iterável. Você pode fazer isso definindo o método __iter__() na classe HashTable.
def __iter__(self): self.keys_iter = iter(self.keys) return self
def __next__(self): key = next(self.keys_iter) while key is None: key = next(self.keys_iter) return key3.12. Represente a tabela hash em texto
Para representar visualmente a tabela hash em formato de texto, você pode usar o método especial __str__().
def __str__(self): table_str = "" for i in range(self.size): if self.keys[i] is not None: table_str += f"{self.keys[i]}: {self.values[i]}\n" return table_str3.13. Teste a igualdade das tabelas hash
Ao comparar duas tabelas hash, é importante verificar se sua estrutura e elementos são iguais. Você pode fazer isso definindo o método especial __eq__().
def __eq__(self, other): if isinstance(other, HashTable) and self.size == other.size: for i in range(self.size): if self.keys[i] != other.keys[i] or self.values[i] != other.values[i]: return False return True return FalseIsso permitirá que você compare duas tabelas hash usando o operador de igualdade (==).
4. Resolva colisões de código hash
Quando você insere elementos em uma tabela hash, pode ocorrer uma colisão de código hash se dois elementos possuírem a mesma saída de função de hash. Várias estratégias de resolução de colisões são utilizadas para lidar com esse problema.
4.1. Encontre chaves colididas por linear probing
Uma maneira comum de lidar com colisões de código hash é usar o linear probing. Isso significa que, se o índice calculado para um elemento já estiver ocupado, você fará um rehashing linear para encontrar o próximo índice disponível.
def rehash(self, index): return (index + 1) % self.sizeA função rehash() retorna o próximo índice disponível calculado a partir do índice atual.
4.2. Use linear probing na classe HashTable
Agora que você já sabe como funciona o linear probing, pode utilizá-lo em sua classe HashTable.
def insert(self, key, value): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: self.values[index] = value return index = self.rehash(index) self.keys[index] = key self.values[index] = value
def get(self, key): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: return self.values[index] index = self.rehash(index) return None4.3. Permita redimensionamento automático da tabela hash
Uma tabela hash deve ser redimensionada automaticamente quando o fator de carga excede um determinado limite. O fator de carga é calculado dividindo a contagem total de elementos pelo tamanho da tabela.
def resize(self): load_factor = self.length() / self.size if load_factor >= 0.7: self.size *= 2 new_keys = [None] * self.size new_values = [None] * self.size for i in range(self.size // 2): if self.keys[i] is not None: index = self.hash_function(self.keys[i]) while new_keys[index] is not None: index = self.rehash(index) new_keys[index] = self.keys[i] new_values[index] = self.values[i] self.keys = new_keys self.values = new_valuesA função resize() é responsável por redimensionar a tabela hash sempre que o fator de carga exceder o limite definido (0,7 neste caso). Quando isso acontece, o tamanho da tabela é duplicado e todos os elementos são reorganizados nos novos arrays keys e values de acordo com a nova função de hash.
4.4. Calcule o fator de carga
Para calcular o fator de carga, você pode utilizar o método length() para contar o número de elementos presentes na tabela.
def load_factor(self): return self.length() / self.size4.5. Isolate chaves colididas com chaining separado
Uma alternativa ao linear probing é o chaining separado, onde cada slot na tabela hash é uma lista ligada. Quando ocorre uma colisão de código hash, os elementos são adicionados à lista correspondente.
class HashTable: def __init__(self): self.size = 10 self.slots = [[] for _ in range(self.size)]
def insert(self, key, value): index = self.hash_function(key) for pair in self.slots[index]: if pair[0] == key: pair[1] = value return self.slots[index].append([key, value])Na classe HashTable, substituímos as listas keys e values por uma lista de listas, chamada slots. Cada slot é uma lista que armazena pares chave-valor.
5. Mantenha a ordem de inserção em uma tabela hash
Por padrão, as tabelas hash não mantêm a ordem de inserção dos elementos. No entanto, é possível implementar uma tabela hash que preserve a ordem de inserção.
class OrderedHashTable: def __init__(self): self.size = 10 self.keys = [None] * self.size self.values = [None] * self.size self.order = []
def insert(self, key, value): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: self.values[index] = value return index = self.rehash(index) self.keys[index] = key self.values[index] = value self.order.append(index)
def items(self): items = [] for index in self.order: if self.keys[index] is not None: items.append((self.keys[index], self.values[index])) return itemsA classe OrderedHashTable é semelhante à classe HashTable, mas inclui uma lista adicional chamada order, que mantém a ordem de inserção dos elementos. O método items() percorre a lista order em vez de percorrer toda a matriz para retornar os pares chave-valor.
6. Use chaves hasháveis
Para que um objeto possa ser usado como chave em uma tabela hash, ele precisa ser hashable. Isso significa que o objeto deve ter uma função de hash definida e ser imutável.
6.1. Hashabilidade vs. imutabilidade
Uma característica importante de um objeto hashable é ser imutável. Isso significa que seus atributos não podem ser alterados após a criação do objeto. Se o objeto for mutável, a função de hash pode retornar valores diferentes para o mesmo objeto.
6.2. O contrato Hash-Equal
O Python impõe um contrato entre as funções __hash__() e __eq__() de um objeto. O objeto deve ter uma função __hash__() implementada e uma função __eq__() para verificar a igualdade entre objetos. Se dois objetos forem considerados iguais pelo método __eq__(), suas funções __hash__() também devem retornar valores iguais.
7. Conclusão
As tabelas hash são uma estrutura de dados poderosa e amplamente utilizada em muitas áreas da programação. Elas permitem pesquisas rápidas e eficientes de elementos com base em uma chave. Neste tutorial, você aprendeu como construir uma tabela hash em Python, desde entender os conceitos básicos da tabela hash até a implementação de um protótipo com testes e lidando com colisões de hash.
Implementar sua própria tabela hash pode ser uma experiência valiosa, pois permite entender como elas funcionam nos bastidores. Além disso, o desenvolvimento orientado a testes (TDD) o ajudará a criar um código mais robusto e confiável.
Agora você está equipado com o conhecimento necessário para construir e trabalhar com tabelas hash em Python. Essa habilidade será útil em muitos cenários onde a eficiência e a velocidade de pesquisa são fundamentais.
Fonte dos códigos
