Estudo e Implementação de Tabelas Hashing

PS GRADUAO EM MODELAGEM MATEMTICA E COMPUTACIONAL - CEFET-MG

ALGORITMOS E ESTRUTURAS DE DADOS - PROF. DRA. CRISTINA D. MURTA

TRABALHO PRTICO No 2

IMPLEMENTAO, EXECUO, TESTE E MEDIO EM TABELAS HASHING

Danilo Antnio Leite [email protected]

Configuraes do Ambiente Utilizado para os Testes

Todo o desenvolvimento dos algoritmos e os testes foram realizados em um computador com as seguintes configuraes: . Dell Vostro 3450 (laptop) . Processador Inter(R) Core(TM) i5-2450M CPU 2.50 GHz . Memria RAM: 6 GB . Sistema Operacional: Windows 7 Professional 64 Bits Service Pack 1 . HD: 605 GB na partio Windows Os cdigos foram implementados utilizando NetBeans IDE 8.0.2 e linguagem Java (JDK 1.8). A execuo dos testes dos algoritmos em Java tambm foi realizada com a utilizao do ambiente NetBeans. Projeto de um TAD Dicionrio para armazenar uma base de dados de URLs O TAD dever possuir as seguintes caractersticas bsicas: Inicializar tabela: inicializao da tabela vazia. Inserir URL: insere uma URL na tabela. Pesquisar URL: realiza busca de uma URL na tabela, retornando o elemento buscado em caso de sucesso e o nmero de comparaes necessrio para encontr-lo; em caso de insucesso retornar o nmero de comparaes necessrios para descobrir o resultado. Importar dados de um arquivo de URLs: insere N URLs na tabela a partir de um arquivo texto fornecido. Relato do Experimento 1. Implementao da Tabela Hashing com Listas Encadeadas a) O tamanho da tabela adotado para o projeto foi de 1071 posies, que corresponde a aproximadamente 10% da quantidade de registros a ser inserida nesta tabela, conforme recomendado pelos referenciais tericos sobre o assunto. Neste caso inicialmente estima-se uma quantidade mdia esperada de 10 colises por posio na tabela. Os elementos sero armazenadas em listas encadeadas vinculadas a cada posio da tabela hash. Em caso de coliso os elementos sero armazenados em uma lista encadeada vinculada posio de coliso. A insero de novos elementos ser realizada sempre na primeira posio da lista encadeada para evitar percorrer a lista no momento da insero.

