Content deleted Content added
JMarianczuk (talk | contribs) added disadvantages to perfect hashing to the summary Tag: Disambiguation links added |
Niceguyedc (talk | contribs) m v2.04 - disambiguate Yi Lu |
||
Line 11:
==Application==
A perfect hash function with values in a limited range can be used for efficient lookup operations, by placing keys from {{mvar|S}} (or other associated values) in a [[lookup table]] indexed by the output of the function. One can then test whether a key is present in {{mvar|S}}, or look up a value associated with that key, by looking for it at its cell of the table. Each such lookup takes [[constant time]] in the [[Worst-case complexity|worst case]].<ref name="inventor"/> With perfect hashing, the associated data can be read or written with a single access to the table.<ref>{{citation
| last1 = Lu | first1 = Yi | author1-link = Yi Lu (computer scientist)
| last2 = Prabhakar | first2 = Balaji | author2-link = Balaji Prabhakar
| last3 = Bonomi | first3 = Flavio | author3-link = Flavio Bonomi
| |||