Perfect hash function: Difference between revisions

Revision as of 14:02, 12 September 2022

Revision as of 11:23, 2 February 2023

Line 96:

==Extensions==

===Memory address identity===

A trivial but pervasive example of perfect hashing is implicit in the (virtual) [[Virtual Memory|memory address space]] of a computer. Since each byte of virtual memory is a distinct, unique, directly addressable storage ___location, the value of the (starting) [[Pointer_Pointer (computer_programmingcomputer programming)|address of any object]] stored in memory can be considered a ''de- facto'' perfect hash of that object into the entire memory address range.<ref>{{cite book|publisher=[[Springer Science+Business Media]]|url=https://books.google.com/books?id=66jBbZYOt-EC&pg=PA254|page=254|author1=Witold Litwin|author2=Tadeusz Morzy|author3=Gottfried Vossen|date=19 August 1998|isbn= 9783540649243|title=Advances in Databases and Information Systems}}</ref>

===Dynamic perfect hashing===

Line 205:

* Fabiano C. Botelho and [[Nivio Ziviani]]. [http://homepages.dcc.ufmg.br/~nivio/papers/cikm07.pdf "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. [https://web.archive.org/web/20140125080021/http://vigna.dsi.unimi.it/ftp/papers/MonotoneMinimalPerfectHashing.pdf "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.

* Marshall D. Brain and Alan L. Tharp. "Near-perfect Hashing of Large Word Sets". Software--PracticeSoftware—Practice and Experience, vol. 19(10), 967-078, October 1989. John Wiley & Sons.

* Douglas C. Schmidt, [http://www.dre.vanderbilt.edu/~schmidt/PDF/gperf.pdf GPERF: A Perfect Hash Function Generator], C++ Report, SIGS, Vol. 10, No. 10, November/December, 1998.