Tabela Hash

Alunos : Gustavo Jorge Zanin nºUSP 6392444

Guilherme Del Tedesco nºUSP 6549330

Sumário

Rápida revisão

O que é Tabela Hash

Função de transformação

Inserção

Remoção

Busca

Colisão

Fator de carga

Complexidade

Exercícios

O que é hash? Relembrando!!!!

Busca Sequencial

A chave de busca percorre cada elemento do vetor sequencialmente até encontrar o elemento desejado.

1. Melhor caso: O(1)

2. Pior caso: O(n)

O que é hash? Relembrando!!!!

Busca Binaria: Chave é comparada com registro que se encontra no meio do vetor ordenado. Se a chave for menor o registro estará na primeira metade do vetor, se for maior o registro estará na segunda metade do vetor.

Melhor caso O(1)

Pior caso O(log n)

O que é hash?

E se pudéssemos acessar o elemento desejado diretamente usando a chave de busca sem ficar percorrendo o vetor?

O que é Tabela hash?

É um método onde os registros armazenados em uma tabela são diretamente endereçados a partir de uma função de transformação que nada mais é que uma transformação aritmética feita sobre a chave de pesquisa.

Tabela hash também é conhecida como tabela de espalhamento.

Função de Transformação

É importante termos uma função de transformação que distribua os registros de forma uniforme entre as entradas da tabela

Função de transformação ideal:

Seja simples de ser computada.

Para cada chave de entrada qualquer uma das saídas possíveis é igualmente provável de ocorrer.

Exemplo:

H(K) = K mod M.

vetor de inteiros [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] ... [ 701]

hash =(chave % 701)

Como funciona a Tabela Hash

Imaginemos que temos chaves de numeros inteiros de 1 ate N. Podemos armazenar um registro de chave i,na posição i da tabela já que ela possui o tamanho necessário. Logo qualquer registro poderia ser imediatamente acessado a partir do valor da chave porém se tivermos uma tabela capaz de armazenar 97 chaves e cada chave tem 4 digitos entao teriamos 10.000 chaves e a função de transformação não pode ser 1 para1,originando as colisões.

Mesmo que o número de registros que devem ser armazenados seja muito menor que o tamanho da tabela, qualquer que seja a função de transformação,algumas colisões também irão ocorrer.

Como funciona

Colisão

Como a função de transformação pode ser qualquer coisa, existe a chance que uma função de transformação gere o mesmo valor de índice de vetor para diferentes valores de chave.

Ex: se a função de transformação é apenas o número de elementos do nome, registros como John Smith e Sandra Dee tem o mesmo número de letras,9. Essa situação é chamada Colisão e precisa ser tratada.

Tratamento de Colisão

Lista Encadeada:

Uma das formas de se resolver as colisões é simplesmente construir uma Lista Linear Encadeada para cada endereço da tabela. Assim todas as chaves com o mesmo endereço são encadeadas em uma lista linear.

Tratamento de Colisão Endereçamento Aberto:

Um endereçamento aberto são utilizados os lugares vazios na própria tabela para resolver a colisão. Quando uma chave chega endereçada para uma entrada na tabela já ocupada, uma sequência de localização alternativa é escolhida na tabela. A alternativa mais usada é o Hashing Linear

Se a i-ésima letra do alfabeto representada pelo número i e a função de transformação h(chave)= chave mod M para M=7 então para inserirmos a palavra LUNES teríamos:

h(L)=h(12)=5 h(E)=h(5)=5

H(U)=h(21)=0 h(S)=h(19)=5

H(N)=h(14)=0

Como funciona:Função de Transformação

Se as chaves não são números naturais, deve-se encontrar um modo de interpretá-las como números naturais .

int Transform(string s)

// pré: s chave a ser transformada

//pós: retorna s convertida para um número // pós: retorna s convertida para um número

// natural

// BASE = 128 (ASCII) ou 256 (ASCII Estendido)

k = 0;

