O guia sem código para tabelas de hash e hash

Se você já programou antes, com certeza já encontrou tabelas de hash e hash. Muitos desenvolvedores usaram tabelas de hash de uma forma ou de outra, e os desenvolvedores iniciantes devem aprender essa estrutura de dados fundamental. Só há um problema:

Todos os tutoriais que você encontrar certamente discutirão hash e tabelas de hash em JavaScript, Python ou alguma outra linguagem de programação.

O que isso significa é que você pode entender um pouco sobre como funciona o hashing e como usar uma tabela de hash em [inserir linguagem aqui], mas pode perder os princípios de como funciona.

Não seria ótimo se pudéssemos aprender sobre hash sem conhecer nenhum idioma específico? Se você sabe como funciona o hashing e o que é uma tabela hash, a linguagem não deve importar.

Essa é a abordagem sem código e, neste post, vou ensinar tudo sobre hashing e tabelas hash, independentemente da linguagem de programação que você está usando no momento. Quer você seja um desenvolvedor júnior ou sênior, todos aprenderão algo com este post.

Então, o que é uma função Hash?

Antes de entrarmos em todas as coisas chiques, deixe-me dizer o que é hash. Para facilitar, vamos imaginar que temos uma caixa preta:

Esta caixa preta é especial. É chamado de caixa de função. Vamos chamá-la de caixa de função porque esta caixa irá mapear uma variável independente na entrada para uma variável dependente na saída (parece matemático, mas tenha paciência comigo).

Nossa caixa de função funciona assim: se colocarmos uma letra na caixa, obteremos um número. Visto que nossa caixa é uma caixa de função, só pode haver uma saída para cada entrada na caixa.

Nossa caixa de função pegará uma letra de AJ na entrada e produzirá um número correspondente de 0 a 9 na saída. Portanto, se inserirmos C, obteremos 2 na saída.

Isso forma os fundamentos do que é uma função hash. A função hash, no entanto, dá um passo adiante. Mapearemos os dados na entrada para algum valor numérico na saída, geralmente uma sequência hexadecimal.

Então, basicamente, tudo o que o hashing faz é usar uma função para mapear os dados para um valor numérico ou alfanumérico representativo. Para a função hash, independentemente do tamanho da entrada, a saída permanecerá sempre a mesma.

E quanto às tabelas de hash?

Portanto, neste ponto, você deve estar se perguntando o que é uma tabela hash. As tabelas de hash utilizam hashing para formar uma estrutura de dados.

As tabelas de hash usam um método associativo para armazenar dados usando o que é conhecido como sistema de pesquisa de valor-chave. Tudo isso significa que, em uma tabela hash, as chaves são mapeadas para valores únicos.

Este sistema de organização de dados resulta em uma maneira muito rápida de encontrar dados de forma eficiente. Isso ocorre porque, uma vez que cada chave é mapeada para um valor único, uma vez que conhecemos uma chave, podemos encontrar o valor associado instantaneamente.

As tabelas de hash são extremamente rápidas, tendo uma complexidade de tempo da ordem de O (1).

Confuso? Dê uma olhada neste diagrama, onde temos várias caixas de função gerando valores de hash.

Nesse cenário, cada caractere na entrada (cada um é uma chave) tem uma função hash aplicada a ele, e a função hash na caixa de função gera o valor hash. Esse valor resultante é então mapeado para um índice na lista vinculada subjacente ou matriz usada para implementar a tabela hash.

A estrutura resultante será semelhante a esta:

Colisões de hash

Este é um bom momento para falar sobre a colisão de funções hash e tabelas hash.

Uma função em matemática é ideal porque um elemento na entrada é mapeado para exatamente um elemento na saída.

Em uma função hash, no entanto, nem sempre é assim. Às vezes, valores de hash diferentes na entrada podem produzir o mesmo valor de hash na saída. Quando isso ocorre, você obtém o que é conhecido como colisão hash.

