.. _PerfectHash:

.. raw:: html

   <script>ODSA.SETTINGS.DISP_MOD_COMP = true;ODSA.SETTINGS.MODULE_NAME = "PerfectHash";ODSA.SETTINGS.MODULE_LONG_NAME = "Perfect Hashing";ODSA.SETTINGS.MODULE_CHAPTER = "Searching"; ODSA.SETTINGS.BUILD_DATE = "2017-09-26 16:09:32"; ODSA.SETTINGS.BUILD_CMAP = false;JSAV_OPTIONS['lang']='en';JSAV_EXERCISE_OPTIONS['code']='java';</script>


.. |--| unicode:: U+2013   .. en dash
.. |---| unicode:: U+2014  .. em dash, trimming surrounding whitespace
   :trim:


.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012-2013 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata::
   :author: Cliff Shaffer
   :topic: Hashing

.. index:: ! perfect hashing

Perfect Hashing
===============

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.

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.

.. avembed:: AV/Development/perfectHashAV.html ss
   :module: PerfectHash
   :points: 0.0
   :required: True
   :threshold: 1.0
   :exer_opts: JXOP-debug=true&amp;JOP-lang=en&amp;JXOP-code=java
   :long_name: Perfect Hashing Visualization