A construo foi iniciada pela lista encadeada. Primeiramente foi implementado o elemento de lista atravs da classe ListElement.java. Em seguida foi criada uma estrutura de lista encadeada atravs da classe ListSet.java utilizando o elemento criado anteriormente, e definindo as operaes necessrias ao funcionamento da lista, em especial a operao de incluso add que responsvel por inserir um elemento (URL) na primeira posio da lista encadeada. Foram realizados em seguida os testes de funcionamento dessa estrutura e acrescentadas operaes para exibio de resultados e outros dados necessrios. Algum cdigo excedente (alm do essencialmente proposto neste trabalho) teve que ser gerado para fins de testes, visibilidade e monitoramento de resultados. Estes foram utilizados durante os testes e a fase de construo dos programas, por isso fazem parte da documentao anexa que integra este relatrio ao final do documento. As estruturas foram adicionadas gradativamente e todas foram testadas individualmente antes de se partir para a prxima etapa. Decidiu-se por incluir uma classe FindResults.java para facilitar a obteno de resultados (nmero de comparaes na lista, retorno da busca - encontrado ou no encontrado, posio da tabela para fins de monitoramento e testes) de uma pesquisa, pensando em extrair posteriormente as estatsticas solicitadas. Finalmente foi implementada a estrutura hashTableListSet.java que disponibiliza as funes do TAD proposto: inicializao da lista, funo hash, incluso em nvel de tabela hash, resultados de pesquisa, estatsticas, alm de exibio de todo o contedo da tabela e das quantidades de URLs armazenadas por posio. Esta ltima funcionalidade foi utilizada para gerao de dados para os grficos de distribuio que foram gerados para facilitar a avaliao da eficcia da funo hash utilizada. Outras funes complementares tiveram que ser implementadas: leitura e importao de dados de arquivo texto (URLs), sorteio de N URLs para realizao de pesquisas, ordenao de vetor de inteiros para fins de eficcia ao extrair dados do arquivo para sorteio e clculo das estatsticas de comparaes. A classe txtFile.java contm as funes para importar os dados do arquivo e incluir na tabela hash (utilizando funes das classes hashTableListSet.java (utiliza tambm hashTableOpenAdress.java que trata de hashing com endereamento aberto linear). Para a funo hash foram consideradas as seguintes variveis e caractersticas para montagem do resultado: . Tamanho da URL; . O cdigo numrico correspondente a cada caractere da URL; . A posio de cada caractere da URL; . O tamanho projetado da tabela hash; . Utilizao de operaes para gerao de um inteiro longo: soma acumulada, potenciao, diviso; . Aplicao do resto da diviso para gerar um valor final dentro dos limites esperados. Finalmente, aps alguns testes e pequenos ajustes a verso final do algoritmo da funo hash ficou definido como segue:

public int hash(String url){ int h = -1; // retorno da funo hash para posicionar na tabela int n = url.length(); // tamanho da string if (n == 0) return h; long codUrl = 0; for(int i = 0; i < n; i++){ codUrl = (long) (codUrl + url.charAt(i)*Math.pow(2, n-i)/(i+1)); //gera um cdigo inteiro baseado nos caracteres da string } codUrl = (long) codUrl/n; h = (int) (codUrl % TABLE_SIZE); // o resultado do hash o codUrl dividido pelo tamanho da tabela hash return h; } Ao fazer os primeiros testes utilizando a verso inicial da funo hash, ao inserir as 10696 URLs na tabela hash com listas encadeadas percebeu-se uma distribuio irregular, com elevado nmero de colises em algumas posies da tabela conforme pode ser visualizado no grfico a seguir:

Nesta situao percebe-se claramente que a funo Hash utilizada no gerou uma boa distribuio das URLs, pois houve nmero elevado de colises em determinadas posies. O maior nmero de colises obtido para uma mesma posio foi 472 neste caso. Houve ainda 7 posies zeradas (sem nenhuma URL). Diante desse cenrio ficou evidente a necessidade de se alterar ou substituir a funo Hash.

0

50

100

150

200

250

300

350

400

450

500

0 200 400 600 800 1000 1200

Distribuio das URLs (quantidades) por posio da Tabela Hash - Resultado InsatisfatrioQtd. URLs

Posio Hash

Em seguida foi realizado um ajuste na funo hash e resultados melhores foram obtidos. Desta vez o nmero mximo de colises em uma mesma posio foi igual a 43. Houve 2 posies zeradas. Nesse caso houve uma melhor distribuio das URLs na tabela hash. A distribuio no foi uniforme (perfeita) porm o resultado foi satisfatrio comparado primeira tentativa. A tabela a seguir apresenta a viso da distribuio da quantidade de URLs por posio da tabela hash com listas encadeadas, aps o procedimento de insero das 10696 URLs:

A seguir exibido o resultado da distribuio aps o teste utilizando a mesma funo hash da situao anterior, mas a massa de dados contendo as URLs foi ajustada. Como havia cdigo HTML em muitas URLs do arquivo original, diversas URLs ficaram com tamanho maior e informaes excedentes e redundantes por conta do cdigo HTML, gerando maior nmero de colises. Utilizando o arquivo contendo somente as URLs "enxutas", foi possvel perceber uma melhora significativa na distribuio das URLs nas posies da tabela hash. Esse ltimo resultado foi adotado como referncia para os testes subsequentes e a funo hash foi considerada satisfatria para os propsitos deste trabalho.

0

5

10

15

20

25

30

35

40

45

50

0 200 400 600 800 1000 1200

Distribuio de URLs (quantidades) na tabela Hash com Listas Encadeadas

Qtd. URLs

Posio Hash

A seguir apresentada uma viso parcial dos dados aps a insero na tabela hash com listas encadeadas. Os dados na ntegra podem ser visualizados atravs da execuo do programa: run: Linha 0 ==> 1.[www.museudouna.com.br];2.[www.juicysantos.com.br];3.[www.danimaalouli.com.br];4.[revistadm.com.br];5.[idgnow.uol.com.br];6.[flip.correiodopovo.com.br];7.[espacodocasamento.com.br];8.[carmagazine.uol.com.br];9.[arvitec.com.br]; Linha 1 ==> 1.[www.habilveiculos.com.br];2.[www.blogdacomunicacao.com.br];3.[the-gimp.softonic.com.br];4.[globo.com.br];5.[css.correiobraziliense.com.br];6.[cinples.blogspot.com.br]; Linha 2 ==> 1.[www.sistemainfo.com.br];2.[www.fortaleza.ce.gov.br];3.[static.ebit.com.br];4.[sovacodesapo.blogspot.com.br];5.[openx.ambientebrasil.com.br];6.[knorte.com.br];7.[img4.reembolsocentral.com.br];8.[facebuug.blogspot.com.br];9.[embalando.com.br];10.[dpaonline.dpaschoal.com.br];11.[clubedaboacompra.com.br]; Linha 3 ==> 1.[www.schabbach.com.br];2.[www.nanavasconcelos.com.br];3.[www.lojatim.com.br];4.[www.faetec.rj.gov.br];5.[www.arnaldoantunes.com.br];6.[corag.com.br]; Linha 4 ==> 1.[www.visitesaothome.com.br];2.[www.rapidssl.com.br];3.[www.amil.com.br];4.[virtualbooks.terra.com.br];5.[siteforte.com.br];6.[parqueestadualcamposdojordao.vilabol.uol.com.br];7.[metodistalondrina.com.br];8.[italo.com.br];9.[img6.clickjogos.uol.com.br];10.[eros.com.br];11.[assineglobocondenast.com.br];12.[apachecompany.com.br]; Linha 5 ==> 1.[www.iancalcados.com.br];2.[www.ebit.com.br];3.[www.dotstore.com.br];4.[www.delicias1001.com.br];5.[www.climatempo.com.br];6.[www.aspersul.com.br];7.[recife.jovempanfm.com.br];8.[guiaribeiraopreto.com.br];

.

.

. Linha 1068 ==> 1.[www.powermemory.com.br];2.[www.guiaeventosefestas.com.br];3.[www.flowerfishaquarios.com.br];4.[www.esmape.com.br];5.[www.clicarolamentos.com.br];6.[www.cbss.com.br];7.[www.bradescoprime.com.br];8.[vinhonline.com.br];9.[valoronline.com.br];10.[sopapel.com.br];11.[posic.slw.com.br];12.[euqueroquero.com.br]; Linha 1069 ==> 1.[www.webpav.com.br];2.[www.vilaguaiamu.com.br];3.[www.publicidadenainternet.com.br];4.[www.proserinstituto.com.br];5.[www.mesaoval.com.br];6.[www.cartamaior.com.br];7.[www.camisetaviajante.com.br];8.[www.abihrj.com.br];9.[tv.canaldoonibus.com.br];10.[senergen.com.br];11.[santaros

0

5

10

15

20

25

0 200 400 600 800 1000 1200

Distribuio de URLs (quantidades) na tabela Hash com Listas EncadeadasQtd. URLs

Posio Hash

aimoveis.com.br];12.[pandabrinquedos.com.br];13.[news.autoz.com.br];14.[loja.trisbrasil.com.br];15.[dicasdeingrid.blogspot.com.br]; Linha 1070 ==> 1.[www.summerlife.com.br];2.[www.radiosantacruzfm.com.br];3.[www.moreirajr.com.br];4.[www.grandesmensagens.com.br];5.[www.demaria.com.br];6.[www.conexacomunicacao.com.br];7.[tecnologia.ig.com.br];8.[personare.com.br];9.[gazetaderibeirao.rac.com.br];10.[fotos.gruporscom.com.br];11.[cursocpa.com.br];12.[canilsetimadinastia.com.br];

b) A seguir so apresentados alguns resultados da anlise estatstica dos dados cadastrados na tabela hash com listas encadeadas. Foram sorteadas 1000 URLs da base e em seguida foram realizadas buscas para cada uma delas, e ao final foram obtidas as estatsticas contendo os seguintes dados referentes ao nmero de comparaes para encontrar as URLs: menor valor, maior valor, mdia e mediana para o nmero de comparaes. Estatsticas para 1000 URLs CADASTRADAS Teste 1 Teste 2 Teste 3 Teste 4 Menor Valor: 1 Maior Valor: 20 Mdia: 6,083000 Mediana: 6,000000

Menor Valor: 1 Maior Valor: 20 Mdia: 5,992000 Mediana: 6,000000



Teste 5 Teste 6 Teste 7 Teste 8 Menor Valor: 1 Maior Valor: 17 Mdia: 5,923000 Mediana: 5,000000








c) A seguir so apresentados resultados da anlise estatstica dos dados NO cadastrados na tabela hash com listas encadeadas. Foram sorteadas 1000 URLs da base e em seguida estas foram alteradas em 1 caractere. Posteriormente foram realizadas buscas para cada uma delas, e ao final foram obtidas as estatsticas contendo os seguintes dados referentes ao nmero de comparaes necessrios para identificar que as URLs no existem na tabela hash: menor valor, maior valor, mdia e mediana para o nmero de comparaes.

Estatsticas para 1000 URLs NO CADASTRADAS (ALTERADAS) Teste 1 Teste 2 Teste 3 Teste 4 Menor Valor: 3 Maior Valor: 22 Mdia: 10,048000 Mediana: 10,00000












d) Fazer uma tabela com os resultados e comparar com a teoria. Analisando os dados abaixo percebe-se que o melhor caso (menor valor) em todos os testes resultou em 1 comparao somente. O valor da mediana entre 5 e 6 mostra que para mais da metade dos elementos amostrados o nmero de colises foi abaixo da mdia esperada de 10 colises. A mdia dos valores em torno de 6 tambm refora a ideia de um nmero de colises um pouco abaixo do esperado para os dados amostrados. O pior caso (maior valor) nos permite visualizar o nmero mximo de colises na mesma posio da tabela hash, o que sugere uma boa distribuio dos dados.

