Content deleted Content added
Niceguyedc (talk | contribs) m v2.04 - disambiguate Yi Lu |
JMarianczuk (talk | contribs) corrected summary statement about re-construction of the PHF (in non-dynamic case) |
||
Line 5:
Perfect hash functions may be used to implement a [[lookup table]] with constant worst-case access time. A perfect hash function can, as any [[hash function]], be used to implement [[hash table|hash tables]], with the advantage that no [[Hash table#Collision resolution|collision resolution]] has to be implemented. In addition, if the keys are not the data and if it is known that queried keys will be valid, then the keys do not need to be stored in the lookup table, saving space.
Disadvantages of perfect hash functions are that {{mvar|S}} needs to be known for the construction of the perfect hash function
The important performance parameters for perfect hash functions are the evaluation time, which should be constant, the construction time, and the representation size.
Line 98:
===Dynamic perfect hashing===
{{main article|Dynamic perfect hashing}}
Using a perfect hash function is best in situations where there is a frequently queried large set, {{mvar|S}}, which is seldom updated. This is because any modification of the set {{mvar|S}} may cause the hash function to no longer be perfect for the modified set. Solutions which update the hash function any time the set is modified are known as [[dynamic perfect hashing]],<ref name="DynamicPerfectHashing">{{citation
| last1 = Dietzfelbinger | first1 = Martin
| last2 = Karlin | first2 = Anna | author2-link = Anna Karlin
| |||