Content deleted Content added
m →Further reading: Replaced arXiv PDF link with more mobile-friendly abstract link, replaced: https://arxiv.org/pdf/ → https://arxiv.org/abs/ |
|||
Line 102:
| last1 = Belazzougui | first1 = Djamal
| last2 = Boldi | first2 = Paolo
| last3 = Pagh | first3 = Rasmus | author3-link = Rasmus Pagh
| last4 = Vigna | first4 = Sebastiano
| date = November 2008
Line 127:
==Related constructions==
A simple alternative to perfect hashing, which also allows dynamic updates, is [[cuckoo hashing]]. This scheme maps keys to two or more locations within a range (unlike perfect hashing which maps each key to a single ___location) but does so in such a way that the keys can be assigned one-to-one to locations to which they have been mapped. Lookups with this scheme are slower, because multiple locations must be checked, but nevertheless take constant worst-case time.<ref>{{citation
| last1 = Pagh | first1 = Rasmus | author1-link = Rasmus Pagh
| last2 = Rodler | first2 = Flemming Friche
| doi = 10.1016/j.jalgor.2003.12.002
Line 144:
*Richard J. Cichelli. ''Minimal Perfect Hash Functions Made Simple'', Communications of the ACM, Vol. 23, Number 1, January 1980.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Third Edition. MIT Press, 2009. {{ISBN|978-0262033848}}. Section 11.5: Perfect hashing, pp.267, 277–282.
* Fabiano C. Botelho, [[Rasmus Pagh]] and Nivio Ziviani. [https://arxiv.org/abs/cs/0702159 "Perfect Hashing for Data Management Applications"].
* 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.
* 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.
| |||