10.1 Introdução às funções de hash e tabelas hash
Bora relembrar e aprofundar nosso entendimento sobre funções de hash e tabelas. Função de hash é um algoritmo que transforma dados de entrada de comprimento arbitrário em uma string de comprimento fixo. Propriedades principais das funções de hash:
- Determinismo: as mesmas entradas sempre dão o mesmo resultado.
- Calculação rápida: o hash deve ser calculado bem rapidinho.
- Irreversibilidade (para funções de hash criptográficas): a partir do hash, é impossível (ou bem difícil) recuperar os dados originais.
- Distribuição uniforme: pequenas mudanças nos dados de entrada resultam em grandes mudanças no hash.
Simplificando, essa função nos mesmos objetos é sempre igual, mas se a função de hash de dois objetos for a mesma, esses objetos não necessariamente são iguais. Na matemática, isso é chamado de condição necessária, mas não suficiente.
Tabela hash é uma estrutura de dados que usa uma função de hash para armazenar e procurar informações de forma eficiente. Ela consiste em:
- Uma matriz de "buckets" para armazenamento de dados.
- Função de hash, que determina em qual bucket colocar os dados.
Tabelas hash oferecem acesso rápido aos dados, geralmente com complexidade O(1) em média.
Aplicação das funções de hash na vida real
Exemplo: Tecnologias de Blockchain
No blockchain, funções de hash são usadas para criar identificadores únicos de blocos e garantir a integridade dos dados. Cada bloco contém o hash do bloco anterior, o que cria uma corrente e torna o sistema resistente a mudanças.
import hashlib
import time
class Block:
def __init__(self, data, previous_hash):
self.timestamp = time.time()
self.data = data
self.previous_hash = previous_hash
self.hash = self.calculate_hash()
def calculate_hash(self):
hash_string = str(self.timestamp) + str(self.data) + str(self.previous_hash)
return hashlib.sha256(hash_string.encode()).hexdigest()
# Exemplo de uso
block1 = Block("Transação 1", "0")
block2 = Block("Transação 2", block1.hash)
print(f"Hash do bloco 1: {block1.hash}")
print(f"Hash do bloco 2: {block2.hash}")
Comparação de performance
Vamos dar uma olhada no problema de encontrar duplicatas em um array. Compararemos a solução usando tabela hash e sem ela:
import time
def find_duplicates_with_hash(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
def find_duplicates_without_hash(arr):
duplicates = []
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] == arr[j] and arr[i] not in duplicates:
duplicates.append(arr[i])
return duplicates
# Teste de performance
arr = list(range(10000)) + list(range(5000)) # Array com duplicatas
start = time.time()
find_duplicates_with_hash(arr)
end = time.time()
print(f"Tempo com tabela hash: {end - start} segundos")
start = time.time()
find_duplicates_without_hash(arr)
end = time.time()
print(f"Tempo sem tabela hash: {end - start} segundos")
Rode o programa e veja como o uso de tabela hash acelera a busca por duplicatas. Especialmente em grandes conjuntos de dados.
10.2 Exemplos de aplicações de funções de hash em tarefas reais
1. Hash de senhas
Funções de hash são usadas para armazenar senhas de forma segura. Em vez de armazenar senhas em texto claro, os sistemas armazenam os hashes delas. Quando o usuário digita a senha, o sistema faz o hash da senha digitada e compara com o hash armazenado no banco de dados.
Exemplo de implementação:
import hashlib
def hash_password(password):
return hashlib.sha256(password.encode()).hexdigest()
# Exemplo de uso:
password = "securepassword"
hashed_password = hash_password(password)
print(f"Hash da senha: {hashed_password}")
2. Verificação de integridade de dados
Funções de hash são usadas para verificar a integridade de arquivos e dados. Por exemplo, para verificar se um arquivo não foi alterado ou corrompido durante a transferência.
Exemplo de implementação:
import hashlib
def get_file_hash(file_path):
hasher = hashlib.sha256()
with open(file_path, 'rb') as file:
buf = file.read()
hasher.update(buf)
return hasher.hexdigest()
# Exemplo de uso:
file_hash = get_file_hash('example.txt')
print(f"SHA-256 hash do arquivo: {file_hash}")
3. Motores de busca e indexação
Os motores de busca usam funções de hash para criar índices e procurar informações rapidamente. Cada documento é indexado por palavras-chave, e funções de hash ajudam a encontrar rapidamente documentos que contêm palavras específicas.
Exemplo de implementação:
def create_index(text):
index = {}
words = text.split()
for word in words:
word_hash = hash(word)
if word_hash not in index:
index[word_hash] = []
index[word_hash].append(word)
return index
# Exemplo de uso:
text = "This is an example text for indexing"
index = create_index(text)
print(f"Índice: {index}")
10.3 Otimização de busca usando funções de hash
1. Uso de tabelas hash para encontrar duplicatas
Tabelas hash permitem encontrar rapidamente duplicatas num array, comparando os valores de hash dos elementos.
Exemplo de implementação:
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]
2. Otimização de busca de pares com soma determinada
Tabelas hash permitem encontrar eficientemente pares de números num array cuja soma é igual a um valor determinado.
Exemplo de implementação:
def find_pairs_with_sum(arr, target_sum):
seen = set()
pairs = []
for num in arr:
complement = target_sum - num
if complement in seen:
pairs.append((complement, num))
seen.add(num)
return pairs
# Exemplo de uso:
arr = [2, 4, 3, 7, 8, -2, 10, -1]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum)) # Saída: [(4, 2), (3, 3), (8, -2)]
10.4 Exemplos de uso de funções de hash em vários algoritmos
1. Contagem de palavras em um texto
Use uma tabela hash para contar o número de ocorrências de cada palavra em um texto.
Exemplo de implementação:
def count_words(text):
word_count = {}
words = text.split()
for word in words:
if word in word_count:
word_count[word] += 1
else:
word_count[word] = 1
return word_count
# Exemplo de uso:
text = "this is a test this is only a test"
print(count_words(text)) # Saída: {'this': 2, 'is': 2, 'a': 2, 'test': 2, 'only': 1}
2. Checagem de interseção entre dois arrays
Verifique se dois arrays se cruzam (têm ao menos um elemento em comum).
Exemplo de implementação:
def has_intersection(arr1, arr2):
set1 = set(arr1)
for item in arr2:
if item in set1:
return True
return False
# Exemplo de uso:
arr1 = [1, 2, 3, 4]
arr2 = [3, 5, 6, 7]
arr3 = [8, 9, 10]
print(has_intersection(arr1, arr2)) # Saída: True
print(has_intersection(arr1, arr3)) # Saída: False
3. Verificação de unicidade de elementos em um array
Verifique se um array contém apenas elementos únicos.
Exemplo de implementação:
def all_unique(arr):
seen = set()
for item in arr:
if item in seen:
return False
seen.add(item)
return True
# Exemplo de uso:
arr1 = [1, 2, 3, 4, 5]
arr2 = [1, 2, 3, 4, 5, 3]
print(all_unique(arr1)) # Saída: True
print(all_unique(arr2)) # Saída: False
GO TO FULL VERSION