Artigo original: What is Hashing? How Hash Codes Work - with Examples

Introdução ao hashing

O hashing foi projetado para resolver o problema da necessidade de encontrar ou armazenar eficientemente um item em uma coleção.

Por exemplo, se tivermos uma lista de 10 mil palavras em inglês e quisermos verificar se uma determinada palavra está na lista, seria ineficiente comparar sucessivamente a palavra com todos os 10 mil itens até encontrarmos uma correspondência. Mesmo que a lista de palavras esteja ordenada lexicograficamente, como em um dicionário, você ainda precisará de algum tempo para encontrar a palavra que está procurando.

O hashing é uma técnica para tornar as coisas mais eficientes, reduzindo efetivamente a busca desde o início.

O que é hashing?

Hashing significa usar alguma função ou algoritmo para mapear os dados do objeto para algum valor inteiro representativo.

Este chamado código de hash (ou simplesmente hash) pode então ser usado como um modo de reduzir a nossa busca ao procurar o item no mapa.

Geralmente, esses códigos de hash são usados para gerar um índice, no qual o valor é armazenado.

Como o hashing funciona

Em tabelas hash (em inglês, hash tables), você armazena os dados em formas de pares de chaves e valores. A chave, que é usada para identificar os dados, é dada como uma entrada para a função de hashing. O código hash, que é um número inteiro, é, então, mapeado para o tamanho fixo que temos.

As tabelas hash têm que dar suporte a 3 funções.

  • inserir (chave, valor)
  • obter (chave)
  • excluir (chave)

Apenas para fins de exemplo e para nos ajudar a compreender o conceito, suponhamos que queremos mapear uma lista de chaves de strings (por exemplo, mapear uma lista de países para suas capitais).

Digamos que queremos armazenar os dados de uma tabela no mapa.

Suponhamos que nossa função de hash é simplesmente medir o comprimento da string.

Para simplificar, teremos dois arrays: um para as nossas chaves e outro para os valores. Assim, para colocar um item na tabela de hash, calculamos seu código de hash (neste caso, basta contar o número de caracteres da string) e, depois, colocamos a chave e o valor nos arrays no índice correspondente.

Por exemplo, 'Cuba' tem um código hash (tamanho) de 4. Assim, armazenamos 'Cuba' na 4ª posição no array de chaves, 'Havana' no 4º índice do array de valores e assim por diante. Terminamos com o seguinte:

Screen-Shot-2020-03-15-at-2.54.43-PM

Agora, neste exemplo específico, as coisas funcionam bem. Nosso array precisa ser grande o suficiente para acomodar a string mais longa. Nesse caso, porém, temos apenas 11 espaços, desperdiçamos um pouco de espaço porque, por exemplo, não há chaves de 1 letra em nossos dados, nem chaves entre 8 e 10 letras.

O espaço desperdiçado, aqui, também não é tão ruim assim. Usar o tamanho de um string é simples e rápido, assim como o processo de encontrar o valor associado a uma determinada chave (certamente mais rápido do que fazer até cinco comparações de strings).

O que faremos, porém, se nosso conjunto de dados tiver uma string com mais de 11 caracteres? O que faremos se tivermos uma outra palavra com 5 caracteres, como "Índia", e se tentarmos atribuí-la a um índice usando nossa função hash? Como o índice 5 já está ocupado, teremos que fazer uma chamada sobre o que fazer com isso. Isso é chamado de 'colisão'.

Se o nosso conjunto de dados tivesse uma string com milhares de caracteres, e se você fizesse um array com milhares de índices para armazenar os dados, isso resultaria em um desperdício de espaço. Se as nossas chaves fossem palavras aleatórias do inglês, onde há muitas palavras com o mesmo tamanho, usar o tamanho como uma função de hashing seria bastante inútil.

Lidando com colisões

Dois métodos básicos são usados para lidar com as colisões.

  1. Encadeamento separado
  2. Endereçamento aberto

Encadeamento separado

O tratamento de colisão de hash por encadeamento separado, usa uma estrutura de dados adicional, de preferência, uma lista vinculada para alocação dinâmica, em buckets. Em nosso exemplo, quando adicionamos 'Índia' ao conjunto de dados, ela é anexada à lista vinculada armazenada no índice 5, então nossa tabela ficaria assim.

Screen-Shot-2020-03-15-at-2.55.47-PM

Para encontrar um item, primeiro vamos até o bucket e depois comparamos as chaves. Esse é um método popular. Se for utilizada uma lista de links, o hash nunca se esgota. O custo para get(k) é, em média, O(n) onde n é o número de chaves no bucket, o número total de chaves sendo N.

O problema com o encadeamento separado é o fato de a estrutura de dados poder crescer sem limites.

Endereçamento aberto

O endereçamento aberto não introduz nenhuma estrutura de dados nova. Se ocorrer uma colisão, procuramos a disponibilidade no próximo ponto gerado por um algoritmo. O endereçamento aberto é geralmente usado onde o espaço de armazenamento é restrito, ou seja, em processadores embarcados. O endereçamento aberto não é necessariamente mais rápido do que o encadeamento separado.

Métodos para endereçamento aberto (textos explicativos em inglês)

Como usar o hashing em seu código

Python

   # Poucas linguagens, como o Python e o Ruby, vêm com um suporte de hashing integrado.
   # Declaração
    my_hash_table = {}
    my_hash_table = dict()

   # Inserção
    my_hash_table[key] = value

   # Busca
    value = my_hash_table.get(key) # retorna None se a chave não estiver presente || Diferido em python 3, disponível em python 2
    value = my_hash_table[key] # lança uma exceção ValueError se a chave não estiver presente

    # Exclusão
    del my_hash_table[key] # lança uma exceção ValueError se a chave não estiver presente

    # Obtendo todas as chaves e valores armazenados no dicionário
    keys = my_hash_table.keys()
    values = my_hash_table.values()

Execução do código

Java

    // Java não inclui hashing por padrão. Você tem que importá-lo da biblioteca java.util
    // Importando hashmaps
    import java.util.HashMap;

   // Declaração
    HashMap<Integer, Integer> myHashTable = new HashMap<Integer, Integer>(); // declara um mapa vazio.

   // Inserção
    myHashTable.put(key, value);

   // Exclusão
    myHashtable.remove(key);

    // Busca
    myHashTable.get(key); // retorna null se a chave K não estiver presente
    myHashTable.containsKey(key); // retorna um valor booleano, indicando a presença de uma chave

    // Número da chave, pares de valores na tabela de hash
    myHashTable.size();

Execução do código

Mais informações sobre hashing (textos em inglês)