[This page is auto-generated; please prefer to read the article’s PDF Form.]
In a hashtable, the set of all possible keys is larger than the size of the hashtable. So, if the actual input keys are not known in advance, we can’t be sure if they would collide under any given hash-function. But if the input keys are known in advance — we call them “static-keys” — is it possible to find a hash-function giving no collision for these keys? We may call such function a “Collision-Free Function” for the given keys, and such method of hashing “Perfect Hashing”. With this hashing, the worst-case time complexity for finding a key is O(1), because there are no collisions.
In this article we discuss a method of Perfect Hashing proposed by Fredman, Komlós and Szemerédi in [1], often called “FKS Method”. Book [2]’s chapter “Hash Tables”, also provides a good description of this method.
[Next]
Copyright © 2021 Nitin Verma. All rights reserved.