Estatsticas de 1000 URLs Cadastradas - Nmero de Comparaes

T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12

Menor Valor 1 1 1 1 1 1 1 1 1 1 1 1

Maior Valor 20 20 17 22 17 21 19 19 19 22 19 18

Mdia 6,083 5,992 6 5,931 5,923 6,224 5,892 5,876 6,165 6,076 6,027 5,971

Mediana 6 6 6 5 5 6 5 6 6 6 6 6

Para a pesquisa de URLs no cadastradas o menor valor corresponde s posies onde houve menor nmero de colises. O maior valor representa o nmero mximo de colises dentro da amostra, e mdia bem prxima da mdia estimada e esperada e a mediana com valor fixo igual a 10 mostra que apesar da distribuio no ser uniforme (perfeita), esse valor sugere uma boa distribuio dos dados como j mostrado anteriormente no grfico de distribuio.

Estatsticas de 1000 URLs NO Cadastradas - Nmero de Comparaes

T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12

Menor Valor 3 2 2 2 3 2 2 2 2 2 2 2

Maior Valor 22 21 21 22 22 22 21 22 22 22 22 22

Mdia 10,05 10,1 10,1 9,953 9,959 9,874 9,996 10,016 10,008 9,882 9,926 10,062

Mediana 10 10 10 10 10 10 10 10 10 10 10 10

A seguir so exibidos os grficos para melhor visualizao dos resultados

0

5

10

15

20

25

1 2 3 4

Estatsticas de 1000 URLs NO Cadastradas

A seguir so exibidos os grficos para melhor visualizao dos resultados

5 6 7 8 9 10 11 12

Estatsticas de 1000 URLs NO Cadastradas Nmero de Comparaes

A seguir so exibidos os grficos para melhor visualizao dos resultados apresentados:

12

Menor Valor

Maior Valor

Mdia

Mediana

Estatsticas de 1000 URLs NO Cadastradas

2. Implementao da Tabela Hashing com Endereamento Aberto a) O tamanho da tabela adotado para o hashing com endereamento aberto foi de 21392 posies, que corresponde exatamente ao dobro da quantidade de registros a ser inserida nesta tabela, conforme recomendado pelos referenciais tericos sobre o assunto. A estrutura dessa tabela composta basicamente de um vetor de Strings, da funo hash e da operao de incluso, alm de propriedades auxiliares e os mtodos de pesquisa e estatsticas. Em caso de coliso no momento da incluso de uma URL, ser procurada a prxima posio livre para incluso. A construo foi facilitada devido ao aproveitamento das estruturas geradas anteriormente, sendo necessrio algumas adaptaes para trabalhar com o vetor de Strings. Os mtodos e a estrutura so similares aos gerados anteriormente para a tabela hash com listas encadeadas, porm os cdigos foram adaptados para trabalhar com a nova estrutura. A classe responsvel pela estrutura de endereamento aberto hashTableOpenAdress.java. A funo hash ir diferir da funo utilizada anteriormente somente pelo tamanho da tabela (neste caso 21392), que utilizado para limitar os valores finais gerados pela funo. Foram realizados testes com valores inferiores mas os resultados no se mostraram satisfatrios, pois o nmero de dados agrupados aumentaram consideravelmente em relao configurao atual. A seguir apresentada a verso final da funo hash utilizada, sendo que o valor da constante TABLE_SIZE neste caso foi configurado para 21392: public int hash(String url){ int h = -1; // retorno da funo hash para posicionar na tabela int n = url.length(); // tamanho da string if (n == 0) return h; long codUrl = 0; for(int i = 0; i < n; i++){ codUrl = (long) (codUrl + url.charAt(i)*Math.pow(2, n-i)/(i+1)); //gera um cdigo inteiro baseado nos caracteres da string } codUrl = (long) codUrl/n; h = (int) (codUrl % TABLE_SIZE); // o resultado do hash o codUrl dividido pelo tamanho da tabela hash return h; }

A seguir so exibidos dados parciais das URLs aps a incluso das mesmas na tabela hash com endereamento aberto: . . . Linha 22 ==> bdp3100.caldeiraodeofertas.com.br Linha 23 ==> lenteszeiss.com.br Linha 24 ==> www.anfiles.blogger.com.br Linha 25 ==> culinaria.terra.com.br Linha 26 ==> Linha 27 ==> Linha 28 ==> Linha 29 ==> Linha 30 ==> Linha 31 ==> lances.caldeiraodeofertas.com.br Linha 32 ==> Linha 33 ==> Linha 34 ==> www.jjcabeleireiros.com.br Linha 35 ==> Linha 36 ==> servlet.pop.com.br Linha 37 ==> www.guiadecasamento.com.br Linha 38 ==> Linha 39 ==> carros.peugeot.com.br Linha 40 ==> www.unimedpaulistanasp.com.br Linha 41 ==> Linha 42 ==> Linha 43 ==> Linha 44 ==> Linha 45 ==> wp.kzuka.com.br Linha 46 ==> www.officina.digi.com.br Linha 47 ==> Linha 48 ==> Linha 49 ==> casacinepoa.com.br Linha 50 ==> minasdeouro.com.br Linha 51 ==> mrvhospitalar.com.br Linha 52 ==> Linha 53 ==> Linha 54 ==> Linha 55 ==> www.tropicalia.com.br Linha 56 ==> Linha 57 ==> Linha 58 ==> Linha 59 ==> Linha 60 ==> parqueestadualcamposdojordao.vilabol.uol.com.br Linha 61 ==> www.goncalves.ind.br Linha 62 ==> Linha 63 ==> Linha 64 ==> Linha 65 ==> Linha 66 ==> valehost.com.br Linha 67 ==> Linha 68 ==> colecionadorasdemoda.blogspot.com.br Linha 69 ==> www.cuponfair.com.br Linha 70 ==> Linha 71 ==> crianca.ig.com.br Linha 72 ==> lojademotos.com.br Linha 73 ==> www.bosqueclube.com.br Linha 74 ==> www.drilllampe.com.br Linha 75 ==> www.iguatu.ce.gov.br Linha 76 ==> usinadorock.com.br Linha 77 ==> www.nordesterural.com.br Linha 78 ==> Linha 79 ==> Linha 80 ==> images.parperfeito.com.br Linha 81 ==> www.goldminer.com.br Linha 82 ==> Linha 83 ==> Linha 84 ==> Linha 85 ==> Linha 86 ==> Linha 87 ==> promaqrental.blogspot.com.br Linha 88 ==> www.campingdopaiol.com.br . . .

b) A seguir so apresentados alguns resultados da anlise estatstica dos dados cadastrados na tabela hash com endereamento aberto. Foram sorteadas 1000 URLs da base e em seguida foram realizadas buscas para cada uma delas, e ao final foram obtidas as estatsticas contendo os seguintes dados referentes ao nmero de comparaes para encontrar as URLs: menor valor, maior valor, mdia e mediana para o nmero de comparaes. Estatsticas para 1000 URLs CADASTRADAS Teste 1 Teste 2 Teste 3 Teste 4 Menor Valor: 1 Maior Valor: 27 Mdia: 1,437000 Mediana: 1,000000












