Uma Introdução às HashTables

Na sua carreira como desenvolvedor você provavelmente já se deparou com esse conceito, seja para agrupar dados ou mesmo para aumentar a performance de um algoritmo, afinal de contas, HashTables são uma das estruturas de dados mais simples e performáticas para a resolução de problemas, mas talvez você nunca tenha se aprofundado nesse assunto. É isso que faremos hoje.

O que é uma HashTable?

É um algoritmo de chave-valor, você insere uma chave e atribui um valor a essa chave, então quando precisar do valor novamente basta referenciar a chave que você definiu e pronto, você tem seu valor de volta.

"Mas Miguel, qual a diferença de eu usar uma HashTable para armazenar minhas estruturas e usar um Array?", bom, dependendo do caso, talvez o Array não performe tão bem quanto você espera, fora que para a maioria dos casos uma tabela hash tem complexidade constante O(1), isso significa que ela não perde performance caso o volume de dados aumente.

Hash Functions

Antes de irmos direto ao ponto precisamos deixar isso claro: uma HashTable é uma implementação de uma HashFunction (não, elas não são a mesma coisa!). Basicamente, uma função hash é uma função que recebe uma sequência de bytes e devolve um número. E sim, é simples dessa forma.

Mas agora talvez você esteja me perguntando: "Mas Miguel, pra que eu vou querer usar isso? Não me parece muito útil!" e é aí que você se engana, meu jovem. Existe um universo de ferramentas que se baseiam inteiramente em uma função hash, principalmente na área da criptografia.

O melhor exemplo que eu posso te dar no momento é o SHA (Secure Hash Algorithm), que pega um arquivo e devolve uma sequência alfanumérica. Podemos usar o SHA, por exemplo, para validar se duas pessoas possuem o mesmo arquivo de texto. Você pega o arquivo binário (que é uma sequência de bytes, não podemos esquecer disso) e se ambos os arquivos gerarem a mesma sequência, então é o mesmo arquivo. Legal, né?

Hash Tables

Como mencionado anteriormente, a HashTable é uma funcionalidade que se baseia numa HashFunction, com a diferença de que ela vai fazer uma implementação de arrays por baixo dos panos. Funciona da seguinte forma:

Sempre que você define uma chave, uma HashFunction é chamada e ela atribui a sua chave ao índice de um array como mostrado na imagem acima. É assim que você consegue guardar estruturas de dados mais complexas dentro de uma HashTable, afinal de contas, não passa de um Array por baixo dos panos.

Hoje temos diversos usos que podemos fazer pra esse tipo de estrutura de dados, uma das mais comuns que eu posso citar é o próprio DNS (Domain Name System), basicamente quando você digita algo como "www.google.com" na URL do seu navegador, esse dominío é traduzido para o IP do servidor da Google (algo como "142.250.217.78"), e é graças à HashTable que o DNS consegue fazer esse tipo de "tradução".

Para finalizar, gostaria de deixar claro que você nunca vai precisar implementar uma HashTable do zero, pois muito provavelmente a sua linguagem de programação favorita já fez isso. Estarei deixando abaixo uma ótimo exemplo de implementação de uma HashTable com C#.

using System.Collections;

class Program
{
    static void Main()
    {
        Hashtable contacts = [];

        contacts.Add("John", "Doe");
        contacts.Add("Joana", "Doe");

        foreach(DictionaryEntry contact in contacts)
        {
            Console.WriteLine("Key = {0}, Value = {1}", contact.Key, contact.Value);
            // Key = John, Value = Doe
            // Key = Joana, Value = Doe
        }
    }
}

Obrigado!

Se você acompanhou este post até aqui eu gostaria de te agradecer, tentei ser o mais didático possível pois sei como esse tipo de tema pode ser confuso às vezes.

Em breve pretendo soltar mais alguns artigos sobre temas um pouco mais complexos. Por enquanto ficamos por aqui. Muito obrigado e até a próxima!⚡