Original title:
Vlastnosti universálního hašování
Translated title:
Properties of universal hashing
Authors:
Babka, Martin Document type: Rigorous theses
Year:
2013
Language:
eng Abstract:
[eng][cze] The aim of this work is to create a model of hashing with an acceptable worst case time complexity. The model is based on the idea of universal hashing and the expected time of every operation is constant. The used universal class of functions consists of linear transformations between vector spaces. This class has already been studied with a good asymptotic result. This work improves the result and proves that the expected amortised time of the scheme is constant.Ciel'om tejto práce je navrhnút' model hashovania s akceptovatel'nou časovou zložitost'ou aj v najhoršom prípade. Vytvorený model je založený na princípe univerzálneho hashovania a výsledná očkávania časové zložitost' je konštantná. Ako systém univerzálnych funkcií sme zvolili množinu všetkých lineárnych zobrazení medzi dvomi vektorovými priestormi. Tento systém už bol študovaný s výsledkom predpovedajúcim dobrý asymptotický odhad. Táto práca nadvazuje na predchádzajúci výsledok a rozširuje ho. Tiež ukazuje, že očakávaný amortizovaný čas navrhnutej schémy je konštantný.
Keywords:
amortised time complexity; linear transformation; universal hashing; amortizovaná časová zložitosť; lineárne zobrazenie; univerzálne hashovanie
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/59201