c) A seguir so apresentados resultados da anlise estatstica dos dados NO cadastrados na tabela hash com endereamento aberto. Foram sorteadas 1000 URLs da base e em seguida estas foram alteradas em 1 caractere. Posteriormente foram realizadas buscas para cada uma delas, e ao final foram obtidas as estatsticas contendo os seguintes dados referentes ao nmero de comparaes necessrios para identificar que as URLs no existem na tabela hash: menor valor, maior valor, mdia e mediana para o nmero de comparaes.

Estatsticas para 1000 URLs NO CADASTRADAS (ALTERADAS) Teste 1 Teste 2 Teste 3 Teste 4 Menor Valor: 0 Maior Valor: 73 Mdia: 3,538000 Mediana: 1,000000












d) Fazer uma tabela com os resultados. Analisar e comparar com a teoria. Conforme anlise dos dados a seguir, percebe-se que o melhor caso (menor valor) em todos os testes resultou em 1 comparao somente. O fato de a mediana tambm resultar em 1 mostra que para a maioria dos elementos amostrados no houve coliso. A mdia dos valores sendo pouco maior que 1 mostra que o nmero de colises foi baixo para a grande maioria dos elementos da tabela, ou seja, houve uma boa distribuio dos dados na tabela hash com endereamento aberto. O pior caso (maior valor) nos permite visualizar o agrupamento mximo dentro dos dados amostrados, ou seja, regies da tabela onde houve maior concentrao dos dados e mais colises.

Estatsticas de 1000 URLs Cadastradas - Nmero de Comparaes

T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12

Menor Valor 1 1 1 1 1 1 1 1 1 1 1 1

Maior Valor 27 42 36 45 42 62 62 17 31 16 21 25

Mdia 1,437 1,497 1,435 1,432 1,42 1,568 1,572 1,32 1,515 1,337 1,371 1,396

Mediana 1 1 1 1 1 1 1 1 1 1 1 1

Para URLs no cadastradas o menor valor corresponde s posies vazias da tabela hash com endereamento linear, ou seja. Nesse caso a implementao no est contando a comparao necessria para identificar a posio vazia (nula), por isso o resultado zero. Se essa comparao for necessria para alguma anlise, dever ser considerada 1 comparao a mais para todos os resultados. Nesta implementao essa comparao est sendo desconsiderada para as estatsticas apresentadas a seguir. O pior caso permite visualizar os agrupamentos maiores dentro da amostra. A mdia de comparaes entre 3 e 4 operaes dentro da amostragem sugere uma boa distribuio. A mediana de valor 1 refora esse ponto, considerando que para a maioria das URLs pesquisadas houve somente 1 comparao para identificar a no existncia da mesma.

Estatsticas de 1000 URLs NO Cadastradas - Nmero de Comparaes

T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12

Menor Valor 0 0 0 0 0 0 0 0 0 0 0 0

Maior Valor 73 76 75 67 79 75 75 67 80 66 80 79

Mdia 3,538 3,656 3,536 3,15 3,182 3,536 3,616 3,576 3,183 3,084 3,77 4,095

Mediana 1 1 1 1 1 1 1 1 1 1 1 1

A seguir so exibidos os grficos para melhor visualizao dos resultados:

0

10

20

30

40

50

60

70

1 2 3 4 5 6 7 8 9 10 11 12

Menor Valor

Maior Valor

Mdia

Mediana

Estatsticas de 1000 URLs CadastradasNmero de Comparaes

0

10

20

30

40

50

60

70

80

90

1 2 3 4 5 6 7 8 9 10 11 12

Menor Valor

Maior Valor

Mdia

Mediana

Estatsticas de 1000 URLs No CadastradasNmero de Comparaes

Consideraes Finais A implementao de tabelas hashing mostrou-se uma tcnica altamente eficiente, eficaz e robusta para criao de estruturas de indexao de dados, com elevado ganho de desempenho nos resultados das pesquisas. A implementao exige muitos testes e especial cuidado na elaborao da estrutura de dados e da funo hash utilizada. Muitas variaes da funo hash podem ser testadas e possvel alcanar ainda melhoria na distribuio dos dados, dependendo da funo hash utilizada. A estrutura de tabela hash com listas encadeadas se mostrou mais eficaz para pesquisas na base de dados utilizada neste trabalho.

