hashing

9.1 Recapitulação
Até agora vimos basicamente dois tipos de estruturas de dados para o armazenamento flexível de dados: Listas e Árvores.
Cada um desses grupos possui muitas variantes.
As Listas são simples de se implementar, mas, com um tempo médio de acesso

T = n/2, são impraticáveis para grandes quantidades de dados.
Em uma lista com 100.000 dados, para recuperar 3 elementos em seqüência faremos um número esperado de 150.000 acessos a nodos.
Listas são ótimas porém, para pequenas quantidades de dados.
As Árvores são estruturas mais complexas, mas que possuem um tempo médio de acesso T= logGn, onde G = grau da árvore.
A organização de uma árvore depende da ordem de entrada dos dados.
Para evitar a deterioração, há modelos de árvores que se reorganizam sozinhas. As principais são AVL e Árvore B.
9.2 Hashing: Visão Geral
É uma forma extremamente simples, fácil de se implementar e intuitiva de se organizar grandes quantidades de dados.
Permite armazenar e encontrar rapidamente dados por chave.
Possui como idéia central a divisão de um universo de dados a ser organizado em subconjuntos mais gerenciáveis
Possui dois conceitos centrais:
Tabela de Hashing:Estrutura que permite o acesso aos subconjuntos.
Função de Hashing: Função que realiza um mapeamento entre valores de chaves e entradas na tabela.
Possui uma série de limitações em relação às árvores:
Não permite recuperar/imprimir todos os elementos em ordem de chave nem tampouco outras operações que exijam seqüência dos dados.
Não permite operações do tipo recuperar o elemento com a maior ou a menor chave.
9.2.1 Hashing: Introdução
Idéia geral: Se eu possuo um universo de dados classificáveis por chave, posso:
Criar um critério simples para dividir este universo em subconjuntos com base em alguma qualidade do domínio das chaves.
Saber em qual subconjunto procurar e colocar uma chave.
Gerenciar estes subconjuntos bem menores por algum método simples.
Para isso eu preciso:
Saber quantos