Close
Register
Close Window

OpenDSA Stand-alone Modules

Chapter 0 modules

Show Source |    | About   «  0.179. Bit Vectors for Representing Sets   ::   Contents   ::   0.181. Finding the Maximum Value  »

Perfect Hashing

1. Perfect Hashing

Perfect hashing is a technique for storing records in a hash table in a way that guarentees no collisions. Perfect hashing sort of turns the concept of hashing on its head, in that it requires that the full set of keys to be stored be available in advance, and a hash function is then generated for that key set. Besides guarenteeing no collisions, perfect hashing techniques can store n records in a table with only n slots.

Todo

type:text

Explain how Perfect Hashing works.

In this example, the set of keys is has already been selected to be the letters a to o. To see this in action, select "perfect hashing" as the hash method, select any collision resolution method, and select a hash table of size 15.

Todo

type:AV

Make a proper visualization for perfect hashing, that lets the user specify a set of input keys, computes the hash function, then lets the user input keys to the table. A proper explanation for the process should be part of the visualization.

   «  0.179. Bit Vectors for Representing Sets   ::   Contents   ::   0.181. Finding the Maximum Value  »

nsf
Close Window