Perfect hash function: Difference between revisions

Revision as of 13:31, 6 March 2023

Revision as of 08:32, 17 March 2023

Line 16:

| last3 = Bonomi | first3 = Flavio | author3-link = Flavio Bonomi

| doi = 10.1109/ISIT.2006.261567

| journal = 2006 [[IEEE International Symposium on Information Theory]]

| pages = 2774–2778

| title = Perfect Hashing for Network Applications

| year = 2006| isbn = 1-4244-0505-X | s2cid = 1494710 }}</ref>

==Performance of perfect hash functions==

Line 42:

| title = Storing a Sparse Table with {{math|''O''(1)}} Worst Case Access Time

| volume = 31

| year = 1984| s2cid = 5399743 }}</ref>

As {{harvtxt|Fredman|Komlós|Szemerédi|1984}} show, there exists a choice of the parameter {{mvar|k}} such that the sum of the lengths of the ranges for the {{mvar|n}} different values of {{math|''g''(''x'')}} is {{math|''O''(''n'')}}. Additionally, for each value of {{math|''g''(''x'')}}, there exists a linear modular function that maps the corresponding subset of {{mvar|S}} into the range associated with that value. Both {{mvar|k}}, and the second-level functions for each value of {{math|''g''(''x'')}}, can be found in [[polynomial time]] by choosing values randomly until finding one that works.<ref name="inventor"/>

Line 167:

| 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

Line 180 ⟶ 181:

| 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>