1

Classificação e Pesquisa

Tabelas HashHashing

Prof. Rodrigo Rochaprof.rodrigorocha@yahoo.com http://www.bolinhabolinha.com

Onde Estamos Ementa

• Pesquisa de DadosSeqüencialBinária

• Métodos de ordenaçãoseleção e trocadistribuição inserção Intercalação

• ÁrvoresPesquisaBináriaAVLPatrícia

• B-Tree• Tabelas hash

Estática e Dinâmica

2

Hashing sort

Não é um algoritmo de ordenação Organiza os dados conforme uma tabela de

mapeamento Método eficiente e veloz de busca e

organização baseado em funções matemáticas

• função comum de hash: módulo• existem outras, como fórmulas matemáticas

possui colisões• dois valores são mapeados para o mesmo lugar

Hashing sort

Função de EspalhamentoMapeamento de valor do elemento com índice do vetor

3

Hashing sort

Resolvendo colisão através de lista. cada “slot” da tabela hash contém uma lista ligada com todos os valores do mapeamento daquela chave.

Hashing sort Exemplo

• utilizando “resto” da divisãoporque o “mod” é uma operação rápida

• Lista de valores 10, 12, 20, 23, 27, 30, 31, 39, 42, 44, 45, 49, 53, 57, 60

• Fazendo hashing em um vetor de 15 elementos• elemento mod tamanho_do_vetor

0 1 2 3 4 5 6 7 8 9 10 11 12 13 1430,45,60

31 49 20 23,43

39 10 12,27,4257

44

4

Hashing sort Criando uma tabela hash em java

• Hashtable numbers = new Hashtable(); numbers.put("one", new Integer(1)); numbers.put("two", new Integer(2)); numbers.put("three", new Integer(3));

Para recuperar um número:• Integer n = (Integer)numbers.get("two");• if (n != null) {

System.out.println("two = " + n); }

Hashing sort Complexidade

• Usando o valor do elemento como índice do vetor ordenação em O(n) procura em O(1)

5

Hashing sort Exemplo de tabela hash

• http://cs.brynmawr.edu/cs206/WorkshopApplets/Chap11/Hash/Hash.html

Hashing sort

Exercícios• a-) Crie um hash em um vetor de 5 elementos

utilizando a seguinte lista de valores: 640, 972, 43, 514

• b-) Crie um hash em um vetor de 10 elementos utilizando a seguinte lista de valores: 990, 910, 862, 618, 58, 0, 953, 682, 258, 698

• c-) Crie um hash em um vetor de 30 elementos utilizando a seguinte lista de valores: 661,151, 783, 901, 841, 37, 129, 370, 852, 763, 81,

261, 896, 657, 568

6

Hashing sort

Exercício• Faça uma pesquisa e comente onde tabelas hash

são utilizadas e com que finalidade?

• Por que hash é importante para criptografia ?

• Implemente uma tabela hash em qualquer linguagem de programação que você conheça.

Bibliografia

Livro texto• ZIVIANI, Nivio. Projeto de Algoritmos : com implementação em Pascal

e C.. 2ª ed. São Paulo: Pioneira Thomson Learning, 2004.• VELOSO, Paulo A. S.. Estrutura de Dados. 1ª ed. São Paulo: Campus,

1983.• CORMEN, Thomas H. Algoritmos : teoria e prática. 1ª ed. Rio de Janeiro:

CAMPUS, 2002.

Complementar• SCHILDT, Herbert. C Completo e Total. 3ª ed. São Paulo: Pearson

Education, 2005.• CELES, Waldemar; CERQUEIRA, Renato. Introdução a Estruturas de

Dados : com técnicas de programação em C. 4ª ed. Rio de Janeiro: Elsevier, 2004

• WIRTH, Niklaus. Algoritmos e Estruturas de Dados. 1ª ed. Rio de Janeiro: LTC, 1989

• TENENBAUM, Aaron M; SOUZA, Tereza Cristina Félix de. Estruturas de Dados usando C. 1ª ed. São Paulo: Makron Books,1995.