Hands-On Data Structures and Algorithms with Python - Second Edition

Perfect hashing functions

A perfect hashing function is the one by which we get a unique hash value for a given string (it can be any data type, here it is a string as we are limiting the discussion to strings for now). In practice, most of the hashing functions are imperfect and face collisions. This means that a hash function gives the same hash value to more than one string; that is undesirable because a perfect hash function should return a unique hash value to a string. Normally, hashing functions need to be very fast, so trying to create a function that gives us a unique hash value for each string is normally not possible. Hence, we accept this fact and we know that we may get some collisions, that is, two or more strings may have the ...