Conceito de função hash

5.1 Definição de função hash e sua aplicação

Função hash — é uma função que recebe dados de entrada (ou chave) e retorna um tamanho fixo de bits, geralmente chamado de hash ou valor hash. O propósito principal de uma função hash é distribuir dados de forma eficiente em uma tabela hash para garantir acesso rápido aos elementos.

Aplicações:

• Tabelas hash: Usadas para implementar arrays associativos (dicionários em Python), fornecendo acesso rápido aos dados por chave.
• Controle de integridade de dados: Funções hash são usadas para verificar a integridade de arquivos e dados (por exemplo, algoritmos MD5, SHA-1, SHA-256).
• Criptografia: Funções hash são usadas em algoritmos criptográficos para criptografia e criação de assinaturas digitais.
• Motores de busca: Aplicadas para indexar dados e buscar informações rapidamente.
• Gerenciamento de cache: Usadas para organizar caches, permitindo encontrar dados rapidamente.

Exemplo de aplicação de função hash em Python:

# Exemplo de uso de função hash em Python para tabela hash (dicionário)
data = {"apple": 1, "banana": 2, "cherry": 3}

# Obtendo o valor hash da chave
key = "banana"
hash_value = hash(key)

print(f"Valor hash para a chave '{key}': {hash_value}")

5.2 Analogias da vida real

Com uma função hash, você pode dividir um grande grupo de objetos em grupos aproximadamente iguais. Além disso, se continuar adicionando novos objetos, eles continuarão a ser distribuídos de forma uniforme entre os grupos.

Suponha que você tenha 1000 pessoas e precisa distribuí-las em 30 grupos. Veja como isso pode ser feito.

Método 1. Pela primeira letra do nome.

O primeiro grupo é formado por todos que têm o nome começando com 'A', o segundo grupo é todos que têm o nome começando com 'B', e assim por diante. A regra "Seu grupo é a primeira letra do seu nome" é a função hash. Mas com tal função hash, corremos o risco de ter muitas pessoas no grupo 'A' e poucas em 'Z'.

Método 2. Pela data de nascimento.

Nascido no primeiro dia de qualquer mês — primeiro grupo, no segundo dia — segundo grupo, e assim por diante. Haverá 31 grupos. No 31º grupo, as pessoas serão cerca de duas vezes menos do que nas outras, mas as pessoas nesses grupos são distribuídas muito mais uniformemente do que no primeiro caso.

Método 3. Número de telefone

O cenário ideal é obter um número que seja, por um lado, o mais aleatório possível (para que tais números sejam distribuídos uniformemente), por outro lado, ele deve ser sempre rápido de calcular e ser o mesmo.

Vamos pegar os últimos 4 dígitos do número de telefone — isso será 10000 alternativas. E então dividimos esse número exatamente por 30. Assim teremos 30 possíveis restos da divisão: 0, 1, 2, ..., 29. Esses serão os números dos nossos grupos.

Legal! A propósito, quase toda função hash usa o resto da divisão inteira — é muito simples e permite regular a quantidade de grupos nos quais os elementos precisam ser divididos.

5.3 Propriedades principais de uma função hash

Propriedades principais de uma boa função hash:

Determinismo: A mesma função hash deve sempre retornar o mesmo valor hash para o mesmo valor de entrada.

Exemplo:

key = "example"
assert hash(key) == hash(key)

Importante! O operador assert verifica se a expressão à direita é verdadeira True. Se a expressão não for verdadeira False, uma exceção será lançada.

Uniformidade: Uma boa função hash deve distribuir valores uniformemente em todo o intervalo de valores de hash possíveis para evitar colisões.

Exemplo da vida de um desenvolvedor Python: No dicionário (classe dict) do Python, a função hash hash() distribui as chaves uniformemente.

Eficiência de cálculo: A função hash deve ser rápida e eficiente, para não atrasar as operações de inserção e busca.

Exemplo da vida de um desenvolvedor Python: As funções hash padrão no Python são implementadas para trabalhar com chaves de diversos tipos, como strings e números.

