Princípios de funcionamento das tabelas hash

6.1 Definição de tabela hash e sua estrutura

Tabela hash – é uma estrutura de dados que oferece a capacidade de encontrar, inserir e remover elementos rapidamente usando uma função hash para calcular índices em um array ou lista. Tabelas hash são geralmente usadas para implementar arrays associativos, também conhecidos como dicionários.

Aspectos importantes da tabela hash

Array – é o componente principal da tabela hash, ele armazena ponteiros para elementos ou listas de elementos.

Função hash: Função que transforma chaves de dicionário em índices de array.

Colisões: Situação em que duas chaves diferentes têm o mesmo valor hash. Para resolver colisões, são usados vários métodos, como encadeamento ou endereçamento aberto (open addressing).

Exemplo de dicionário:

{
   "apple": 101,
   "banana": 102,
   "cherry": 103
}

Exemplo de estrutura de tabela hash:

6.2 Operações principais na tabela hash

As operações principais na tabela hash: inserção, busca, exclusão

1. Inserção (Insertion): Processo de adicionar um novo elemento (par chave-valor) na tabela hash.

Passos da inserção:

1. Calcular o valor hash da chave usando a função hash.
2. Achar o índice no array com base no valor hash.
3. Se no array há um elemento neste índice (colisão), adicionar o elemento à lista (no caso de encadeamento) ou encontrar o próximo índice disponível (no caso de endereçamento aberto).

Exemplo de inserção na tabela hash usando encadeamento:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

# Exemplo de uso:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)

2. Busca (Search): Processo de encontrar o valor por uma chave dada na tabela hash.

Passos da busca:

1. Calcular o valor hash da chave usando a função hash.
2. Achar o índice no array com base no valor hash.
3. Verificar a existência da chave na lista de elementos (no caso de encadeamento) ou pelo índice (no caso de endereçamento aberto).

Exemplo de busca na tabela hash usando encadeamento:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def search(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return None
        for k, v in self.table[index]:
            if k == key:
                return v
        return None

# Exemplo de uso:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana"))  # Saída: 2
print(hash_table.search("grape"))   # Saída: None

3. Exclusão (Deletion): Processo de remoção de um elemento (par chave-valor) da tabela hash.

Passos da exclusão:

1. Calcular o valor hash da chave usando a função hash.
2. Achar o índice no array com base no valor hash.
3. Remover o elemento da lista (no caso de encadeamento) ou definir o valor no índice como None (no caso de endereçamento aberto).

Exemplo de exclusão da tabela hash usando encadeamento:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash_function(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            for i, kv in enumerate(self.table[index]):
                k, v = kv
                if k == key:
                    self.table[index][i] = (key, value)
                    return
            self.table[index].append((key, value))

    def delete(self, key):
        index = self.hash_function(key)
        if self.table[index] is None:
            return
        for i, kv in enumerate(self.table[index]):
            k, v = kv
            if k == key:
                del self.table[index][i]
                return

# Exemplo de uso:
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana"))  # Saída: None

6.3 Complexidade temporal da tabela hash

Complexidade temporal das operações na tabela hash

Inserção (Insertion):

• Caso médio: O(1)
• Pior caso: O(n) (em caso de muitas colisões ou se todos os elementos caírem no mesmo lugar)

Busca (Search):

• Caso médio: O(1)
• Pior caso: O(n) (em caso de muitas colisões ou se todos os elementos caírem no mesmo lugar)

Exclusão (Deletion):

• Caso médio: O(1)
• Pior caso: O(n) (em caso de muitas colisões ou se todos os elementos caírem no mesmo lugar)

Explicação:

Caso médio: No caso médio, a função hash distribui os elementos uniformemente na tabela, e cada elemento está em sua célula única, o que garante tempo constante de acesso O(1).

Pior caso: No pior caso, todos os elementos caem em uma célula devido a uma má função hash ou muitas colisões. Então a tabela hash se transforma em uma lista encadeada, e a complexidade temporal das operações se torna O(n).

6.4 Exemplos de uso de tabelas hash

1. Implementação de dicionário (array associativo)

Tabelas hash são frequentemente usadas para implementar dicionários, que permitem armazenar pares chave-valor e oferecem acesso rápido por chave.

Exemplo:

# Criação de dicionário
dictionary = {}

# Inserção de elementos
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3

# Busca de elemento
print(dictionary["banana"])  # Saída: 2

# Remoção de elemento
del dictionary["cherry"]

# Verificação da existência da chave
if "apple" in dictionary:
    print("A chave 'apple' existe no dicionário")  # Saída: A chave 'apple' existe no dicionário

Agora você sabe um pouco mais sobre o dicionário no Python e como ele funciona.

2. Cache de resultados de cálculos

Tabelas hash são usadas para armazenar em cache os resultados de cálculos dispendiosos para acelerar solicitações subsequentes.

Exemplo:

# Cache para armazenar resultados
cache = {}

def expensive_computation(x):
    if x in cache:
        return cache[x]
    result = x * x  # Exemplo de cálculo dispendioso
    cache[x] = result
    return result

# Uso do cache
print(expensive_computation(10))  # Saída: 100 (cálculo e cache)
print(expensive_computation(10))  # Saída: 100 (do cache)

3. Contagem da frequência de palavras em um texto

Tabelas hash são usadas para contar o número de ocorrências de cada palavra em um texto.

Exemplo:

from collections import defaultdict

text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)

for word in text.split():
    word_count[word] += 1

# Saída dos resultados
for word, count in word_count.items():
    print(f"A palavra '{word}' aparece {count} vez(es)")

4. Busca de duplicados em uma lista

Tabelas hash são usadas para busca eficiente de duplicados em uma lista.

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Exemplo de uso
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Saída: [2, 4]