Esquemas de hashing perfeitos, mínimos, práticos, determinísticos e eficientes em tempo e em espaço

Abstract

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.

Abstract: This work proposes deterministic algorithms that, given a set with n keys, build in expected time O(n) a hash function with worst-case O(1) lookup time, which maps without collision the keys to the set {0, . . . , n-1}. These minimal perfect hashing schemes are mere variants of the probabilistic schemes of Botelho, Kohayakawa e Ziviani (2005) and Botelho, Pagh e Ziviani (2007) and have showed empirical results equivalent to the original algorithms. The deterministic variants have been implemented from the source codes of the original schemes developed in CMPH library by the authors theirselves, which is maintained at SourceForge.net. All the schemes have been input with the same key sets, so they could be compared fairly. Tests have been executed over datesets with up to 25 000 000 keys. Moreover, the proposed schemes have evidently the advantage of always generating the same hash function for the same key set. This deterministic behaviour might be useful for developing a dynamic hashing scheme, in which lie operations like insertion and deletion of keys, inspired in one of the excelent static schemes covered. One of the schemes of Botelho, Pagh e Ziviani (2007), as an example of excellence, builds hash functions representable by only about 2.62 bits for key. Such a result is very close to the known tight lower bound, of about 1.44 bits for key. Both the deterministic proposed versions and the original ones show to be practical for common applications of Hashing. However, in the theoretical foundation of the work of Botelho, Kohayakawa e Ziviani (2005) a conjecture remained open. The present dissertation also proposes a proof for the conjecture and ends up the correctness of the scheme.