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

■ We use while instead of if to perform the “wrap around” just in case the new location is more than twice the
table size. For instance, suppose n is 25, the increment is 42, and we are going forward from location 20. this will take us
to location 62. if we had used if , the “wrap around” location would be 62 - 25 = 37, which is still outside the range of
the table. With while , we will get the valid location 37 - 25 = 12.

Note

Could we have used loc % n instead of the while loop? In this example, we would get the correct location, but if
the new location were a multiple of n , loc % n would give 0 . This will be an invalid location if the table starts from 1 .
With quadratic probing, keys that hash to different locations trace different sequences; hence, primary clustering is
eliminated. However, keys that hash to the same location will trace the same sequence, so secondary clustering remains.
Here are some other points to note:

• n is a power of 2, that is, n = 2 m for some m , this method explores only a small fraction of the
locations in the table and is, therefore, not very effective.

If

• n is prime, the method can reach half the locations in the table; this is usually sufficient for
most practical purposes.

If

10.3.3 Chaining
In this method, all items that hash to the same location are held on a linked list. One immediate advantage of this is that
items that hash “near” to each other will not interfere with each other since they will not be vying for the same free space
in the table, as happens with linear probing. One way to implement chaining is to let the hash table contain “top of list”
pointers. For instance, if hash[1..n] is the hash table, then hash[k] will point to the linked list of all items that hash to
location k . An item can be added to a linked list at the head, at the tail, or in a position such that the list is in order.
To illustrate the method, suppose the items are integers. Each linked list item will consist of an integer value and
a pointer to the next item. We use the following class to create the nodes in the linked lists:

class Node {
int num;
Node next;

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

We can now define the array hash as follows:

Node[] hash = new Node[n+1]; //assume n has a value

We initialize it with this:

for (int h = 1; h <= n; h++) hash[h] = null;

Suppose an incoming key, inKey , hashes to location k . We must search the linked list pointed to by hash[k] for
inKey . If it is not found, we must add it to the list. In our program, we will add it such that the list is in ascending order.
We write Program P10.2 to count the number of distinct integers in the input file numbers.in . The program uses
hashing with chaining . At the end, we print the list of numbers that hash to each location.