Hashing Tutorial

Welcome to the interactive hashing tutorial! This tutorial does more than simply explain hashing and collision resolution. It will let you try out hash functions and collision resolution methods for yourself so that you can really see how they work. It will also let 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 what makes hashing work and why it is such a powerful technique.

Java note: The Java applets in this tutorial were compiled using Java 1.6. To run them, your browser must be equipped with Java 1.6 or later.

Section 1 - Introduction

Section 2 - Hash Functions

    Section 2.1 - Simple Mod Function

    Section 2.2 - Mid-Square Method

    Section 2.3 - Hash Functions for Strings

    Section 2.4 - 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