Hashing Tutorial

AlgoViz Award 2010 Logo 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