Anexos (cdigo fonte) 1 2 package table; 3 4 import inputFile.txtFile; 5 import list.FindResults; 6 import table.hashTableListSet; 7 8 /** 9 * Teste de tabela hash com listas encadeadas 10 * @author danilo.leite 11 */ 12 public class TestHashTableListSet { 13 14 15 16 public static void main(String[] args) { 17 18 txtFile arquivoUrl = new txtFile(); 19 hashTableListSet listaURL; 20 arquivoUrl.setHashTableLS(); 21 //String lista = arquivoUrl.getListURL(); 22 listaURL = arquivoUrl.getHashTableLS(); 23 // exibir o contedo da tabela hash 24 listaURL.showHashTable(); 25 System.out.println(); 26 System.out.println("*****Estatsticas para 1000 URLs CADASTRADAS*****"); 27 listaURL.findStats(true); 28 System.out.println(); 29 System.out.println("*****Estatsticas para 1000 URLs NO CADASTRADAS (ALTERADAS)*****"); 30 listaURL.findStats(false); 31 32 } 33 34 } 1 package table; 2 3 import inputFile.txtFile; 4 import list.FindResults; 5 6 /** 7 * Teste de tabela hash com endereamento aberto linear 8 * @author danilo.leite 9 */ 10 public class TestHashTableOpen { 11 12 public static void main(String[] args) { 13 14 txtFile arquivoUrl = new txtFile(); 15 hashTableOpenAdress listaURL; 16 arquivoUrl.setHashTableOpen();

17 //String lista = arquivoUrl.getListURL(); 18 listaURL = arquivoUrl.getHashTableOpen(); 19 // exibir o contedo da tabela hash 20 listaURL.showHashTableOpen(); 21 System.out.println(); 22 System.out.println("*****Estatsticas para 1000 URLs CADASTRADAS*****"); 23 listaURL.findStats(true); 24 System.out.println(); 25 System.out.println("*****Estatsticas para 1000 URLs NO CADASTRADAS (ALTERADAS)*****"); 26 listaURL.findStats(false); 27 28 } 29 30 } 31 1 package table; 2 3 import inputFile.txtFile; 4 import list.ListSet; 5 import list.FindResults; 6 import vectorInt.VectorInt; 7 8 /** tabela hash com listas encadeadas 9 * 10 * @author danilo.leite 11 */ 12 public class hashTableListSet { 13 private final int TABLE_SIZE = 1071; // tamanho da tabela hash 14 private ListSet[] htable; 15 private ListSet aux; 16 private final int NUMBER_COMPARES = 1000; // nmero de URLs a serem sorteadas 17 18 public hashTableListSet(){ 19 htable = new ListSet[TABLE_SIZE]; 20 } 21 22 public int hash(String url){ 23 int h = -1; // retorno da funo hash para posicionar na tabela 24 int n = url.length(); // tamanho da string 25 if (n == 0) 26 return h; 27 long codUrl = 0; 28 for(int i = 0; i < n; i++){ 29 codUrl = (long) (codUrl + url.charAt(i)*Math.pow(2, n-i)/(i+1)); //gera um cdigo inteiro baseado nos caracteres da string 30 } 31 codUrl = (long) codUrl/n; 32 h = (int) (codUrl % TABLE_SIZE); // o resultado do hash o codUrl dividido pelo tamanho da tabela hash

33 return h; 34 } 35 36 public void add(String url){ 37 int posicao = hash(url); 38 if (posicao == -1) 39 return; 40 if (this.htable[posicao] == null) 41 this.htable[posicao] = new ListSet(); 42 this.htable[posicao].add(url); 43 } 44 45 public FindResults find(String url){ 46 FindResults results = new FindResults(); 47 int posicao = hash(url); 48 if (posicao == -1) 49 return results; 50 results = this.htable[posicao].findInList(url); // pesquisa na posio da tabela onde est a lista encadeada 51 results.setHashPosition(posicao); // guarda a posio da tabela hash 52 return results; // retorna posio, nmero de comparaes, resultado da pesquisa 53 } 54 // realiza pesquisa sobre N URLs sorteadas e fornece estatsticas de nmeros de comparaes: 55 // menor valor, maior valor, mdia e mediana 56 public void findStats(boolean allExist){ 57 // allExist: parmetro para indicar se na pesquisa realizada esto sendo utilizadas URLs existentes ou no existentes na base 58 // allExist ser verdadeiro se todas as URLs pesquisadas existem na base 59 // allExist ser falso se todas as URLs pesquisadas no existem na base 60 int minorValue; // menor valor 61 int majorValue; // maior valor 62 double mediaValue; // media 63 double medianaValue; // mediana 64 int sumValues = 0; // soma dos valores 65 int rest; 66 boolean allRegistered = true; 67 boolean allNotRegistered = true; // flags para indicar se todas as URLs pesquisadas so cadastradas ou no 68 // allRegistered ser falso caso 1 URL no seja encontrada; allNotRegistered ser falso caso 1 URL seja encontrada; 69 int[] compareValues = new int[this.NUMBER_COMPARES]; // armazena a quantidade de comparaes 70 FindResults result = new FindResults(); // resultados de uma pesquisa 71 txtFile arquivoUrl = new txtFile(); 72 arquivoUrl.sortLines(this.NUMBER_COMPARES); // seleciona aleatoriamente [NUMBER_COMPARES] do arquivo 73 String newURL; 74 if (!allExist){ // se prentende realizar pesquisas com URLs inexistentes (alteradas)

75 // alterar as URLs em 1 caractere: o caracter 'X' ir sobrepor 1 caractere da URL aproximadamente no meio da String 76 for(int n = 0; n < this.NUMBER_COMPARES; n++){ 77 newURL = arquivoUrl.getSortList()[n]; 78 newURL = newURL.substring(0, (int) newURL.length()/2) + 'X' + newURL.substring((int) (newURL.length()/2)+2, newURL.length()-1); // substitui 1 caracter por 'X' 79 arquivoUrl.setSortListItem(newURL, n); // atualiza 80 } 81 } 82 // realiza as pesquisas e monta vetor com nmero de comparaes das pesquisas 83 for(int i = 0; i < this.NUMBER_COMPARES; i++) { 84 result = this.find(arquivoUrl.getSortList()[i]); 85 compareValues[i] = result.getNumberOfComparison(); 86 if (result.isFound()){ // se foi encontrado 87 if (allNotRegistered) allNotRegistered = false; // se houver uma ocorrncia encontrada, ser falso 88 } 89 else 90 if (allRegistered) allRegistered = false; // se uma ocorrncia no for encontrada, ser falso 91 } 92 // ordenar os resultados das comparaes 93 VectorInt vet = new VectorInt(); // classe que contm o mtodo de ordenao 94 compareValues = vet.selectionOrder(compareValues); 95 // fim ordenao 96 // compareValues = 97 // calcula as estatsticas 98 minorValue = compareValues[0]; // aps a ordenao, o primeiro valor o menor valor 99 majorValue = compareValues[this.NUMBER_COMPARES-1]; // o maior valor encontra-se na ltima posio 100 for(int j = 0; j < this.NUMBER_COMPARES; j++){ 101 // calcular aqui as medias percorrendo o vetor 102 sumValues = sumValues + compareValues[j]; // faz o somatrio 103 } 104 mediaValue = (double) sumValues/this.NUMBER_COMPARES; // calcula a mdia de comparaes 105 // calcula a mediana 106 rest = this.NUMBER_COMPARES % 2; // verificar se o tamanho do vetor par 107 boolean isPair = (rest == 0); // se o resto da diviso for zero o tamanho do vetor par 108 if (isPair) {// mediana no caso de vetor tamanho par 109 medianaValue = (double) (compareValues[(this.NUMBER_COMPARES/2)] + compareValues[(this.NUMBER_COMPARES/2)+1])/2; 110 }else 111 { 112 // mediana no caso de vetor tamanho mpar

113 medianaValue = compareValues[(this.NUMBER_COMPARES/2)+1]; 114 } 115 System.out.printf("Menor Valor: %d\n", minorValue); 116 System.out.printf("Maior Valor: %d\n", majorValue); 117 System.out.printf("Mdia: %f\n", mediaValue); 118 System.out.printf("Mediana: %f\n", medianaValue); 119 if (allRegistered) 120 System.out.println("TODAS as URLs pesquisadas foram encontradas."); 121 if (allNotRegistered) 122 System.out.println("NENHUMA das URLs pesquisadas foi encontrada."); 123 124 } 125 126 127 // mtodo para teste: visualizar contedo da tabela hash com listas encadeadas 128 public void showHashTable(){ 129 for(int i = 0; i < TABLE_SIZE; i++){ 130 System.out.printf("Linha %d ==> ",i); 131 if (this.htable[i] == null){ 132 System.out.print("Posio vazia"); 133 } 134 else{ 135 this.htable[i].showList(); 136 } 137 System.out.println(); 138 } 139 } 140 // mtodo para teste: visualizar o nmero de colises por posio da tabela hash 141 public void showHashTableRecordsPerLine(){ 142 int majorLine = 0; 143 int quantity = 0; 144 for(int i = 0; i < TABLE_SIZE; i++){ 145 System.out.printf("Linha %d ==> ",i); 146 if (this.htable[i] == null){ 147 System.out.print("Posio vazia"); 148 } 149 else{ 150 quantity = this.htable[i].sizeList(); 151 if (quantity > majorLine) 152 majorLine = quantity; 153 System.out.printf("%d registros",quantity); 154 } 155 System.out.println(); 156 } 157 System.out.printf("Nmero mximo de colises: %d registros na mesma posio\n",majorLine); 158 } 159 160 } 161

