Savršena heš funkcija

Savršena heš funkcija za skup S je heš funkcija koja povezuje različite elemente iz S u skup celih brojeva, bez heš preklapanja. Savršena heš funkcija je dosta slična ostalim heš funkcijama, ali uz prednost da razrešavanje sudara mora da se sprovede. Matematički, to je totalna injektivna funkcija.

Upotrebe i korišćenja[uredi | uredi izvor]

Savršena heš funkcija za određeni skup S koji može da se oceni u konstantnom vremenu, i sa vrednostima u malom opsegu, može se naći po slučajnom algoritmu po broju operacija koji je proporcionalan veličini skupa S.^[1] Minimalna veličina opisa savršene heš funkcije zavisi od raspona njenih vrednosti:Što je manji raspon, više prostora je potrebno. Svaka savršena heš funkcija pogodna za upotrebu sa heš tabelama zahteva najmanje broj bitova koji je proporcionalan veličini S.

Savršena heš funkcija sa vrednostima u ograničenom opsegu može da se koristi za efikasne operacije pretrage, postavljanjem ključeva iz S (ili druge odgovarajuće vrednosti) u tabelu koja je indeksirana po izlaznim vrednostima funkcije. Korišćenje savršene heš funkcije je najbolje u situacijama kada je često ispitivan veliki skup S, koji se retko ažurira. Efikasna rešenja za vršenje ispravke su poznati kao savršeno dinamično heširanje, ali ove metode su relativno komplikovane za sprovođenje. Jednostavna alternativa savršenog heširanja, koja takođe omogućava dinamične ispravke, je kukavičje sortiranje.

Minimalna savršena heš funkcija[uredi | uredi izvor]

Minimalna savršena heš funkcija je savršena heš funkcija koja mapira n ključeva za n uzastopnih celih brojeva-obično [0 ..n -1] ili [1. n.]. Formalniji način izražavanja je: Neka su j i k elementi nekog konačnog skupa K. F je minimalna savršena heš funkcija akko F(j) = F(K) sledi j = K (injekcija) i postoji ceo broj takav da je raspon od F a...a + |K | -1. Dokazano je da shema minimalne savršene heš funkcije opšte namene zahteva najmanje 1.44 bitova/ključeva ^[2] Međutim najmanja trenutno koristi oko 2.5 bita / ključa.

Minimalna savršena heš funkcija F čuva redosled ako su ključevi dati u nekom redosledu a₁,a₂, , ...an i za sve ključevea _j i a _K, J < K sledi (F(a_j) < F(a_k) ^[3] Minimalne perfektne heš funkcije koje čuvaju redosled zahtevaju Ω (n logn) bitova ^[4]

Minimalna savršena heš funkcija F je monotona ako čuva leksikografski redosled ključeva. Monotone minimalne savršene heš funkcije mogu da zauzimaju veoma mali prostor.

Vidi još[uredi | uredi izvor]

Reference[uredi | uredi izvor]

^ 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. Pristupljeno 11. 8. 2011.
^ Jenkins, Bob (14. 4. 2009), „order-preserving minimal perfect hashing”, Ur.: Black, Paul E., Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, Pristupljeno 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.

Literatura[uredi | uredi izvor]

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. Pronađeni su suvišni parametri: |author-link= i |authorlink= (pomoć) 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. „Theory and practise of monotone minimal perfect hashing”. 10 (10). 1998.

Spoljašnje veze[uredi | uredi izvor]

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. Pristupljeno 11. 8. 2011.

[3] Jenkins, Bob (14. 4. 2009), „order-preserving minimal perfect hashing”, Ur.: Black, Paul E., Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, Pristupljeno 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]