Aula 20 Tabela Hash.pdf

Prévia do material em texto

Tabela Hash
Professor:
Silvio Luiz Bragatto Boss
e-mail:
silvioboss@utfpr.edu.br
Universidade Tecnolo´gica Federal do Parana´ - UTFPR
Coordenac¸a˜o de Informa´tica - COINF
Curso de Engenharia de Computac¸a˜o
Disciplina de Estrutura de Dados I
Tabela Hash
Suma´rio
1 Tabela Hash
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Definic¸a˜o
Tambe´m conhecido como tabela de espalhamento ou tabela
de dispersa˜o;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Definic¸a˜o
Tambe´m conhecido como tabela de espalhamento ou tabela
de dispersa˜o;
Hashing e´ uma te´cnica que utiliza uma func¸a˜o h para
transformar uma chave k em um enderec¸o;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Definic¸a˜o
Tambe´m conhecido como tabela de espalhamento ou tabela
de dispersa˜o;
Hashing e´ uma te´cnica que utiliza uma func¸a˜o h para
transformar uma chave k em um enderec¸o;
O enderec¸o e´ usado para armazenar e recuperar registros;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Definic¸a˜o
Tambe´m conhecido como tabela de espalhamento ou tabela
de dispersa˜o;
Hashing e´ uma te´cnica que utiliza uma func¸a˜o h para
transformar uma chave k em um enderec¸o;
O enderec¸o e´ usado para armazenar e recuperar registros;
Ide´ia: particionar um conjunto de elementos em um nu´mero
determinado de classes.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Alguns Conceitos
A func¸a˜o h e´ chamada de func¸a˜o hash h(k) retorna o valor
hash de k;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Alguns Conceitos
A func¸a˜o h e´ chamada de func¸a˜o hash h(k) retorna o valor
hash de k;
Usado como enderec¸o para armazenar a informac¸a˜o cuja
chave e´ k;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Alguns Conceitos
A func¸a˜o h e´ chamada de func¸a˜o hash h(k) retorna o valor
hash de k;
Usado como enderec¸o para armazenar a informac¸a˜o cuja
chave e´ k;
k pertence a chave h(k).
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Outros Conceitos
A func¸a˜o hash e´ utilizada para inserir, remover ou buscar
um determinado elemento;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Outros Conceitos
A func¸a˜o hash e´ utilizada para inserir, remover ou buscar
um determinado elemento;
A func¸a˜o hash deve ser determin´ıstica, ou seja, resultar
sempre no mesmo valor para uma determinada chave.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Outros Conceitos
A func¸a˜o hash e´ utilizada para inserir, remover ou buscar
um determinado elemento;
A func¸a˜o hash deve ser determin´ıstica, ou seja, resultar
sempre no mesmo valor para uma determinada chave.
Colisa˜o
Ocorre quando a func¸a˜o hash produz o mesmo enderec¸o para
chaves diferentes.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Para um bom Hashing
Escolher uma boa func¸a˜o de hash - em func¸a˜o dos dados:
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Para um bom Hashing
Escolher uma boa func¸a˜o de hash - em func¸a˜o dos dados:
Distribui uniformemente os dados, na medida do poss´ıvel;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Para um bom Hashing
Escolher uma boa func¸a˜o de hash - em func¸a˜o dos dados:
Distribui uniformemente os dados, na medida do poss´ıvel;
Evita coliso˜es.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Para um bom Hashing
Escolher uma boa func¸a˜o de hash - em func¸a˜o dos dados:
Distribui uniformemente os dados, na medida do poss´ıvel;
Evita coliso˜es.
Estabelecer uma boa estrate´gia para tratamento de coliso˜es.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Nesta aula, utilizaremos uma te´cnica simples e muito utilizada
que produz bons resultados;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Nesta aula, utilizaremos uma te´cnica simples e muito utilizada
que produz bons resultados;
Para chaves inteiras, calcular o resto da divisa˜o (k%B), sendo
que o resto indica a posic¸a˜o de armazenamento:
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Nesta aula, utilizaremos uma te´cnica simples e muito utilizada
que produz bons resultados;
Para chaves inteiras, calcular o resto da divisa˜o (k%B), sendo
que o resto indica a posic¸a˜o de armazenamento:
k = valor da chave e,
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Nesta aula, utilizaremos uma te´cnica simples e muito utilizada
que produz bons resultados;
Para chaves inteiras, calcular o resto da divisa˜o (k%B), sendo
que o resto indica a posic¸a˜o de armazenamento:
k = valor da chave e,
B = tamanho do espac¸o de enderec¸amento.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Nesta aula, utilizaremos uma te´cnica simples e muito utilizada
que produz bons resultados;
Para chaves inteiras, calcular o resto da divisa˜o (k%B), sendo
que o resto indica a posic¸a˜o de armazenamento:
k = valor da chave e,
B = tamanho do espac¸o de enderec¸amento.
Para chaves tipo string, tratar cada caracter como um valor
inteiro (ASCII), soma´-los e pegar o resto da divisa˜o por B.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Nesta aula, utilizaremos uma te´cnica simples e muito utilizada
que produz bons resultados;
Para chaves inteiras, calcular o resto da divisa˜o (k%B), sendo
que o resto indica a posic¸a˜o de armazenamento:
k = valor da chave e,
B = tamanho do espac¸o de enderec¸amento.
Para chaves tipo string, tratar cada caracter como um valor
inteiro (ASCII), soma´-los e pegar o resto da divisa˜o por B.
B deve ser preferencialmente, primo.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
B um vetor de 7 elementos
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
B um vetor de 7 elementos
Inserc¸a˜o dos nu´meros 1, 5, 10, 20, 25, 24
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
B um vetor de 7 elementos
Inserc¸a˜o dos nu´meros 1, 5, 10, 20, 25, 24
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
B um vetor de 7 elementos
Inserc¸a˜o dos nu´meros 1, 5, 10, 20, 25, 24
1%7 = 1
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
B um vetor de 7 elementos
Inserc¸a˜o dos nu´meros 1, 5, 10, 20, 25, 24
5%7 = 5
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
B um vetor de 7 elementos
Inserc¸a˜o dos nu´meros 1, 5, 10, 20, 25, 24
10%7 = 3
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
B um vetor de 7 elementos
Inserc¸a˜o dos nu´meros 1, 5, 10, 20, 25, 24
20%7 = 6
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
B um vetor de 7 elementos
Inserc¸a˜o dos nu´meros 1, 5, 10, 20, 25, 24
25%7 = 4
Silvio Luiz Bragatto Boss UTFPR
TabelaHash LATEX
Tabela Hash
Tabela Hash
Exemplo
Seja:
B um vetor de 7 elementos
Inserc¸a˜o dos nu´meros 1, 5, 10, 20, 25, 24
24%7 = 3
COLISA˜O
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Como Tratar Coliso˜es??
Existem duas te´cnicas ba´sicas:
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Como Tratar Coliso˜es??
Existem duas te´cnicas ba´sicas:
Fechado
Te´cnicas de rehash para tratamento de coliso˜es
Permite armazenar um conjunto de informac¸o˜es de tamanho
limitado
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Como Tratar Coliso˜es??
Existem duas te´cnicas ba´sicas:
Fechado
Te´cnicas de rehash para tratamento de coliso˜es
Permite armazenar um conjunto de informac¸o˜es de tamanho
limitado
Aberto
Encadeamento de elementos para tratamento de coliso˜es
Permite armazenar um conjunto de informac¸o˜es de tamanho
potencialmente ilimitado
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Hashing Fechado
Uma tabela de ”itens”e´ utilizada para armazenar informac¸o˜es
Os elementos sa˜o armazenados na pro´pria tabela
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Hashing Fechado
Uma tabela de ”itens”e´ utilizada para armazenar informac¸o˜es
Os elementos sa˜o armazenados na pro´pria tabela
Colis~oes: aplicar te´cnicas de rehash
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Te´cnicas de rehash
Se posic¸a˜o h(k) esta´ ocupada (lembre-se de que h(k) e´ um
ı´ndice da tabela), aplicar func¸a˜o de rehash sobre h(k), que
deve retornar o pro´ximo ı´ndice livre.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Hashing Aberto
A tabela de ı´ndices, conte´m apenas ponteiros para uma lista
de elementos;
Quando ha´ colisa˜o, o elemento e´ inserido no ı´ndice como um
novo no´ da lista
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Hashing Aberto
Se as listas estiverem ordenadas, reduz-se o tempo de busca
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Vantagens
A tabela pode receber mais itens mesmo quando um ı´ndice ja´
foi ocupado;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Vantagens
A tabela pode receber mais itens mesmo quando um ı´ndice ja´
foi ocupado;
Desvantagens
Exige maior espac¸o para armazenamento das listas;
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX
Tabela Hash
Tabela Hash
Vantagens
A tabela pode receber mais itens mesmo quando um ı´ndice ja´
foi ocupado;
Desvantagens
Exige maior espac¸o para armazenamento das listas;
Listas longas implicam em muito tempo gasto na busca;
Se as listas estiverem ordenadas, reduz-se o tempo de busca.
Silvio Luiz Bragatto Boss UTFPR
Tabela Hash LATEX