Java Reference
In-Depth Information
Figure 5
A Simplistic Implementation of a Hash Table
708
709
Then it is a very simple matter to find out whether an object is already present in the
set or not. Compute its hash code and check whether the array position with that hash
code is already occupied. This doesn't require a search through the entire array!
However, there are two problems with this simplistic approach. First, it is not possible
to allocate an array that is large enough to hold all possible integer index positions.
Therefore, we must pick an array of some reasonable size and then reduce the hash
code to fall inside the array:
int h = x.hashCode();
if (h < 0) h = -h;
h = h % size;
Furthermore, it is possible that two different objects have the same hash code. After
reducing the hash code modulo a smaller array size, it becomes even more likely that
several objects will collide and need to share a position in the array.
To store multiple objects in the same array position, use short node sequences for the
elements with the same hash code (see
Figure 6
). These node sequences are called
buckets.
