Hashing - Advanced Topics in Java: Core Concepts in Data Structures - page 284

The following shows the array after all the numbers have been inserted:

num

84 23 61 52 16 43 31 33 59

1

2 3 4 5 6 7 8 9 10 11 12

Note that if a number is already in the array, the method would find it. For example, suppose we are searching for 23.

•

23 hashes to 12 .
• num[12] is occupied and not by 23 .
We try the next location, • 1 ; num[1] is occupied and not by 23 .

We next try

num[2] ; num[2] is occupied by 23 —we find it.
Suppose we are searching for 33 ; 33 hashes to 10 , and num[10] contains 33 —we find it immediately.
As an exercise, determine the state of num after the previous numbers have been added using the hash function
H1(key) = key % 10 + 1 .
We can summarize the process described with the following algorithm:

•

//find or insert 'key' in the hash table, num[1..n]
loc = H(key)
while (num[loc] is not empty && num[loc] != key) loc = loc % n + 1
if (num[loc] is empty) { //key is not in the table
num[loc] = key
add 1 to the count of distinct numbers
}
else print key, " found in location ", loc

Note the expression loc % n + 1 for going to the next location. If loc is less than n , loc % n is simply loc , and
the expression is the same as loc + 1 . If loc is n , loc % n is 0, and the expression evaluates to 1 . In either case, loc
takes on the value of the next location.
Alert readers will realize that we exit the while loop when either num[loc] is empty or it contains the key. What
if neither happens so the while loop never exits? This situation will arise if the table is completely full (no empty
locations) and does not contain the key we are searching for.
However, in practice , we never allow the hash table to become completely full. We always ensure that there are a
few “extra” locations that are not filled by keys so that the while statement will exit at some point. In general, the hash
technique works better when there are more free locations in the table.
How does the algorithm tell when a location is “empty”? We will need to initialize the array with some value that
indicates “empty.” For instance, if the keys are positive integers, we can use 0 or -1 as the empty value.
Let's write Program P10.1, which reads integers from a file, numbers.in , and uses a hash technique to determine
the number of distinct integers in the file.

Program P10.1

import java.util.*;
import java.io.*;
public class DistinctNumbers {
final static int MaxDistinctNumbers = 20;
final static int N = 23;
final static int Empty = 0;