Java Reference
In-Depth Information
FIGURE 21-2
A collision caused by the hash function
h
h
(555-1214)
h
(555-8132)
150 Main Street
Collision
Hash table
21.5
General characteristics.
Any function can be a hash function if it produces an integer that is suit-
able as an array index. But not every such function is a
good
hash function. Our previous discus-
sions suggest that a good hash function should
•
Minimize collisions
•
Be fast to compute
Recall that a typical hash function first converts a search key to an integer hash code. The hash function
then compresses the hash code into an integer that is suitable as an index to the particular hash table.
Note:
To reduce the chance of a collision, choose a hash function that distributes entries
uniformly throughout the hash table.
First, consider how to convert a search key to an
int
. Realize that a search key can be either a
primitive type or an instance of a class.
21.6
The hash code for a class type.
Java's base class
Object
has a method
hashCode
that returns an
integer hash code. Since every class is a subclass of
Object
, all classes inherit this method. But unless
a class overrides
hashCode
, the method will return an
int
value based on the invoking object's mem-
ory address. This default hash code usually is not appropriate for hashing, because equal but distinct
