Resumo: Este trabalho propõe algoritmos determinísticos que, dado um conjunto com n chaves, constroem em tempo esperado O(n) uma função hash com tempo de busca no pior caso O(1), a qual mapeia sem colisão as chaves para o conjunto {0, . . . , n-1}. Esses esquemas de hashing perfeitos e mínimos são meras variantes dos esquemas aleatorizados de Botelho, Kohayakawa e Ziviani (2005) e Botelho, Pagh e Ziviani (2007) e mostraram resultados empíricos equivalentes aos dos algoritmos originais. As variantes determinísticas foram implementadas a partir dos códigos dos esquemas originais desenvolvidos na biblioteca CMPH pelos próprios autores, a qual é mantida no SourceForge.net. Todos os esquemas foram alimentados com os mesmos conjuntos de chaves, para que pudessem ser comparados com justiça. Foram executados testes para conjuntos com até 25 000 000 de chaves. Ademais, os esquemas propostos contam evidentemente com a vantagem de sempre produzirem a mesma hash para um mesmo conjunto de chaves. Esse comportamento determinístico pode ser útil para o desenvolvimento dum esquema dinâmico de hashing, em que figuram operações como inserção e deleção de chaves, inspirado num dos excelentes esquemas estáticos abordados. Um dos esquemas de Botelho, Pagh e Ziviani (2007), por exemplo de excelência, constrói hashes representáveis por apenas aproximadamente 2,62 bits por chave. Tal resultado é muito próximo da cota inferior justa conhecida, de aproximadamente 1,44 bits por chave. Tanto as versões determinísticas propostas quanto as originais mostram-se práticas para aplicações reais de Hashing. No entanto, na fundamentação teórica do trabalho de Botelho, Kohayakawa e Ziviani (2005) ainda restava uma conjectura. A presente dissertação também propõe uma demonstração para a conjectura e encerra a corretude do esquema.
| Identifer | oai:union.ndltd.org:IBICT/oai:dspace.c3sl.ufpr.br:1884/26904 |
| Date | 01 March 2012 |
| Creators | Zatesko, Leandro Miranda, 1988- |
| Contributors | Donadelli Júnior, Jair, Universidade Federal do Paraná. Programa de Pós-Graduaçao em Informática |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFPR, instname:Universidade Federal do Paraná, instacron:UFPR |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds