11

O conceito de hashes (ou tabelas hash) já vem embutido em várias linguagens de programação como Javascript, Python, Ruby, etc, e é conhecida por ser muito mais rápida que, por exemplo, listas encadeadas. Ela associa pares chave-valor assim:

meuHash = []
meuHash["minha chave"] = "meu valor"

Minha dúvida é: Como elas são implementadas? Ou seja, o que acontece por trás quando incluímos ou buscamos um valor em um hash?

Apenas sei que sua implementação é diferente de estruturas encadeadas como pilhas, filas, listas, árvores binárias, etc.

1
  • Lembrando que isso é um dicionário. 'Hash' é uma metonímia. A implementação pode usar hash, mas também pode usar vetor, ou árvore, ou outra coisa. A implementação do dicionário Python muda de hash para árvore na versão 3.7 pois os valores das chaves passam a ser mantidos ordenados.
    – epx
    Commented 1/04/2020 às 12:12

2 Respostas 2

16

Cada coisa é uma coisa

Antes de mais nada, é importante entender que cada tipo de estrutura de dados possui uma aplicação mais específica. Então, dizer que hashes são mais rápidos que listas encadeadas é comparar laranjas com bananas.

Uma "tabela" é bastante eficiente para recuperar um elemento contido nela a partir de uma chave. Isso significa que é rápido encontrar uma agulha no palheiro se você tiver uma forma (hash) de identificar a agulha.

Entretanto, percorrer uma tabela inteiro é, em geral, menos eficiente que percorrer uma lista inteiro.

Além disso, somente uma lista baseada em vetores permite acessar elementos aleatórios de forma eficiente.

Hashes

São valores numéricos calculados por uma função a partir de um valor original de tamanho arbitrário. Existem vários algoritmos de hash, sendo que os melhores são os que emitem o menor número possível de hashes repetidos.

Por exemplo, a classe String do Java possui o seguinte método para gerar o hash code:

public int More ...hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

A documentação do método afirma que o hash é calculado da seguinte forma:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

Onde:

  • s[i]: i-ésimo caractere da String.
  • m: tamanho da String, em caracteres

Em resumo, gerar um hash é como gerar um ID numérico para o objeto.

Em Java, qualquer objeto pode ter uma implementação próprio do hashCode. Essa implementação deve considerar todos os atributos que identificam o objeto. É importante que objetos diferentes tenham hashes diferentes, tanto quanto possível.

Tabelas de Hashes

O número gerado por uma função hash pode ser usado para localizar facilmente um objeto numa espécie de "tabela".

Internamente, no Java por exemplo, essa tabela é um vetor. A cada posição do vetor é atribuído uma faixa de números. Seria como slots de uma prateleira.

Armazenando valores

Vamos supor que criamos um Hashtable e o vetor interno tem 10 posições (slots). Suponha ainda que adicionamos objetos e informemos chaves valores de hash variem de 1 a 100. Dessa forma, hashes que retornem valores de 1 a 10 serão colocados no primeiro slot, os que retornem valores de 11 a 20 no segundo slot e assim por diante.

Se adicionarmos um objeto (1) cujo hash da chave seja 20 ele será colocado no segundo slot. Se adicionarmos outro objeto (2) com chave de hash 45 ele será colocado quinto slot. Se adicionarmos ainda outro objeto (3) com chave de hash 15, ele será colocando também no segundo slot. Teríamos a seguinte estrutura de dados:

Slot 1: 
Slot 2: Objeto 1, Objeto 3
Slot 3: 
Slot 4: 
Slot 5: Objeto 2 
Slot 6: 
Slot 7: 
Slot 8: 
Slot 9: 
Slot 10: 

Note que cada item da tabela é também um tipo de vetor. Em Java, na classe Hashtable, isso é implementado através de uma lista ligada de objetos do tipo Entry (entrada).

Recuperando valores

Então, para recuperar um objeto, basta passar a chave para a tabela, esta calculará o hash e irá diretamente ao slot para recuperar o item.

Continuando o exemplo mais acima, se eu quisesse recuperar o Objeto 3, teria que passar a chave do mesmo. A tabela iria calcular o hash code da chave, que retornaria o valor 15. Hashes sempre retornam o mesmo valor para a mesma chave. Então com uma conta simples eu sei que o item será encontrado no segundo slot. Porém, como ainda temos uma lista de objetos, a tabela terá que percorrer a lista de entradas do slot 2 e verificar, um a um, qual é realmente o Objeto 3.

Implicações

As explicações acima possuem várias implicações:

  • Se houver muita colisão de hashes, muitos objetos acabarão caindo em poucos slots. havendo uma distribuição ruim, cada vez que for necessário recuperar um item a eficiência será ruim, pois será necessário percorrer a lista de elementos do slot e comparar um a um.
  • O tamanho interno da tabela precisa ser bem calculado, para que não haja muitos itens em cada slot, nem muitos slots vazios. Na implementação do Java, quando os slots começam a ficar cheios o Hashtable aumenta o número de slots e faz uma redistribuição.
  • No Java, o método que gera o hash pode ser chamado várias vezes, então é importante cuidar do desempenho e fazer cache do valor quando possível.
  • Dependendo da implementação da hash table, incluir muitos itens repetidamente pode ser bem ineficiente, já que haverá repetidas pausas para adicionar novos slots e redistribuir os elementos.

Diferentes tipos de implementações

Uma grande parte do que foi descrito acima é apenas um dos tipos possíveis de implementação de uso de hashes para recuperar valores.

Por exemplo, em Java, existe o TreeMap, uma "tabela" cujos hashes das entradas não ficam armazenadas num vetor, mas em uma árvore binária.

Há várias implicações nisso. Dependendo do balanceamento da árvore pode ser mais ou menos eficiente recuperar elementos. Comparando uma árvore balanceada com uma implementação de vetores com slots cheios a árvore iria ganhar.

Porém, já fiz algumas implementações que precisavam carregar árvores bem grandes em memória e o TreeMap foi muito mais eficiente.

2
  • Excelente resposta! Abordou todos os detalhes de forma simples.
    – user7261
    Commented 6/08/2014 às 11:22
  • Muito esclarecedor a explicação.
    – SoabTI
    Commented 26/10/2016 às 13:07
0

Uma tabela hash é uma estrutura que permite associar uma chave a um valor e, posteriormente, ter acesso ao valor a partir de sua chave associada. A chave é transformada por uma função em uma posição na tabela; usando sempre essa transformação, a localização de chaves na tabela é realizada rapidamente.

Em Java, essa estrutura de dados é implementada por objetos da classe Hashtable. Para manipular elementos na tabela hash, são usados os métodos put(), que armazena um par de objetos especificados na tabela, get(), que retorna o objeto valor associado ao objeto chave especificado, e remove(), que remove o par de objetos com a chave especificada. É também possível consultar se uma determinada chave existe na tabela, com o método containsKey(), ou se um determinado valor está presente na tabela associado a qualquer chave, com o método contains(). O número de pares de elementos na tabela pode ser obtido com o método size().

1
  • 1
    Eu na verdade não queria saber como usar, mas como isso é implementado por trás, ou seja, o que acontece quando buscamos ou incluímos um valor num hash.
    – user7261
    Commented 5/08/2014 às 18:40

Você deve fazer log-in para responder a esta pergunta.