Tabelas Hash

Prévia do material em texto

UNIVERSIDADE ESTADUAL DE MARINGÁ
DEPARTAMENTO DE INFORMÁTICA
ENGENHARIA DE PRODUÇÃO – SOFTWARE
TRABALHO DE ALGORITMO E ESTRUTURA DE DADOS
Professor: Carlos F. Scatambulo Costa
Alunos: Luan Veloso Rossini RA: 83156
 Vinicius Aguiar RA: 83354
Método da Divisão para chaves numéricas inteiras: O método da divisão consiste basicamente em realizar uma divisão inteira e tomar o seu resto.
Funções de Hash para chaves alfanuméricas: O método da divisão não pode ser usado diretamente quando as chaves são alfanuméricas; neste caso, temos antes que transformá-las em valores numéricos que poderão ser divididos por N. Uma forma simples de se transformar uma chave alfanumérica num valor numérico consiste em considerar cada caractere da chave como um valor inteiro (correspondente ao seu código ASCII) e realizar uma soma com todos eles.
Problema apresentado: Considere uma empresa cujos produtos são designados por uma chave alfanumérica no formato XXX-XX-XXXX, onde X pode ser uma letra [A .. Z] ou um número [0 .. 9]. Ex.: 3BC-52-D1E7. Crie uma função de hash para distribuir essas chaves numa tabela com 555 encaixes (índices) e um algoritmo (para essa função), preferencialmente em pseudocódigo. Explique, de forma clara e objetiva, como a função de hash foi criada e seu funcionamento, use exemplos para demonstrar.
Resolução:
O Algoritmo da Função Hash para Transformação de chaves alfanuméricas em valores numéricos para posterior divisão por N é dado por:
função ADH (CHAVE: caractere): inteiro; 
var
 I, SOMA : inteiro; 
 SOMA ← 0; 
 para I ← 1 até COMPRIMENTO(CHAVE) faça
 SOMA ← SOMA + ORD(CHAVE[I]); {ORD retorna o código ASCII} 
 fim para; {do parâmetro} 
 ADH ← (SOMA mod N) + 1; 
fim função ADH;
Algoritmo do problema:
função ADH (CHAVE: caractere): inteiro; 
var
 I, SOMA : inteiro; 
 SOMA ← 0; 
 para I ← 1 até COMPRIMENTO (CHAVE) faça
 SOMA ← SOMA + ORD(CHAVE[I]); {ORD retorna o código ASCII} 
 fim para; {do parâmetro} 
 ADH ← (SOMA mod N) + 1; 
fim função ADH;
inicio
 COMPRIMENTO ← 555; // tamanho da tabela
 função ADH (CHAVE);
 digite (CHAVE no formato XXX-XX-XXXX com os traços);
 leia (CHAVE);
 faça (CHAVE) ← UPCASE (CHAVE); // faz a chave ficar toda maiúscula
 resultado ← função ADH (CHAVE);
 mostra ← resultado; // o resultado recebe o valor da chave da função hash
fim algoritmo.