HASHING - Introduction to Java Programming: Comprehensive Version - page 987

function. When two or more keys are mapped to the same hash value, we say that a collision
has occurred. Although there are ways to deal with collisions, which are discussed later in this
chapter, it is better to avoid collisions in the first place. Thus, you should design a fast and
easy-to-compute hash function that minimizes collisions.

collision

27.1

✓ ✓

What is a hash function? What is a perfect hash function? What is a collision?

Check

Point

27.3 Hash Functions and Hash Codes
A typical hash function first converts a search key to an integer value called a hash
code, then compresses the hash code into an index to the hash table.

Key
Point
hash code
hashCode()

Java's root class Object has the hashCode method, which returns an integer hash code. By
default, the method returns the memory address for the object. The general contract for the
hashCode method is as follows:

1. You should override the hashCode method whenever the equals method is overridden
to ensure that two equal objects return the same hash code.
2. During the execution of a program, invoking the hashCode method multiple times
returns the same integer, provided that the object's data are not changed.

3. Two unequal objects may have the same hash code, but you should implement the
hashCode method to avoid too many such cases.

27.3.1 Hash Codes for Primitive Types
For search keys of the type byte , short , int , and char , simply cast them to int . Therefore,
two different search keys of any one of these types will have different hash codes.
For a search key of the type float , use Float.floatToIntBits(key) as the hash
code. Note that floatToIntBits(float f) returns an int value whose bit representation
is the same as the bit representation for the floating number f . Thus, two different search keys
of the float type will have different hash codes.
For a search key of the type long , simply casting it to int would not be a good choice,
because all keys that differ in only the first 32 bits will have the same hash code. To take the
first 32 bits into consideration, divide the 64 bits into two halves and perform the exclusive-
or operation to combine the two halves. This process is called folding . The hash code for a
long key is

byte, short, int, char

float

long

folding

int hashCode = ( int )(key ^ (key >> 32 ));

Note that >> is the right-shift operator that shifts the bits 32 positions to the right. For exam-
ple, 1010110 >> 2 yields 0010101 . The ^ is the bitwise exclusive-or operator. It operates
on two corresponding bits of the binary operands. For example, 1010110 ^ 0110111 yields
1100001 . For more on bitwise operations, see Appendix G, Bitwise Operations.
For a search key of the type double , first convert it to a long value using the
Double.doubleToLongBits method, and then perform a folding as follows:

double
folding

long bits = Double.doubleToLongBits(key);
int hashCode = ( int )(bits ^ (bits >> 32 ));

27.3.2 Hash Codes for Strings
Search keys are often strings, so it is important to design a good hash function for strings. An
intuitive approach is to sum the Unicode of all characters as the hash code for the string. This
approach may work if two search keys in an application don't contain the same letters, but