Савршена хеш функција

Из Википедије, слободне енциклопедије

Савршена хеш функција за скуп С је хеш функција која повезује различите елементе из С у скуп целих бројева, без хеш преклапања. Савршена хеш функција је доста слична осталим хеш функцијама, али уз предност да разрешавање судара мора да се спроведе. Математички, то је тотална инјективна функција.

Употребе и коришћења[уреди]

Савршена хеш функција за одређени скуп С који може да се оцени у константном времену, и са вредностима у малом опсегу, може се наћи по случајном алгоритму по броју операција који је пропорционалан величини скупа С. [1] Минимална величина описа савршене хеш функције зависи од распона њених вредности:Што је мањи распон, више простора је потребно. Свака савршена хеш функција погодна за употребу са хеш табелама захтева најмање број битова који је пропорционалан величини С.

Савршена хеш функција са вредностима у ограниченом опсегу може да се користи за ефикасне операције претраге, постављањем кључева из С (или друге одговарајуће вредности) у табелу која је индексирана по излазним вредностима функције. Коришћење савршене хеш функције је најбоље у ситуацијама када је често испитиван велики скуп С, који се ретко ажурира. Ефикасна решења за вршење исправке су познати као савршено динамично хеширање, али ове методе су релативно компликоване за спровођење. Једноставна алтернатива савршеног хеширања, која такође омогућава динамичне исправке, је кукавичје сортирање.

Минимална савршена хеш функција[уреди]

Минимална савршена хеш функција је савршена хеш функција која мапира n кључева за n узастопних целих бројева-обично [0 ..n -1] или [1. n.]. Формалнији начин изражавања је: Нека су j и k елементи неког коначног скупа K. F је минимална савршена хеш функција акко F(ј) = F(К) sledi ј = К (инјекција) и постоји цео број такав да је распон од F a...a + |К | -1. Доказано је да схема минималне савршене хеш функције опште намене захтева најманје 1.44 битова/кључева [2] Међутим најмања тренутно користи око 2.5 бита / кључа.

Минимална савршена хеш функција F чува редослед ако су кључеви дати у неком редоследу a 1 ,a 2 , , ...an и за све кључевеa ј и a К , Ј < К следи (F(aj) < F(ak) [3] Минималне перфектне хеш функције које чувају редослед захтевају Ω (n logn) битова [4]

Минимална савршена хеш функција F је монотона ако чува лексикографски редослед кључева. Монотоне минималне савршене хеш функције могу да заузимају веома мали простор.

Види још[уреди]

Референце[уреди]

  1. ^ Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#
  2. ^ Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger (2009) (PDF). Hash, displace, and compress. Springer Berlin / Heidelberg Приступљено 11. 8. 2011.. 
  3. ^ Jenkins, Bob (14. 4. 2009.), „order-preserving minimal perfect hashing“, in Black, Paul E., Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, приступљено 5. 3. 2013. 
  4. ^ Fox, E. A.; Chen, Q. F.; Daoud, A. M.; Heath, L. S. (1990). „Order preserving minimal perfect hash functions and information retrieval“. Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval (ACM): 279-311. DOI:10.1145/96749.98233. ISBN 0-89791-408-2. 

Литература[уреди]

За даље читање[уреди]

Спољашње везе[уреди]