1 package table; 2 3 import inputFile.txtFile; 4 import list.FindResults; 5 import vectorInt.VectorInt; 6 7 /** tabela hash com endereamento aberto linear 8 * 9 * @author danilo.leite 10 */ 11 public class hashTableOpenAdress { 12 private final int TABLE_SIZE = 21392; // tamanho da tabela hash linear 13 private String[] htableOpen; 14 private String aux; 15 private final int NUMBER_COMPARES = 1000; // nmero de URLs a serem sorteadas 16 17 public hashTableOpenAdress(){ 18 htableOpen = new String[TABLE_SIZE]; 19 } 20 21 public int hash(String url){ 22 int h = -1; // retorno da funo hash para posicionar na tabela 23 int n = url.length(); // tamanho da string 24 if (n == 0) 25 return h; 26 long codUrl = 0; 27 for(int i = 0; i < n; i++){ 28 codUrl = (long) (codUrl + url.charAt(i)*Math.pow(2, n-i)/(i+1)); //gera um cdigo inteiro baseado nos caracteres da string 29 } 30 codUrl = (long) codUrl/n; 31 h = (int) (codUrl % TABLE_SIZE); // o resultado do hash o codUrl dividido pelo tamanho da tabela hash 32 return h; 33 } 34 // incluir elemento na tabela 35 public void add(String url){ 36 int posicao = hash(url); 37 if (posicao == -1) 38 return; 39 if (this.htableOpen[posicao] == null) 40 this.htableOpen[posicao] = url; 41 else // em caso de coliso (posio ocupada) 42 { // encontrar nova posio vazia 43 do { 44 posicao = posicao+1; 45 } while (this.htableOpen[posicao] != null); 46 this.htableOpen[posicao] = url; // inclui em nova posio vazia 47 } 48 } 49

50 public FindResults find(String url){ 51 FindResults results = new FindResults(); 52 int posicao = hash(url); 53 if ((posicao == -1) || (this.htableOpen[posicao] == null)) 54 return results; 55 results.incNumberOfComparison();// incrementa nmero de comparaes 56 // se encontrar na primeira posio 57 if (this.htableOpen[posicao].equals(url)){ 58 results.setFound(true); 59 results.setHashPosition(posicao); 60 return results; 61 } 62 posicao = posicao + 1; // proxima posio 63 while ((this.htableOpen[posicao] != null) && (!this.htableOpen[posicao].equals(url))){ 64 posicao = posicao + 1; 65 results.incNumberOfComparison();// incrementa nmero de comparaes 66 } 67 // se no achou 68 if (this.htableOpen[posicao] == null){ 69 // termina a busca e retorna resultados 70 results.setFound(false); 71 results.setHashPosition(posicao); 72 return results; 73 } 74 // se achou (os testes anteriores deram falso) 75 results.setFound(true); 76 results.setHashPosition(posicao); 77 return results; 78 } 79 80 // realiza pesquisa sobre N URLs sorteadas e fornece estatsticas de nmeros de comparaes: 81 // menor valor, maior valor, mdia e mediana 82 public void findStats(boolean allExist){ 83 // allExist: parmetro para indicar se na pesquisa realizada esto sendo utilizadas URLs existentes ou no existentes na base 84 // allExist ser verdadeiro se todas as URLs pesquisadas existem na base 85 // allExist ser falso se todas as URLs pesquisadas no existem na base 86 int minorValue; // menor valor 87 int majorValue; // maior valor 88 double mediaValue; // media 89 double medianaValue; // mediana 90 int sumValues = 0; // soma dos valores 91 int rest; 92 boolean allRegistered = true; 93 boolean allNotRegistered = true; // flags para indicar se todas as URLs pesquisadas so cadastradas ou no 94 // allRegistered ser falso caso 1 URL no seja encontrada; allNotRegistered ser falso caso 1 URL seja encontrada;

95 int[] compareValues = new int[this.NUMBER_COMPARES]; // armazena a quantidade de comparaes 96 FindResults result = new FindResults(); // resultados de uma pesquisa 97 txtFile arquivoUrl = new txtFile(); 98 arquivoUrl.sortLines(this.NUMBER_COMPARES); // seleciona aleatoriamente [NUMBER_COMPARES] do arquivo 99 String newURL; 100 if (!allExist){ // se prentende realizar pesquisas com URLs inexistentes (alteradas) 101 // alterar as URLs em 1 caractere: o caracter 'X' ir sobrepor 1 caractere da URL aproximadamente no meio da String 102 for(int n = 0; n < this.NUMBER_COMPARES; n++){ 103 newURL = arquivoUrl.getSortList()[n]; 104 newURL = newURL.substring(0, (int) newURL.length()/2) + 'X' + newURL.substring((int) (newURL.length()/2)+2, newURL.length()-1); // substitui 1 caracter por 'X' 105 arquivoUrl.setSortListItem(newURL, n); // atualiza 106 } 107 } 108 // realiza as pesquisas e monta vetor com nmero de comparaes das pesquisas 109 for(int i = 0; i < this.NUMBER_COMPARES; i++) { 110 result = this.find(arquivoUrl.getSortList()[i]); 111 compareValues[i] = result.getNumberOfComparison(); 112 if (result.isFound()){ // se foi encontrado 113 if (allNotRegistered) allNotRegistered = false; // se houver uma ocorrncia encontrada, ser falso 114 } 115 else 116 if (allRegistered) allRegistered = false; // se uma ocorrncia no for encontrada, ser falso 117 } 118 // ordenar os resultados das comparaes 119 VectorInt vet = new VectorInt(); // classe que contm o mtodo de ordenao 120 compareValues = vet.selectionOrder(compareValues); 121 // fim ordenao 122 // calcula as estatsticas 123 minorValue = compareValues[0]; // aps a ordenao, o primeiro valor o menor valor 124 majorValue = compareValues[this.NUMBER_COMPARES-1]; // o maior valor encontra-se na ltima posio 125 for(int j = 0; j < this.NUMBER_COMPARES; j++){ 126 // calcular aqui as medias percorrendo o vetor 127 sumValues = sumValues + compareValues[j]; // faz o somatrio 128 } 129 mediaValue = (double) sumValues/this.NUMBER_COMPARES; // calcula a mdia de comparaes 130 // calcula a mediana 131 rest = this.NUMBER_COMPARES % 2; // verificar se o tamanho do vetor par

132 boolean isPair = (rest == 0); // se o resto da diviso for zero o tamanho do vetor par 133 if (isPair) {// mediana no caso de vetor tamanho par 134 medianaValue = (double) (compareValues[(this.NUMBER_COMPARES/2)] + compareValues[(this.NUMBER_COMPARES/2)+1])/2; 135 }else 136 { 137 // mediana no caso de vetor tamanho mpar 138 medianaValue = compareValues[(this.NUMBER_COMPARES/2)+1]; 139 } 140 System.out.printf("Menor Valor: %d\n", minorValue); 141 System.out.printf("Maior Valor: %d\n", majorValue); 142 System.out.printf("Mdia: %f\n", mediaValue); 143 System.out.printf("Mediana: %f\n", medianaValue); 144 if (allRegistered) 145 System.out.println("TODAS as URLs pesquisadas foram encontradas."); 146 if (allNotRegistered) 147 System.out.println("NENHUMA das URLs pesquisadas foi encontrada."); 148 149 } 150 151 152 // mtodo para teste: visualizar contedo da tabela hash 153 public void showHashTableOpen(){ 154 for(int i = 0; i < TABLE_SIZE; i++){ 155 System.out.printf("Linha %d ==> ",i); 156 if (this.htableOpen[i] == null){ 157 System.out.print("\n"); 158 } 159 else{ 160 System.out.println(this.htableOpen[i]); 161 } 162 //System.out.println(); 163 } 164 } 165 } 1 package list; 2 3 /** classe para retornar os resultados de uma pesquisa na lista ou em uma posio da tabela hash 4 * dever conter o nmero de comparaes e o resultado da pesquisa (verdadeiro ou falso) 5 * se a pesquisa for na tabela hash retornar tambm a posio na tabela 6 * dessa forma podero ser retornadas mais informaes sobre a pesquisa 7 * @author danilo.leite 8 */ 9 public class FindResults { 10 private int numberOfComparison; // nmero de comparaes na lista 11 private boolean found; // resultado da pesquisa

12 private int hashPosition; // posio na tabela hash (quando for o caso) 13 14 public FindResults(){ 15 this.numberOfComparison = 0; 16 this.found = false; 17 this.hashPosition = -1; // posio inicial inexistente; somente ser utilizada para tabela hash 18 } 19 20 public int getNumberOfComparison() { 21 return this.numberOfComparison; 22 } 23 24 25 public void incNumberOfComparison() { 26 this.numberOfComparison = this.numberOfComparison + 1; 27 } 28 29 public boolean isFound() { 30 return this.found; 31 } 32 33 public void setFound(boolean found) { 34 this.found = found; 35 } 36 37 public int getHashPosition() { 38 return this.hashPosition; 39 } 40 41 public void setHashPosition(int hashPosition) { 42 this.hashPosition = hashPosition; 43 } 44 } 1 package list; 2 3 /**define a estrutura de um elemento da lista 4 * composta de uma String para URL e um apontador para o prximo elemento da lista 5 * @author danilo.leite 6 */ 7 public class ListElement { 8 private String url; 9 private ListElement next; 10 11 public ListElement(){ 12 } 13 14 public String getUrl() { 15 return url; 16 } 17 18 public void setUrl(String url) { 19 this.url = url;

20 } 1 package list; 2 3 /**define estrutura e as operaes da lista encadeada 4 * 5 * @author danilo.leite 6 */ 7 public class ListSet { 8 private ListElement first; // primeiro elemento da lista atua como ncora (referncia para a lista) 9 private ListElement aux,newElement; 10 private boolean found; // resultado da ltima pesquisa findInList 11 12 // inicializa a lista vazia 13 public ListSet(){ 14 this.first = null; // a ideia sempre guardar o primeiro elemento como uma ncora 15 } 16 17 // ao adicionar elemento na lista, dever sempre colocar na primeira posio 18 public void add(String url){ 19 if (this.first == null){ 20 this.first = new ListElement(); 21 this.first.setUrl(url); 22 this.first.setNext(null); // o ltimo elemento da lista sempre vazio (nulo) 23 } 24 else{ 25 this.newElement = new ListElement(); // cria novo 26 this.newElement.setUrl(url); // atribui a url 27 this.aux = this.first; // guarda a primeira posio da lista em aux 28 this.newElement.setNext(this.aux); // coloca no novo elemento na primeira posio apontando para aux 29 this.first = this.newElement; // atribui o novo elemento varivel first (ncora), que aponta para o antigo primeiro elemento 30 } 31 } 32 33 // exibe o resultado da pesquisa na lista: retorna nmero de comparaes na lista e atribui true ou false varivel this.found 34 public FindResults findInList(String url){ 35 FindResults results = new FindResults(); // o resultado inicial nmero de comparaes = 0 e resultado da pesquisa = falso 36 if (this.first == null){ 37 return results; // no houve pesquisa 38 } 39 else{ 40 aux = first; 41 while (aux != null){ 42 results.incNumberOfComparison(); // incrementa o nmero de comparaes em + 43 if (aux.getUrl().equals(url)){ 44 results.setFound(true);// encontrou

45 break; 46 } 47 aux = aux.getNext(); 48 } 49 } 50 return results; 51 } 52 53 // exibe o contedo da lista 54 public void showList(){ 55 if (this.first == null){ 56 System.out.println("Lista vazia"); 57 } 58 else{ 59 aux = first; 60 int i = 1; 61 while (aux != null){ 62 System.out.printf("%d.["+aux.getUrl()+"];",i); 63 aux = aux.getNext(); 64 i = i+1; 65 } 66 } 67 } 68 69 // exibe o tamanho da lista 70 public int sizeList(){ 71 int i = 0; 72 if (this.first == null){ 73 return i; 74 } 75 else{ 76 aux = first; 77 while (aux != null){ 78 i = i+1; 79 aux = aux.getNext(); 80 } 81 } 82 return i; 83 } 84 85 /** 86 * @return the found 87 */ 88 public boolean isFound() { 89 return this.found; 90 } 91 } 1 package list; 2 3 /** teste de lista encadeada 4 * 5 * @author danilo.leite 6 */ 7 public class TestList { 8

