In a chained hash table, elements reside in buckets extending from each position. In an open-addressed hash table, on the other hand, all elements reside in the table itself. This may be important for some applications that rely on the table being a fixed size. Without a way to extend the number of elements at each position, however, an open-addressed hash table needs another way to resolve collisions.

Whereas chained hash tables have an inherent means of
resolving collisions, open-addressed hash tables must handle them in
a different way. The way to resolve collisions in an open-addressed
hash table is to *probe* the table. To insert an element, for example, we probe
positions until we find an unoccupied one, and insert the element
there. To remove or look up an element, we probe positions until the
element is located or until we encounter an unoccupied position. If
we encounter an unoccupied position before finding the element, or
if we end up traversing all of the positions, the element is not in
the table.

Of course, the goal is to minimize how many probes we
have to perform. Exactly how many positions we end up probing
depends primarily on two things: the load factor of the hash table
and the degree to which elements are distributed uniformly. Recall
that the load factor of a hash table is α =
*n*/*m*, where
*n* is the number of elements and
*m* is the number of positions into which the elements may be hashed. Notice that ...

Start Free Trial

No credit card required