Suponha que queiramos projetar um sistema para armazenar registros de funcionários digitados em números de telefone. E queremos que as seguintes consultas sejam realizadas de forma eficiente: 
 

  1. Insira um número de telefone e as informações correspondentes.
  2. Pesquise um número de telefone e obtenha as informações.
  3. Exclua um número de telefone e informações relacionadas.

Podemos pensar em usar as seguintes estruturas de dados para manter informações sobre diferentes números de telefone. 
 

  1. Array de números de telefone e registros.
  2. Lista vinculada de números de telefone e registros.
  3. Árvore de pesquisa binária equilibrada com números de telefone como chaves.
  4. Tabela de acesso direto.

Para arrayes e listas vinculadas , precisamos pesquisar de maneira linear, o que pode ser caro na prática. Se usarmos arrayes e mantivermos os dados classificados, um número de telefone pode ser pesquisado em tempo O (Logn) usando a Pesquisa Binária, mas as operações de inserção e exclusão tornam-se caras, pois temos que manter a ordem classificada. 
 

Com a árvore de pesquisa binária balanceada , obtemos tempos moderados de pesquisa, inserção e exclusão. Todas essas operações podem ser garantidas no tempo O (Logn). 

Outra solução que se pode pensar é usar uma tabela de acesso direto onde fazemos um grande array e usamos números de telefone como índice no array. Uma entrada na array é NIL se o número de telefone não estiver presente, caso contrário, a entrada da array armazena o ponteiro para os registros correspondentes ao número do telefone. Em termos de complexidade de tempo, esta solução é a melhor entre todas, podemos fazer todas as operações em tempo O (1). Por exemplo, para inserir um número de telefone, criamos um registro com detalhes de um determinado número de telefone, usamos o número de telefone como índice e armazenamos o ponteiro para o registro criado na tabela. 
Esta solução tem muitas limitações práticas. O primeiro problema com esta solução é que o espaço extra necessário é enorme. Por exemplo, se o número de telefone tiver n dígitos, precisamos de O (m * 10 n) espaço para a tabela onde m é o tamanho de um ponteiro para registrar. Outro problema é que um número inteiro em uma linguagem de programação pode não armazenar n dígitos. 

Devido às limitações acima, a Tabela de acesso direto nem sempre pode ser usada. Hashing é a solução que pode ser usada em quase todas essas situações e tem um desempenho extremamente bom em comparação com as estruturas de dados acima, como Array, Linked List, Balanced BST na prática. Com o hashing, obtemos O (1) tempo de pesquisa em média (sob suposições razoáveis) e O (n) no pior caso. 

O hash é uma melhoria em relação à Tabela de acesso direto. A ideia é usar a função hash que converte um determinado número de telefone ou qualquer outra chave em um número menor e usa o número pequeno como índice em uma tabela chamada hash table. 

Função hash : uma função que converte um determinado grande número de telefone em um pequeno valor inteiro prático. O valor inteiro mapeado é usado como um índice na tabela hash. Em termos simples, uma função hash mapeia um grande número ou string para um pequeno inteiro que pode ser usado como índice na tabela hash. 
Uma boa função hash deve ter as seguintes propriedades 
1) Eficientemente computável. 
2) Deve distribuir uniformemente as chaves (cada posição da mesa é igualmente provável para cada chave) 

Por exemplo, para números de telefone, uma função hash incorreta é usar os três primeiros dígitos. Uma função melhor é considerar os três últimos dígitos. Observe que esta pode não ser a melhor função hash. Pode haver maneiras melhores. 

Tabela de hash : uma array que armazena ponteiros para registros correspondentes a um determinado número de telefone. Uma entrada na tabela hash é NIL se nenhum número de telefone existente tiver um valor de função hash igual ao índice da entrada. 

Tratamento de colisões : como uma função hash nos dá um pequeno número para uma chave grande, é possível que duas chaves resultem no mesmo valor. A situação em que uma chave recém-inserida mapeia para um slot já ocupado na tabela hash é chamada de colisão e deve ser tratada usando alguma técnica de tratamento de colisão. A seguir estão as maneiras de lidar com as colisões: 
 

  • Encadeamento: A ideia é fazer com que cada célula da tabela de hash aponte para uma lista vinculada de registros que possuem o mesmo valor da função de hash. O encadeamento é simples, mas requer memória adicional fora da mesa.
  • Endereçamento aberto: no endereçamento aberto, todos os elementos são armazenados na própria tabela hash. Cada entrada da tabela contém um registro ou NIL. Ao procurar um elemento, examinamos os slots da tabela um por um até que o elemento desejado seja encontrado ou fique claro que o elemento não está na tabela.

<iframe allow="autoplay; encrypted-media" allowfullscreen="" frameborder="0" height="374" src="https://www.youtube.com/embed/wWgIAphfn2U?feature=oembed" width="665"></iframe>

Próximas postagens:  
Encadeamento separado para tratamento de colisão 
Endereçamento aberto para tratamento de colisão 

Referências:  
MIT Video Lecture 

Palestra em vídeo do IITD 

“Introdução aos Algoritmos”, Segunda Edição de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein . 

http://www.cs.princeton.edu/~rs/AlgsDS07/10Hashing.pdf 

http://www.martinbroadhurst.com/articles/hash-table.html 

Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.