|
===Order preservation===
A minimal perfect hash function {{mvar|F}} is ''order preserving'' if keys are given in some order {{math|''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>}} and for any keys {{math|''a''<sub>''j''</sub>}} and {{math|''a''<sub>''k''</sub>}}, {{math|''j'' < ''k''}} implies {{math|''F''(''a''<sub>''j''</sub>) < F(''a''<sub>''k''</sub>)}}.<ref>{{Citation |first=Bob |last=Jenkins |contribution=order-preserving minimal perfect hashing |title=Dictionary of Algorithms and Data Structures |editor-first=Paul E. |editor-last=Black |publisher=U.S. National Institute of Standards and Technology |date=14 April 2009 |accessdate=2013-03-05 |url=https://xlinux.nist.gov/dads/HTML/orderPreservMinPerfectHash.html}}</ref> In this case, the function value is just the position of each key in the sorted ordering of all of the keys. A simple implementation of order-preserving minimal perfect hash functions with constant access time is to use an (ordinary) perfect hash function or [[cuckoo hashing]] to store a lookup table of the positions of each key. IfThis solution uses <math>O(n \log n)</math> bits, which is optimal in the setting where the comparison function for the keys tomay be hashedarbitrary.<ref>{{citation |last1=Fox |first1=Edward A. |title=Order-preserving minimal perfect hash functions and information retrieval |date=July 1991 |url=http://eprints.cs.vt.edu/archive/00000248/01/TR-91-01.pdf |journal=ACM Transactions on Information Systems |volume=9 |issue=3 |pages=281–308 |___location=New York, NY, USA |publisher=ACM |doi=10.1145/125187.125200 |s2cid=53239140 |last2=Chen |first2=Qi Fan |last3=Daoud |first3=Amjad M. |last4=Heath |first4=Lenwood S.}}.</ref> However, if the keys {{math|''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>}} are themselvesintegers storeddrawn infrom a sorteduniverse array<math>\{1, 2, \ldots, U\}</math> of polynomial size (i.e., <math>U = \text{poly}(n)</math>), then it is possible to storeconstruct aan smallorder-preserving numberhash offunction additionalusing only <math>O(n \log \log \log n)</math> bits perof keyspace<ref>{{citation in|last1=Belazzougui a|first1=Djamal data|title=Theory structureand thatpractice canof bemonotone usedminimal toperfect computehashing hash|date=November values2008 quickly|journal=Journal of Experimental Algorithmics |volume=16 |at=Art. no. 3.2, 26pp |doi=10.1145/1963190.2025378 |s2cid=2367401 |last2=Boldi |first2=Paolo |last3=Pagh |first3=Rasmus |last4=Vigna |first4=Sebastiano |author3-link=Rasmus Pagh}}.</ref>. Moreover, this bound is known to be optimal.<ref>{{citationCitation |last=Assadi |first=Sepehr |title=Tight Bounds for Monotone Minimal Perfect Hashing |date=2023-01 |url=http://dx.doi.org/10.1137/1.9781611977554.ch20 |work=Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=456–476 |access-date=2023-04-27 |place=Philadelphia, PA |publisher=Society for Industrial and Applied Mathematics |isbn=978-1-61197-755-4 |last2=Farach-Colton |first2=Martín |last3=Kuszmaul |first3=William}}</ref>
| last1 = Belazzougui | first1 = Djamal
| last2 = Boldi | first2 = Paolo
| last3 = Pagh | first3 = Rasmus | author3-link = Rasmus Pagh
| last4 = Vigna | first4 = Sebastiano
| date = November 2008
| doi = 10.1145/1963190.2025378
| journal = Journal of Experimental Algorithmics
| at = Art. no. 3.2, 26pp
| title = Theory and practice of monotone minimal perfect hashing
| volume = 16| s2cid = 2367401
}}.</ref> Order-preserving minimal perfect hash functions require necessarily {{math|''Ω''(''n'' log ''n'')}} bits to be represented.<ref>{{citation
| last1 = Fox | first1 = Edward A.
| last2 = Chen | first2 = Qi Fan
| last3 = Daoud | first3 = Amjad M.
| last4 = Heath | first4 = Lenwood S.
| date = July 1991
| doi = 10.1145/125187.125200
| issue = 3
| journal = ACM Transactions on Information Systems
| ___location = New York, NY, USA
| pages = 281–308
| publisher = ACM
| title = Order-preserving minimal perfect hash functions and information retrieval
| volume = 9| s2cid = 53239140
| url = http://eprints.cs.vt.edu/archive/00000248/01/TR-91-01.pdf
}}.</ref>
==Related constructions==
| 