Tabela Hash

Introdução

Estrutura de dados é uma parte fundamental no estudo inicial de programação. Entender as diferentes estruturas de dados, saber como usá-las é primordial. Estava estudando o curso: Aprenda o que são estrutura de dados e algoritmos, no momento que falou de tabela hash foi mais superficial que as outras estruturas de dados. Fui procurar mais informações na internet, como um bom dev aprendiz dei um google e logo encontrei vários vídeos falando do assunto e então vi algumas definições também superficiais e a frustração foi inevitável. Então tentei o ChatGPT, mas acreditem, estava fora do ar, não consegui obter nenhuma resposta. Então, busquei ajuda no copilot e consegui entender um pouco mais do que havia entendido no curso, aí decidi escrever este artigo para aprender mais e obter o feedback dos que entendem mais do assunto. Então vamos ao pouco que entendi.

Definição

Uma tabela hash é uma estrutura de dados que associa chaves a valores, ela permite buscas rápidas e eficientes, ideal para indexação e acesso a dados. Cada conjunto chave, valor, o campo valor é chamado “slot”. No geral, muito utilizado em sistemas de autenticação de usuários para guardas as senhas escolhidas com mais segurança, mais à frente vamos falar um pouco mais sobre isso.

Um exemplo de uso de tabelas hash são:

Vetores associativos: mapeamento de chaves (por exemplo, nomes) para valores (por exemplo, números de telefone).

Índice 0: “Paula” | “7198749874”        <- slot 1

Índice 1: “Antenor” | “71999999999”  <- slot 2

Índice 2:                                              <- slot 3

Índice 3:                                              <- slot 4

Índice 4: “fernando” | “11999994444” <- slot 5

Neste exemplo temos uma tabela hash em que há um mapeamento do nome da pessoa pelo seu número de telefone.

Sets (conjuntos): Verificação de pertencimento (por exemplo, verificar se um elemento está em um conjunto). O referido conjunto não necessariamente estão ordenados.

Temos por exemplo o conjunto de números primos (2, 3, 5, 7, 11). Para a verificação de pertencimento usamos a operação in. 

Caches: área de armazenamento temporário para dados que são usados com frequência. Exemplo: cache de resultados de consultas de um banco de dados, evita novas consultas ao banco de dados uma vez que tais dados serão usados novamente. Quando uma consulta é feita antecipadamente verifica-se o cache. Se os dados estiverem lá, evita-se mais uma consulta, diminuindo assim o fluxo de dados e tornando a aplicação mais célere.

Enfim, as tabelas hashes são uma forma de indexar dados. Elas são projetadas para permitir o acesso rápido aos valores com base em chaves associados de forma otimizada, mesmo que se trate de recuperação de informações em grandes conjuntos de dados. O código hash (índice) é calculado e mapeado para um índice no array, os valores por sua vez são armazenados nos índices correspondentes.

Função de Espalhamento (Hash Function)

O que é: A função de espalhamento mapeia a chave para um índice na tabela hash. Vamos ver um exemplo. Sumponha que temos uma tabela hash com 10 índices numerados de 0 a 9. Queremos armazenar palavras chaves nessa tabela. Vamos criar uma função de espalhamento básica. Armazenar as palavras: “gato”; “cachorro”; “leão”; “cabra”; “onça”; “urso”; “elefante”; “touro”; “cobra”; “jacaré”. Para popular a tabela hash vamos utilizar a seguinte função: O resto da divisão entre a soma dos valores ASCII de cada caracter das palavras pela quantidade de posições da tabela.

1ª palavra: “gato” => (103 +97 + 116 +111) % 10

                                            427 % 10 = 7, este é o índice (hash) que armazenaremos a palavra gato.

2ª palavra: “cachorro” => (99+97+99+104+111+114+114+111) % 10

                                                      849 % 10 = 9, este é o hash para a palavra cachorro.

