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

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

Употребе и коришћења

Савршена хеш функција за одређени скуп С који може да се оцени у константном времену, и са вредностима у малом опсегу, може се наћи по случајном алгоритму по броју операција који је пропорционалан величини скупа С.^[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₁,a₂, , ...an и за све кључевеa _ј и a _К, Ј < К следи (F(a_j) < F(a_k)^[3] Минималне перфектне хеш функције које чувају редослед захтевају Ω (n logn) битова^[4]

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

Види још

Референце

^ 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#
^ Belazzougui, Djamal; Fabiano C. Botelho; Dietzfelbinger, Martin (2009). „Hash, displace, and compress” (PDF). Springer Berlin / Heidelberg. Приступљено 11. 8. 2011.
^ Jenkins, Bob (14. 4. 2009), „order-preserving minimal perfect hashing”, Ур.: Black, Paul E., Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, Приступљено 5. 3. 2013
^ 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. ISBN 978-0-89791-408-6. doi:10.1145/96749.98233.

Литература

Richard J. Cichelli. Minimal Perfect Hash Functions Made Simple, Communications of the ACM, Vol. 23, Number 1, January 1980.
Cormen, Thomas H.; Leiserson, Charles E.; Ronald L. Rivest; Stein, Clifford (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. Пронађени су сувишни параметри: |author-link= и |authorlink= (помоћ) Section 11.5: Perfect hashing. pp. 245–249.
Botelho, Fabiano C.; Pagh, Rasmus; Ziviani, Nivio (2007). „"Perfect Hashing for Data Management Applications"”. Bibcode:2007cs........2159B. arXiv:cs/0702159 . .
Fabiano C. Botelho and Nivio Ziviani. "External perfect hashing for very large key sets". 16th ACM Conference on Information and Knowledge Management (CIKM07), Lisbon, Portugal, November 2007.
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. "Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses". In Proceedings of the 20th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA), New York, 2009. ACM Press.
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. "Theory and practise of monotone minimal perfect hashing". In Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, 2009.
Douglas C. Schmidt, GPERF: A Perfect Hash Function Generator, C++ Report, SIGS,, November/December, 1998. „Тheory and practise of monotone minimal perfect hashing”. 10 (10). 1998.

Спољашње везе

Minimal Perfect Hashing by Bob Jenkins
gperf is an Open Source C and C++ perfect hash generator
cmph is Open Source implementing many perfect hashing methods
Sux4J is Open Source implementing perfect hashing, including monotone minimal perfect hashing in Java
MPHSharp is Open Source implementing many perfect hashing methods in C#

[inventor-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] Belazzougui, Djamal; Fabiano C. Botelho; Dietzfelbinger, Martin (2009). „Hash, displace, and compress” (PDF). Springer Berlin / Heidelberg. Приступљено 11. 8. 2011.

[3] Jenkins, Bob (14. 4. 2009), „order-preserving minimal perfect hashing”, Ур.: 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. ISBN 978-0-89791-408-6. doi:10.1145/96749.98233.

[1]

[2]

[3]

[4]