Minimização de colisões: Colisão acontece quando duas chaves diferentes possuem o mesmo valor hash. Uma boa função hash deve minimizar a probabilidade de colisões.

Exemplo da vida de um desenvolvedor Python: O algoritmo SHA-256 minimiza a probabilidade de colisões ao hash dos dados.

Distribuição de hashes: Para grandes volumes de dados, a função hash deve garantir uma distribuição uniforme dos valores hash por toda a tabela hash.

Exemplo da vida de um desenvolvedor Python: As funções hash padrão no Python lidam bem com a distribuição de chaves em tabelas hash.

5.4 Exemplos de funções hash e sua implementação

Funções hash recebem como entrada dados de tamanho variável e retornam tamanho fixo de valor hash. Vamos ver alguns exemplos de funções hash e sua implementação.

Exemplo 1: Função hash simples para strings

Uma das funções hash mais simples para strings pode ser implementada usando a soma dos códigos dos caracteres da string:

def simple_hash(key):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % 1000  # Assumimos que nossa tabela tem tamanho 1000

# Exemplo de uso:
key = "example"
print(f"Valor hash para a chave '{key}': {simple_hash(key)}")

Exemplo 2: Função hash para strings usando hash polinomial

O hash polinomial é uma técnica mais complexa, mas eficaz:

def polynomial_hash(key, a=33, m=1000):
    hash_value = 0
    for char in key:
        hash_value = (hash_value * a + ord(char)) % m
    return hash_value

# Exemplo de uso:
key = "example"
print(f"Valor hash para a chave '{key}': {polynomial_hash(key)}")

Exemplo 3: Função hash embutida no Python

O Python fornece uma função embutida hash() para obter o valor hash para diferentes tipos de dados:

key = "example"
print(f"Valor hash para a chave '{key}': {hash(key)}")

Exemplo 4: Função hash criptográfica (SHA-256)

Funções hash criptográficas, como SHA-256, são usadas para garantir a segurança dos dados:

import hashlib

def sha256_hash(key):
    return hashlib.sha256(key.encode()).hexdigest()

# Exemplo de uso:
key = "example"
print(f"Valor hash para a chave '{key}': {sha256_hash(key)}")

5.5 Introdução ao hash e sua aplicação

Hashing — é o processo de converter dados de entrada de tamanho variável em um valor hash de tamanho fixo usando uma função hash. Hashing é amplamente usado em ciências da computação e programação para otimização e segurança.

Principais aplicações de hashing:

1. Tabelas hash (dicionários): Tabelas hash usam funções hash para organizar e acessar dados rapidamente.

data = {"apple": 1, "banana": 2, "cherry": 3}
key = "banana"
hash_value = hash(key)
print(f"Valor hash para a chave '{key}': {hash_value}")

2. Controle de integridade de dados: Funções hash são usadas para verificar a integridade de arquivos e dados.

Exemplo: Verificação de integridade de arquivo usando SHA-256:

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()

file_hash = get_file_hash('example.txt')
print(f"SHA-256 hash do arquivo: {file_hash}")

3. Criptografia e segurança: Funções hash são usadas para criar primitivas criptográficas, como assinaturas digitais e hashes de senhas.

Exemplo: Hashing de senha usando SHA-256:

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

password = "securepassword"
hashed_password = hash_password(password)
print(f"Hash da senha: {hashed_password}")

4. Motores de busca e indexação: Hashing é aplicado para criar índices e buscar dados rapidamente.

Exemplo: Criando um índice para busca de texto:

def create_index(text):
    index = {}
    for word in text.split():
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

text = "This is an example text for indexing"
index = create_index(text)
print(f"Índice: {index}")

5. Gerenciamento de cache: Hashing é usado para organizar caches para encontrar dados rapidamente.

Exemplo: Cache simples usando função hash:

cache = {}

def get_from_cache(key):
    hash_key = hash(key)
    return cache.get(hash_key, None)

def add_to_cache(key, value):
    hash_key = hash(key)
    cache[hash_key] = value

# Adicionando e obtendo dados do cache
add_to_cache("test_key", "test_value")
print(get_from_cache("test_key"))  # Saída: test_value