O(1) pristup podacima pomoću 'trie' strukture

Abstract

U ovom radu mi smo ukratko opisali nekoliko važnih algoritama za savršeno heširanje. Najbolji u ovoj klasi algoritama u pogledu efikasnosti kreiranja heš funkcije, sprečavanja da dođe do kolizije i složenosti funkcije za pristup podacima je Brain-Tharp-ov algoritam. Za razliku od mnogih drugih algoritama Brain-Tharp-ov algoritam kreira uređenu savršenu heš funkciju. Međutim, faza pakovanja kolona kod Brian-Tharp-ovog algoritma veoma dugo traje. U cilju poboljšanja Brain-Tharpovog algoritma u ovom radu mi smo predložili tri implementacione tehnike za fazu pakovanja kolona. Predložene tehnike su proverene empirijski.

In this paper we briefly describe several important perfect hashing algorithms. The Brian-Tharp's algorithm is the best known in this class of algorithms in terms of function building efficiency, pattern collision avoidance nad retrieval function complexity. Unlike many other algorithms the Brian-Tharp's algorithm produces an ordered perfect hash function. However, the column packing phase of the Brian-Tharp's algorithm is very time-consuming. In order to improve the Brain-Tharp's algorithm in this paper we propose three implementation techniques for the column packing phase. The proposed techniques are validated empirically.