9 public static ListSet lista = new ListSet(); 10 11 public static void main(String[] args) { 12 // TODO code application logic here 13 lista = new ListSet(); 14 lista.add("www.pdcase.com"); 15 lista.add("www.globo.com"); 16 lista.add("www.estaminas.com"); 17 lista.add("www.ufop.br"); 18 19 lista.showList(); 20 } 21 22 23 } 1 package inputFile; 2 3 import java.io.BufferedReader; 4 import java.io.FileReader; 5 import java.io.IOException; 6 import java.util.Random; 7 import table.hashTableListSet; 8 import table.hashTableOpenAdress; 9 import vectorInt.VectorInt; 10 11 /** 12 * funes de manipulao de arquivo texto e integrao com tabela hash 13 * @author danilo.leite 14 */ 15 public class txtFile { 16 17 private int numLinhas = 0; 18 private String listUrl; // lista de urls do arquivo no formato String -- testes de importao 19 private hashTableListSet hashTableLS; 20 private hashTableOpenAdress hashTableOpen; 21 private final int RANGE_LIMIT = 10696; // limite para o sorteio das URLs 22 private String[] sortList;// lista de URLs sorteadas 23 private String arquivo; 24 25 public txtFile(){ 26 this.hashTableLS = new hashTableListSet(); 27 this.hashTableOpen = new hashTableOpenAdress(); 28 this.arquivo = "c:\\Users\\danilo.leite\\Documents\\NetBeansProjects\\Hashing\\src\\inputFile\\URLs2.txt"; 29 } 30 31 public void setListURL() { 32 33 String tagInicio = "

"; 34 String tagFim = "
"; 35 String txtURL = new String();

36 try { 37 //abrir arquivo 38 BufferedReader br = new BufferedReader(new FileReader(this.arquivo)); 39 while (br.ready()) { 40 String linha = br.readLine(); 41 if (br.ready()) { 42 this.numLinhas = this.numLinhas + 1; 43 } 44 if (linha.contains(tagInicio)) { 45 linha = linha.replaceFirst(tagInicio, ""); // remover tag incio 46 } 47 if (linha.contains(tagFim)) { 48 linha = linha.replaceFirst(tagFim, ""); // remover tag fim 49 } 50 //txtURL = txtURL + linha + "#"; // # para separar as linhas 51 if (txtURL != null) 52 txtURL = txtURL + '\n'; 53 txtURL = txtURL + linha; 54 } 55 br.close(); 56 this.listUrl = txtURL; 57 } catch (IOException ioe) { 58 ioe.printStackTrace(); 59 } 60 } 61 62 public String getListURL() { 63 return this.listUrl; 64 } 65 66 public int getNumLinhas() { 67 return this.numLinhas; 68 } 69 70 public hashTableListSet getHashTableLS() { 71 return this.hashTableLS; 72 } 73 74 public void setHashTableLS() { 75 String tagInicio = "

"; 77 try { 78 //abrir arquivo 79 BufferedReader br = new BufferedReader(new FileReader(this.arquivo)); 80 while (br.ready()) { 81 String linha = br.readLine(); 82 if (br.ready()) { 83 this.numLinhas = this.numLinhas + 1; 84 } 85 if (linha.contains(tagInicio)) {

86 linha = linha.replaceFirst(tagInicio, ""); // remover tag incio 87 } 88 if (linha.contains(tagFim)) { 89 linha = linha.replaceFirst(tagFim, ""); // remover tag fim 90 } 91 if (linha != null) 92 this.hashTableLS.add(linha); // adiciona URL na hashTableLS 93 } 94 br.close(); 95 } catch (IOException ioe) { 96 ioe.printStackTrace(); 97 } 98 } 99 100 public void setHashTableOpen() { 101 String tagInicio = "

"; 103 this.numLinhas = 0; 104 try { 105 //abrir arquivo 106 BufferedReader br = new BufferedReader(new FileReader(this.arquivo)); 107 while (br.ready()) { 108 String linha = br.readLine(); 109 if (br.ready()) { 110 this.numLinhas = this.numLinhas + 1; 111 } 112 if (linha.contains(tagInicio)) { 113 linha = linha.replaceFirst(tagInicio, ""); // remover tag incio 114 } 115 if (linha.contains(tagFim)) { 116 linha = linha.replaceFirst(tagFim, ""); // remover tag fim 117 } 118 if (linha != null) 119 this.hashTableOpen.add(linha); // adiciona URL na hashTableOpen 120 } 121 br.close(); 122 } catch (IOException ioe) { 123 ioe.printStackTrace(); 124 } 125 } 126 127 public hashTableOpenAdress getHashTableOpen() { 128 return this.hashTableOpen; 129 } 130 131 // sorteia e seleciona um determinado nmero de linhas (URLs) do arquivo 132 public void sortLines(int numberSortLines){ 133 String tagInicio = "
";

134 String tagFim = "
"; 135 this.sortList = new String[numberSortLines]; // cria um vetor de [numberSortLines] posies para armazenar as URLs sorteadas 136 int[] sortedLines = new int[numberSortLines]; // vetor de inteiros para guardar as posies sorteadas 137 Random rdm = new Random(); 138 int pos = 0; // posio no arquivo 139 String linha = ""; // varivel para armazenar linha do arquivo 140 // sortear as [numberSortLines] URLs e adicionar em resultLines 141 try { 142 //abrir arquivo 143 BufferedReader br = new BufferedReader(new FileReader(this.arquivo)); 144 // selecionar [numberSortLines] posies para extrair as URLs para pesquisa 145 for(int i = 0; i < numberSortLines; i++) { 146 sortedLines[i] = rdm.nextInt(RANGE_LIMIT); // gera posio randomicamente dentro do range da tabela 147 // (entre 0 e RANGE_LIMIT-1) 148 } 149 // ordena vetor de posies 150 VectorInt vet = new VectorInt(); // classe que contm o mtodo de ordenao 151 sortedLines = vet.selectionOrder(sortedLines); 152 // fim ordenao 153 for(int i = 0; i < numberSortLines; i++) { 154 // posiciona na prxima linha sorteada 155 for(int j = pos; j < sortedLines[i]-1; j++){ 156 br.readLine(); 157 } 158 if (pos < sortedLines[i]){ 159 pos = sortedLines[i]; // atualiza posio no arquivo 160 linha = br.readLine(); 161 } 162 if (br.ready()) { 163 if (linha.contains(tagInicio)) { 164 linha = linha.replaceFirst(tagInicio, ""); // remover tag incio 165 } 166 if (linha.contains(tagFim)) { 167 linha = linha.replaceFirst(tagFim, ""); // remover tag fim 168 } 169 } 170 //this.sortList[i] = Integer.toString(sortedLines[i])+"."+linha; // teste para verificar a aleatoriedade 171 this.sortList[i] = linha; // teste para verificar a aleatoriedade 172 } 173 br.close(); 174 } 175 catch (IOException ioe) {

176 ioe.printStackTrace(); 177 } 178 179 } 180 181 public String[] getSortList() { 182 return this.sortList; 183 } 184 185 // alterar a URL em uma determinada posio da lista 186 public void setSortListItem(String newURL, int index) { 187 this.sortList[index] = newURL; 188 } 189 190 191 } 192 1 package inputFile; 2 3 /** 4 * teste de importao de dados do arquivo texto 5 * @author danilo.leite 6 */ 7 public class TestTxtFile { 8 9 public static void main(String[] args) { 10 11 txtFile arquivoUrl = new txtFile(); 12 arquivoUrl.setListURL(); 13 System.out.println(arquivoUrl.getListURL()); 14 System.out.printf("Nmero de linhas: %d", arquivoUrl.getNumLinhas()); 15 System.out.println(); 16 } 17 18 } 1 package inputFile; 2 3 /** 4 * teste do sorteio das URLs 5 * @author danilo.leite 6 */ 7 public class TestSortList { 8 public static void main(String[] args) { 9 txtFile arquivoUrl = new txtFile(); 10 arquivoUrl.sortLines(1000); 11 for(int i = 0; i < 1000; i++) { 12 System.out.println(arquivoUrl.getSortList()[i]); 13 } 14 System.out.println(); 15 } 16 }

1 package vectorInt; 2 /** 3 * ordenao de vetor de inteiros 4 * @author danilo.leite 5 */ 6 public class VectorInt { 7 public int[] selectionOrder(int[] vet){ // ordena vetor de inteiros 8 int menor, aux; // max recebe o primeiro elemento do vetor 9 for(int i = 0; i