Hash tables - Data Structures and Problem Solving Using Java - page 786

If quadratic probing is used and the table size is prime, then a new element can
always be inserted if the table is at least half empty. Furthermore, in the course of the
insertion, no cell is probed twice.

Theorem 20.4

Proof

Let M be the size of the table. Assume that M is an odd prime greater than 3. We
show that the first M 2⁄ H 2 alternative locations (including the original) are distinct.

Two of these locations are + ( mod M ) and H 2 + ( mod M ) , where

0 ≤ i , j ≤⎣ M /2⎦ . Suppose, for the sake of contradiction, that these two locations are

the same but that ij ≠ . Then

H 2 + H 2 mod M ≡ + ( )

i 2 ≡ j 2 ( mod M )

i 2 - j 2 ≡ 0 mod M ( )

( ij - ) ( ij + ) ≡ 0 mod M ( )

Because M is prime, it follows that either or is divisible by M . As i and j are
distinct and their sum is smaller than M , neither of these possibilities can occur. Thus
we obtain a contradiction. It follows that the first alternatives (including the
original location) are all distinct and guarantee that an insertion must succeed if the
table is at least half empty.

i - ij +

M 2 ⁄

routine that generates prime numbers, using the algorithm shown in Figure 9.8
(a more complex algorithm is not warranted).
If the table is even 1 more than half full, the insertion could fail (although fail-
ure is extremely unlikely). If we keep the table size prime and the load factor
below 0.5, we have a guarantee of success for the insertion. If the table size is not
prime, the number of alternative locations can be severely reduced. For example,

1 /**
2 * Method to find a prime number at least as large as n.
3 * @param n the starting number (must be positive).
4 * @return a prime number larger than or equal to n.
5 */
6 private static int nextPrime( int n )
7 {
8 if( n % 2 == 0 )
9 n++;
10
11 for( ; !isPrime( n ); n += 2 )
12 ;
13
14 return n;
15 }

figure 20.8
A routine used in
quadratic probing to
find a prime greater
than or equal to N