Hashing Tutorial

Welcome to the interactive hashing tutorial. This tutorial does more than simply explain hashing and collision resolution. It lets you try out hash functions and collision resolution methods for yourself so that you can really see how they work. It also lets you compare different methods to see how well they perform in various situations.

There are many activities scattered throughout these pages. If you spend some time with each one, at the end you will understand how to build an efficient hashing system.

Students: Please make sure that your screen resolution is at least 1024x768, and that your browser is equipped with Java 1.5 or later. Also, please reset your browser's page zoom before continuing, as zooming in and out will distort the Java applets and make them unusable.

Section 1 - Introduction

Section 2 - Hash Functions

    Section 2.1 - Simple Mod Function

    Section 2.2 - Binning

    Section 2.3 - Mid-Square Method

    Section 2.4 - Hash Functions for Strings

    Section 2.5 - Summary of Hash Functions

Section 3 - Open Hashing

Section 4 - Bucket Hashing

Section 5 - Collision Resolution

Section 6 - Improved Collision Resolution Methods

    Section 6.1 - Linear Probing by Steps

    Section 6.2 - Pseudo-random Probing

    Section 6.3 - Quadratic Probing

    Section 6.4 - Double Hashing

Section 7 - Analysis of Closed Hashing

Section 8 - Deletion

NEXT: Section 1 - Introduction

This tutorial was created by the Virginia Tech Algorithm Visualization Research Group. This work is available for your use, under conditions of the Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License. The text is Copyright 2007-2011 by Clifford A. Shaffer. Sourcecode for the Java Applets is available under Gnu Public License Version 3.0. For more information about the authoring of this tutorial, see the About this Tutorial page.

[Last updated: 10/27/2011]