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

public static void main(String[] args) throws IOException {
Scanner in = new Scanner(new FileReader("numbers.in"));
int[] num = new int[N + 1];
for (int j = 1; j <= N; j++) num[j] = Empty;
int distinct = 0;
while (in.hasNextInt()) {
int key = in.nextInt();
int loc = key % N + 1;
while (num[loc] != Empty && num[loc] != key) loc = loc % N + 1;

if (num[loc] == Empty) { //key is not in the table
if (distinct == MaxDistinctNumbers) {
System.out.printf("\nTable full: %d not added\n", key);
System.exit(1);
}
num[loc] = key;
distinct++;
}
} //end while
System.out.printf("\nThere are %d distinct numbers\n", distinct);
in.close();
} //end main

} //end class DistinctNumbers

Suppose numbers.in contains these numbers:

25 28 29 23 26 35 22 31 21 26 25 21 31 32 26 20 36 21 27 24 35 23 32 28 36

When run, Program P10.1 prints the following:

There are 14 distinct numbers

Here are some notes on Program P10.1:

MaxDistinctNumbers ( 20 ) is the maximum amount of distinct numbers catered for. •

N ( 23 ) is the hash table size, a little bigger than MaxDistinctNumbers so that there is always at
least three free locations in the table.

•

num[1] to num[N] . If you want, num[0] may be used; in this case, the
hash function could simply be key % N .

• The hash table occupies

key is not in the table (an empty location is encountered), we first check whether the
number of entries has reached MaxDistinctNumbers . If it has, we declare the table full and do
not add key . Otherwise, we put key in the table and count it.

• If

key is found, we simply go on to read the next number. • If