for(i=0; i<s.length(); i++)

k = (k * BASE + s[i]) % P;

return k;

Como funciona:Função de Transformação

int h(char *chave, int p[], int m){

int i;

unsigned int soma = 0;

int comp = strlen(chave);

for (i = 0; i < comp; i++)

soma += (unsigned int) chave[i] * p[i];

return (soma % m);

}

void GeraPesos(int p[], int n) {int i;srand(time(NULL));for (i = 0; i < n; i++) p[i] = 1 + (int) (10000.0*rand() / RAND_MAX);}

O usos de pesos diferentes levam a funções de transformações diferentes

Como FuncionaInserção

Primeiramente tenho um vetor onde cada elemento é um registro com dados de pessoas. Esses registros contem nomes, endereços e um numero chave de identificação.

Quero inserir um novo registro nesse vetor

Como funcionaInserção

(Number%701)+1

(580625685 % 701) + 1 ?

Como funcionaInserção

Então o valor hash será usado para localizar o registro

Como funcionaInserção

Queremos inserir um novo registro com valor de hash 3

Como funcionaInserção

Quando ocorre colisão percorre-se o vetor até achar uma posição vazia

Como funcionaBuscando uma chave

1º Calcular o valor de hash

2ºConfira a chave do elemento do vetor com a chave procurada

Como funciona Buscando uma chave

Quando o item é encontrado, a informação será copiada para o local necessario.

Como funciona Remoção

Tambem podemos excluir um registro, mas nesse caso devemos marcar a posição do elemento que foi retirado para que a busca possa saber que existiu algum registro lá,caso contrário irá interferir nas buscas.

Pseudo-código

int Hash-Search(T,k)

// pré: tabela hash T[1..P], chave de busca k

// pós: retorna posição onde k foi achada ou zero c.c.

// H(.,,.) função de mapeamento

i = 0;

do

{ h = H(k,i);

if (T[h].key == k.key)

return h;

else

i = i + 1;

} while (i != P && T[h] não está livre);

return 0; // não encontrado

int Hash-Insert(T,k) // pré: tabela hash T[1..P], chave de busca k // pós: insere k em T, retornando posição de inserção // H(.,,.) função de mapeamento i = 0;

do

{ h = H(k,i);

if (T[h] está livre)

{ T[h] = k;

return h;

} else

i = i + 1;

} while (i != P);

cerr << “Error: hash table overflow”;

FATOR DE CARGA

É indicado por α (alpha) e é definido como o numero de elementos ocupados em uma tabela hash(n) dividido pelo numero total de elementos disponiveis(P).

O Fator de Carga é inversamente proporcional ao processo de recuperação e portanto,quanto maior for este fator,mais lenta é a recuperação do dado.

Com endereçamento aberto, 0 <= α <= 1

Com endereçamento encadeado, freqüentemente α>1

Complexidade

Lista encadeada

Endereçamento Aberto:

Melhor caso Caso médio Pior caso

Busca O(1) O (1+α) O(n)

inserção O(1) O(1+α) O(n)

Remoção O(1) O(1+α) O(n)

Melhor caso Caso médio Pior caso

Busca O(1) O (1) O(n)

inserção O(1) O(1) O(n)

Remoção O(1) O(1) O(n)

Exercícios

1- Quando se utiliza tabelas Hash pode ocorrer colisão. Quais são os métodos de tratamento de colisão?

Explique cada um deles com suas palavras. Dê exemplo

2-Demonstre a inserção das chaves 5, 28, 19, 15, 20, 33, 12, 17, 10 em uma tabela hash com colisões resolvidas por encadeamento. Seja a tabela com 9 posições, e seja a função hash h(k)=k mod 9.

Bibliografia

http://dcm.ffclrp.usp.br/~augusto/teaching/icii/Hash-Tables-Apresentacao.pdf

Nívio Ziviani, Projeto de Algoritmos com Implementações em Pascal e C, Terceira Edição, Editora Cengage Learning, 2010.