As colisões de hash não são muito comuns na maioria dos casos de uso, pois uma pequena mudança na entrada pode produzir uma saída drasticamente diferente. Porém, quanto mais dados você tiver para inserir na função hash, maior será a probabilidade de ocorrer uma colisão.

No exemplo da tabela hash que fornecemos anteriormente, presumimos que uma matriz foi usada para implementar a tabela hash. Embora isso seja bom para tabelas hash simples, na prática elas não são muito boas para lidar com colisões.

Como tal, um método conhecido como encadeamento é usado. No encadeamento, se a tabela hash retornar o mesmo valor hash para vários elementos, simplesmente "encadearemos" os elementos com os mesmos valores hash no mesmo índice da tabela hash.  

Dessa forma, em vez de ser implementado como um array com um índice, implementamos a tabela hash usando uma lista vinculada onde cada elemento é uma lista em vez de simplesmente ter um único valor atribuído a ela.

Mas, à medida que o comprimento da cadeia aumenta, a complexidade do tempo da tabela hash pode piorar. Um método conhecido como endereçamento aberto também é usado. Nele, são encontrados locais alternativos na estrutura de dados subjacente que implementa a tabela hash. Basta lembrar que este método reduzirá a eficiência da tabela hash e terá uma complexidade de tempo pior.

Hashing é o mesmo que criptografia ou codificação?

Muitas pessoas tendem a associar o hashing com criptografia ou codificação. Então, hashing é criptografia? É o mesmo que codificação?

Veja, na criptografia nós misturamos os dados para que apenas alguém com a chave necessária para descriptografar os dados tenha acesso a eles. Quando utilizamos uma cifra de criptografia, não apenas criptografamos os dados, mas também queremos descriptografá-los em algum ponto. Na criptografia, queremos recuperar os dados originais.

O hash, por outro lado, pega os dados e produz uma saída com o propósito de confirmar a integridade dos dados. No hashing, não temos intenção de recuperar os dados originais.

A codificação difere da criptografia e do hashing porque o objetivo da codificação não é obscurecer os dados para qualquer finalidade de segurança, mas simplesmente converter os dados em um formato que outro sistema possa usar.

O que posso fazer com o hash?

Hashes e tabelas hash têm vários usos! Esses incluem:

  1. Criptossistemas
  2. Verificações de redundância cíclica
  3. Motores de busca
  4. Bancos de dados
  5. Compiladores

Ou qualquer sistema que tenha um processo de pesquisa complexo.

Empacotando

Nesta postagem, cobrimos o básico do hashing, tudo sem escrever uma única linha de código! Isso foi fácil certo? A abordagem sem código é uma maneira muito mais fácil de aprender sobre esses tópicos fundamentais.

Aprendemos que as funções hash podem ser usadas para converter objetos em uma saída alfanumérica de comprimento fixo. Também aprendemos que as tabelas hash são sistemas de pesquisa de valor-chave e, embora funcionem bem, não são perfeitas e às vezes sofrem colisões.

No final desta postagem, você deve saber a diferença entre hashing, criptografia e codificação, e também ter uma ideia de onde os hashes podem ser usados.

Você gostou da abordagem sem código? Quer ir mais longe?

Aprenda mais sobre tabelas de hash e outras estruturas de dados e algoritmos no livro "Codeless Data Structures and Algorithms". Você obterá uma expansão do que foi abordado neste post e aprenderá sobre muitos outros tópicos, tudo sem escrever uma única linha de código!

Algoritmos e estruturas de dados sem código - Aprenda DSA sem escrever uma única linha de código | Armstrong Subero | Apress Este livro traz uma nova perspectiva sobre algoritmos e estruturas de dados, totalmente livre de códigos. Aprenda sobre algoritmos de estrutura de dados (DSAs) sem nunca ter que abrir seu editor de código, usar um compilador ou olhar para um ambiente de desenvolvimento integrado (IDE) .... Armstrong Subero Pesquisar Menu Carrinho V Seu carrinho está vazio no momento. Login AccountBookshelf Login Apress Access