Java Reference
In-Depth Information
A hash table can be implemented as an array of bucketsȌsequences of nodes that
hold elements with the same hash code.
Now the algorithm for finding an object
x
in a hash table is quite simple.
1. Compute the hash code and reduce it modulo the table size. This gives an index
h
into the hash table.
2. Iterate through the elements of the bucket at position
h
. For each element of the
bucket, check whether it is equal to
x
.
3. If a match is found among the elements of that bucket, then
x
is in the set.
Otherwise, it is not.
Figure 6
A Hash Table with Buckets to Store Elements with the Same Hash Code
709
710
In the best case, in which there are no collisions, all buckets either are empty or have
a single element. Then checking for containment takes constant or O(1) time.
