Perfect Hash Functions: Cichelli's Method for Strings

Perfect Hash Functions

Sometimes, when the data to be hashed is well behaved (has certain properties), it may be possible to construct a hash function that is perfect, i.e. there are no collisions. For example, if we want to hash a group of words (Strings) that are known in advance, we can use a method called Cichelli's Method shown in the video below. Not only does this result in a perfect hash function, but it is also a minimal perfect hash function because the size of the hash table only needs to fit exactly with the number of elements in the orignal data.

This video can be a bit difficult to understand. Here is a more detailed explanation of Cichelli's Method provided by the University of Vermont using Powerpoint Slides.

Quiz on Perfect Hashing

  1. 1 point
    Cichelli's Method contains heuristics. Furthermore, some similarities between the original data will render the method unusable. The presence of which two data elements in the original space will now allow Cichelli's Method to be used?