Assim se procederá com todas as palavras, não muito raro, principalmente neste caso que a quantidade de índices da tabela é limitada que alguma palavra precise ser armazenada no mesmo índice de outra palavra, a isto dá-se o nome de “colisão”, é comum funções de espalhamento gerarem colisões. Mas aí fica a questão, e agora como armazenar as palavras se não se pode armazenar palavras distintas no mesmo índice? Há algumas formas de resolver colisões.

Resolvendo Colisões

Os métodos mais comuns para resolver colisões são: Endereçamento Separado, Endereçamento Aberto e a Indexação perfeita (melhor dos casos).

Endereçamento separado: Neste caso cada slot da tabela contém uma lista encadeada de elementos com o mesmo índice. Quando ocorre uma colisão (ou seja, duas chaves são mapeada para o mesmo slot), os elementos são simplesmente adicionados à lista correspondente. Vamos supor que as palavras “cachorro” e “elefante” mapeiem para o mesmo slot, então a tabela hash ficaria da seguinte forma:

Índice 0:

Índice 1:

Índice 2:

Índice 3:

Índice 4:

Índice 5:

Índice 6:

Índice 7: 7 | “gato”

Índice 8:

Índice 9:  9 | “cachorro” -> “elefante”

Outra forma de resolver a colisão é Endereçamento Aberto, ou sondagem linear que consiste em tentar encontrar outro slot livre na tabela. A sondagem linear é uma técnica comum em que se verifica os slots sequencialmente até encontrar um vazo. No exemplo que acabamos de tratar a colisão entre “cachorro” e “elefante” a palavra elefante seria armazenada no slot de índice 0, pois é o próximo slot vazio. Caso o slot 0 estivesse ocupado, então tentaria o slot 1, caso estivesse ocupado tentaria o slot 3 e assim por diante. No caso citado sempre se encontrará um slot vazio pois tem-se 10 palavras para 10 slots.

Indexação Perfeita é a situação ideal, mas nem sempre é possível. Significa que cada chave tem um índice exclusivo na tabela hash sem colisões. Se tivéssemos a função hash perfeita, cada palavra estaria indexada perfeitamente e não haveria nenhuma colisão.

Há estratégias que visam auxiliar na busca de uma boa função hash que garante o máximo de espelhamento pela tabela, o hashing (espalhamento) perfeita é aquela em que, dada uma tabela de n posições e n elementos a serem inseridos não há colisão. Uma estratégia para escolher a função hash é o método Cichelli, visa minimizar as colisões que na verdade consiste em fazer algum ajuste no hash para diferenciar do hash já calculado. Este ajuste pode ser chamado salt que é, por exemplo, uma constante adicionada à hashing fazendo-se diferentes possíveis valores que colidiram, este salt deve ser armazenado em algum campo da tabela, para quando houver tentativa de acesso ao valor, adicionar ao hash e assim os valores coincidirem. Talvez isso tenha ficado um pouco confuso.

Lembrando do exemplo acima em que fizemos as palavras “cachorro” e “elefante” colidirem, o salt poderia ser o hashing dividido por 2, ou o número 1 por exemplo. Aí você pensa, ué, mas se fizer isso para todo hash a colisão permanece, mas o salt é adicionado apenas ao segundo valor, o que gerou a colisão, logo seria apenas o hash da palavra elefante.

Por exemplo:

Índice 9: 9 | “cachorro”

Hash calculado para “elefante” 9, adicionando o salt 1, o hash passaria a ser 10 % 10 = 0, logo a palavra “elefante” seria armazenado no slot de índice 0.

Índice 0: 0 | “elefante”

Índice 7: 7 | “cachorro”

A estrutura de dados tabela hash tem complexidade na notação Big O(1), pois a busca é imediata, ideal.

Aplicação

Uma aplicação muito comum para tabelas hash é sistemas de autenticação de usuário. O usuário cadastra uma senha, uma hashing é aplicada a esta senha, e no banco de dados deve ser armazenado o hash da senha cadastrada, jamais guardar a própria senha digitada pelo usuário, assim garante a segurança de uma informação tão sensível. Há várias hasins utilizadas para isso: md4, md5, sha-1, sha-256, sha-512.

