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

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

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

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

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

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

Види још 
 Динамичко савршено хеширање
 Пирсон хеширање
 Универзално хеширање

Референце

Литература 
 Richard J. Cichelli. Minimal Perfect Hash Functions Made Simple, Communications of the ACM, Vol. 23, Number 1, January 1980.
  Section 11.5: Perfect hashing. pp. 245–249.
 .
 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.

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

 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#

Алгоритми претраживања
Савршена хеш функција за скуп С је хеш функција која повезује различите елементе из С у скуп целих бројева , без хеш преклапања . Савршена хеш функција је доста слична осталим хеш функцијама , али уз предност да разрешавање судара мора да се спроведе . Математички , то је тотална инјективна функција . Употребе и коришћења Савршена хеш функција за одређени скуп С који може да се оцени у константном времену , и са вредностима у малом опсегу , може се наћи по случајном алгоритму по броју операција који је пропорционалан величини скупа С . Минимална величина описа савршене хеш функције зависи од распона њених вредности:Што је мањи распон , више простора је потребно . Свака савршена хеш функција погодна за употребу са хеш табелама захтева најмање број битова који је пропорционалан величини С . Савршена хеш функција са вредностима у ограниченом опсегу може да се користи за ефикасне операције претраге , постављањем кључева из С ( или друге одговарајуће вредности ) у табелу која је индексирана по излазним вредностима функције . Коришћење савршене хеш функције је најбоље у ситуацијама када је често испитиван велики скуп С , који се ретко ажурира . Ефикасна решења за вршење исправке су познати као савршено динамично хеширање , али ове методе су релативно компликоване за спровођење . Једноставна алтернатива савршеног хеширања , која такође омогућава динамичне исправке , је кукавичје сортирање . Минимална савршена хеш функција Минимална савршена хеш функција је савршена хеш функција која мапира n кључева за n узастопних целих бројева-обично [ 0 \ ..n или [ 1. n . ] . Формалнији начин изражавања је : Нека су j и k елементи неког коначног скупа K . F је минимална савршена хеш функција акко F( ј ) = F( К ) sledi ј = К ( инјекција ) и постоји цео број такав да је распон од F a...a + |К | Доказано је да схема минималне савршене хеш функције опште намене захтева најманје44 битова / кључева Међутим најмања тренутно користи око5 бита / кључа . Минимална савршена хеш функција F чува редослед ако су кључеви дати у неком редоследу a,a , , \ ...an и за све кључевеa ј и a К , Ј < К следи ( F( aj ) < F( ak ) Минималне перфектне хеш функције које чувају редослед захтевају Ω ( n logn ) битова Минимална савршена хеш функција F је монотона ако чува лексикографски редослед кључева . Монотоне минималне савршене хеш функције могу да заузимају веома мали простор . Види још Динамичко савршено хеширање Пирсон хеширање Универзално хеширање Референце Литература Richard J. Cichelli . Minimal Perfect Hash Functions Made Simple , Communications of the ACM , Vol . Number January Section5 : Perfect hashing. pp.249. \ . Fabiano C . Botelho and Nivio Ziviani . " External perfect hashing for very large key sets" .h ACM Conference on Information and Knowledge Management ( CIKM07 ) , Lisbon , Portugal , November Djamal Belazzougui , Paolo Boldi , Rasmus Pagh , and Sebastiano Vigna . " Monotone minimal perfect hashing : Searching a sorted table with O( 1 ) accesses " . In Proceedings of theh Annual ACM-SIAM Symposium On Discrete Mathematics ( SODA ) , New York , 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 , Douglas C . Schmidt , GPERF : A Perfect Hash Function Generator , C++ Report , SIGS , , November / December , Спољашње везе 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 # Алгоритми претраживања