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

class Node {
int num;
Node next;

public Node(int n) {
num = n;
next = null;
}
} //end class Node

Suppose numbers.in contains the following numbers:

24 57 35 37 31 98 85 47 60 32 48 82 16 96 87 46 53 92 71 56
73 85 47 46 22 40 95 32 54 67 31 44 74 40 58 42 88 29 78 87
45 13 73 29 84 48 85 29 66 73 87 17 10 83 95 25 44 93 32 39

When run, Program P10.2 produces the following output:

There are 43 distinct numbers

hash[1]: 13 39 78
hash[2]: 40 53 66 92
hash[3]: 54 67 93
hash[4]: 16 29 42
hash[5]: 17 56 82 95
hash[6]: 31 44 57 83 96
hash[7]: 32 45 58 71 84
hash[8]: 46 85 98
hash[9]: 47 60 73
hash[10]: 22 35 48 74 87
hash[11]: 10 88
hash[12]: 24 37
hash[13]: 25

If m keys have been stored in the linked lists and there are n hash locations, the average length of a list is m

n , and

since we must search the lists sequentially, the average successful search length is m

2n . The search length can be

reduced by increasing the number of hash locations.
Another way to implement hashing with chaining is to use a single array and use array subscripts as links. We can
use the following declarations:

class Node {
int num; //key
int next; //array subscript of the next item in the list
}

Node[] hash = new Node[MaxItems+1];

The first part of the table, hash[1..n] , say, is designated as the hash table, and the remaining locations are used
as an overflow table, as shown in Figure 10-1 .