Mas se a senha não está armazenada, apenas o hash da senha, com saber se o usuário digitou a senha correta? Simples, a senha digitada pelo usuário passa novamente pela hashin e então comparado o hash recém gerado com o hash armazenado no banco de dados, deste modo ocorre a autenticação.

Outra situação de uso de hash é verificação de arquivos. Como as funções hash garantem a integridade de arquivos? Quando se calcula o hash de um arquivo, obtém uma representação compacta dos dados. Se houver alguma alteração em um arquivo o hash resultante será distinto. Portanto, tal comparação permite verificar se o arquivo permaneceu inalterado. Então pode-se fazer tal comparação antes e após o download de um arquivo por exemplo.

Uma outra aplicação de tabela hash são as assinaturas digitais. As assinaturas digitais usam funções hash para verificar a autenticidade de documentos. O hash do documento é criptografado com a chave privada do remetente, criando uma assinatura digital. O destinatário pode verificar a assinatura descriptografando o hash com a chave pública do remetente.

Um exemplo de uso de tabelas hash para um pequeno sistema de autenticação de usuário. Aqui vou adicionar um código em python. Usuário cria senha, a senha é armazenada em uma tabela hash. No momento do login, a senha digitada pelo usuário passa novamente pela função hash (hashin) e então verificado se os valores hash são idênticos. Para este exemplo vou usar o hashin MD5. Usarei o módulo python haslib para trabalhar com funções de hash.

import hashlib

# Tabela hash para armazenar senhas (usuário -> senha_hash)
tabela_senhas_hash = {}

def hash_senha(senha):
# Cria um objeto MD5
Md5_hash = hashlib.md5()
# Atualiza o objeto MD5 como uma string hexadecimal
Md5_hash.update(senha.encode(‘utf-8’))
# Retorna o hash MD5 como uma string hexadecimal
Return md5_hash.hexdigest()


def add_user(usuario, senha):
# Armazena a senha hash na tabela
tabela_senhas_hash[usuário] = hash_senha(senha)
  
def autenticar_usuario(usuario, senha):
if usuário in tabela_senhas_hash:
  hash_armazenado = tabela_senhas_hash[usuario]
  input_hash = hash_senha(senha)
  return stored_hash == input_hash
return False

# Exemplo de uso
add_user(‘alice’, ‘mysecret’)
add_user(‘guedes’, ‘password123’)
# Essas não são senhas boas, são fracas e mesmo com o hash, é possível descriptografar # com uma table_name. Por isso é importante os usuários escolherem senhas fortes.

# simulando autenticação
print(autenticar_usuario(‘alice’, ‘mysecret’)) # Deve retornar True
print(autenticar_usuario(‘guedes’, ‘wrogpass’)) # Deve retornar False

No exemplo não há nenhuma forma de tratar as colisões. Se por alguma coincidência houver colisão entre as senhas cadastradas por diferentes usuários? Vamos tentar tratar as colisões. Neste nosso exemplo vamos usar a técnica de encadeamento (chaning), cada entrada da tabela hash é uma lista ligada (ou seja, uma lista de senhas com o mesmo valor de hash). Se houver uma colisão, adicionamos uma nova senha à lista existente. Para adicionar o tratamento de colisão vamos alterar o método de adicionar usuário pois é onde acontece a inserção de valores na tabela hash, o método fica da seguinte forma:

def add_user(usuario, senha):
# Calcula o hash da senha
senha_hash = hash_senha(senha)

# Verifica se o usuário já existe na tabela
If usuário in tabela_senhas_hash:

  # Adiciona a senha à lista hash existente
    tabela_senhas_hash[usuário].append(senhas_hash)
else:
  # Cria uma nova lista com a nova senha
  tabela_senhas_hash[usuario] = [senha_hash]

Considerações importantes: Para fins de segurança a hashin MD5 não é o mais indicado, seria melhor utilizar sha-256 ou sha-512. Interessante também adicionar um salt às senhas antes de calcular o hash, o que aumentará a segurança, pois isso torna mais difícil para um invasor usar tabelas de hash pré-computadas (Rainbow tables) para quebrar senhas. 

Obrigado por ler este artigo.