Técnicas de Espalhamento (Hashtables)

 Direct Addressing
  •  Universo de chaves são números sequenciais de 0..N-1
  • Vetor com N posições é alocado para armazenar diretamente as chaves/info. Uma posição do vetor para cada chave.
  • Chaves definidas implícitamente pelo índice do vetor
  • :oD  Acesso rápido, implementação simples
  • :o(  Desperdício de espaço  

Hashtable : Estrutura de dados que implementa eficientemente um conjunto dinâmico suportando as três operações básicas de um dicionário ( inserção, busca e remoção). Implicitamente, uma tabela de espalhamento (hashtable) define um algoritmo de mapeamento entre o conjunto de chaves possíveis e seu conjunto de células ou slots (posições internas na tabela).

Suposição: Simple Uniform Hashing - Cada chave é vinculada a uma célula da hashtable independentemente do resultado da vinculação da chave anterior.

Load Factor : razão entre número de chaves (N) e tamanho do células da hashtable (m).  a = N/m

Chaves são Números Naturais
Vamos supor que chaves são sempre números Naturais. Quando chaves forem cadeias de caracteres (strings), as mesmas podem ser mapeadas em números Naturais por diversas técnicas, destacando-se:

Técnicas de Open Addressing (load factor <1)

 Division
  • h(k) = k mod m
      k é a chave (número natural), m é um número primo que representa número de células da hashtable, e h(k) é a célula onde a chave k será armazenada. 0 <= h(k) <= m-1
  • Técnica básica combinada com todas as demais técnicas.
  • :o( Problema são as colisões e remoção.

 Multiplication
  • h(k) = k' mod m
      k' é selecionado como um conjunto p de dígitos (posição média) do valor resultante de k*k
  • :o( Problema são as colisões e remoção.

 Folding
  • h(k) = k' mod m
      k' é selecionado como um somatório de agrupamentos de dígitos de k
  • :o( Problema são as colisões e remoção.

 

Técnicas de Resolução de Colisão

Linear Probing

 Linear Probing
  • h(k) = (h'(k) + a*i ) mod m
  • :o( Problemas: remoção,...
  • a é uma constante que representa tamanho do salto (ex. + simples a=1)
  • i é número natural incremental utilizado a cada resolução de colisão (pode começar de 1).
  • Não resolve o problema da colisão.

 Quadratic Probing
  • h(k,i) = (h'(k) + a*i + b*i*i) mod m
  • a e b são constantes que representam tamanho do salto (ex. + simples a=0 e b=1)
  • i é número natural incremental utilizado a cada resolução de colisão (melhor começar de 2)
  • :o( Problema é remoção.

 Double Hashing
  • h(k,i) = ( h1(k)+i*h2(k) ) mod m
    h1(k) = k mod m
    h2(k) = 1 + (k mod m')
  • m' é um outro número primo menor que m (m' < m)
  • :o( Problema é remoção.
  • Instância de RANDOM HASHING (computacionalmente inviável)
  • Minimiza primary clustering.

 External Chaining
  • Em caso de colisão utilizar estrutura adicional para armazenar chaves: lista ligada, árvore, heap, etc
  • Resolve o problema da remoção
  • suporta load factor > 1

 Coalesced Chaining
  • Associar a cada posição da tabela HASH uma variável de status ( FREE|OCCUPIED|LINKED) e um campo next (índice para outra posição quando status==LINKED)
  • A cada colisão utilizar campo next para continuar a busca de chave na hashtable
  • Inserção em posição FREE muda status para OCCUPIED
  • Inserção em posição OCCUPIED muda status para LINKED, onde campo next recebe valor do índice efetivo onde chave que sofreu colisão foi armazenada.
  • Resolução de colisão: 1 estratégia é buscar posições livres do fim para o começo da tabela
  • Otimização: Alocar p posições extras na tabela hash mas continua com h(k) = h'(k) mod m, onde tamanho da tabela = p + m

 

Perfect Hashing