Hash Tables

An ArrayList encapsulates an array, a contiguous block of space in memory. Finding an object in an array requires serially traversing the array in order to find an element. The class java.util.HashMap is built around the hash table construct mentioned at the beginning of this lesson. It too is based on a contiguous block of space in memory.

I can pictorially represent a hash table as a bunch of slots (Figure 9.2).