Funções e Tabelas de Hashing

Aluno: Breno Helfstein Moura
Supervisor: José Coelho de Pina

Contexto

Funções de hashing são amplamente utilizadas em aplicações do dia a dia. Suas aplicações são diversas, entre elas estão consistência de arquivos, sistemas distribuídos de banco de dados, encurtador de URL, verificação de isomorfismo em árvores, armazenamento de senhas, entre outros.

A ideia geral de uma função de hashing é associar um objeto de um espaço específico (uma string por exemplo) para um inteiro dentro de um intervalo positivo.

Motivação

Pretendo nesse trabalho detalhar sobre como funcionam os algoritmos de hashing e as estratégias para resolver colisões. Ter uma função de hashing bem distribuída ou uma boa estratégia de resolver colisões pode implicar em uma tabela de hashing mais eficiente, que usa melhor as capacidades da CPU. Pensando em grande escala, isso pode implicar em um menor uso de energia e economias para grandes empresas de software.

Proposta

Nesse trabalho pretendo abordar sobre os seguintes tópicos:

  1. Funções de hashing: Definir e discutir sobre algumas clássicas funções de Hashing.
  2. Tabelas de hashing: Discutir implementações e os detalhes de Tabelas de Hashing. Pretendo implementar e realizar experimentos, a fim de descobrir quais são as melhores implementações de tabelas de Hashing para cada aplicação. Pretendo discutir políticas de tratamento de colisões como chaining hashing, linear probing e double hashing. Pretendo começar com uma análise alto nível das implementações de hashing e então explicar o por que um algoritmo é superior a outro em alguma característica. As analises podem incluir análise assintótica dos algoritmos, caching, organização da memória, detalhes de implementação, entre outros.
  3. Aplicações: Pretendo falar sobre usos em criptografia, check-sum, rolling hashing (rabin karp), hashing para verificar isomorfismos em árvores entre outros.

Cronograma

Atividade Jan Fev Mar Abr Mai Jun Jul Ago Set Out Nov
Planejamento e escolha da bibliografia • • • •
Leitura mais detalhada da bibliografia • • • •
Elaboração do trabalho escrito e implementações das tabelas de hashing • • • • •