Java Reference
In-Depth Information
Let's try to find a more efficient way to organize the numbers. Let's use more buckets, say 4, to store them. Any
number that is given to you will be stored in one of the four buckets. If you place a number in one of the four buckets
arbitrarily, it poses the same problem in searching. In the worst-case scenario, you will have to search all four buckets
for a number because you do not know which bucket contains a specific number. To avoid this inefficiency, let's use
an algorithm to place a specific number into a bucket.
To keep the algorithm simple, you will compute the modulus of the number by the number of buckets (four in
your case) and place the number in the bucket that corresponds to the modulus value. If you compute a modulus
of a number using 4, the value will be 0, 1, 2, or 3. You will name your four buckets as bucket-0, bucket-1, bucket-2,
and bucket-3. Which bucket will hold the number 17? The result of 17 modulus 4 is 1. Therefore, the number 17 will
go to the bucket-1. Where will number 31 go? The result of 31 modulus 4 is 3. Therefore, the number 31 will go to the
bucket-3. Figure
12-6
shows an arrangement in which you have used four buckets to store some numbers based on
this algorithm.
72 0 12 84
32 8 24 16
4 60 68 8
80
29 5 41 17
93 9 49 13
1 25 97
2 14 98 26
50 6 30 42
18 94
7 51 27 3
99 15 43 31
55 11
Bucket-0
Bucket-1
Bucket-2
Bucket-3
Figure 12-6.
Using four buckets to hold numbers
Let's walk through the steps to store a number in one of your four buckets. Suppose you are handed the number
94. Which one of the four buckets will store the number 94? First, you evaluate the result of 94 modulus 4, which is 2.
Therefore, the number 94 will be stored in the bucket-2. You will follow this logic to decide the bucket for every
number that you need to store.
Now, let's walk through the steps of verifying if a number exists in one of the buckets. Suppose you are asked to
verify if the number 67 exists in the collection. First, you compute the result of 67 modulus 4, which is 3. According
to the logic of storing a number, if the number 67 exists in the collection, it must exist in bucket-3. Once you know
the bucket number, you look at each number in the bucket (bucket-3 in this case) for that number. In this case (see
Figure
12-6
), there are ten numbers in bucket-3 and none of them is 67. After looking at ten numbers in bucket-3,
you respond that the number 67 does not exist in the collection. Note that you looked at numbers in only one of the
buckets to tell whether the number 67 existed in the collection or not. You did not have to look at numbers in all four
buckets. By using an algorithm to store and retrieve a number from the collection, you have shortened the time it
takes to search for a number in the collection.
The story is not over yet. Let's consider using four buckets to store numbers where all numbers are a multiple of
4 such as 4, 8, 12, 16, 20, 24, etc. The value of N modulus 4 for all N, which are multiple of 4 is 0. This means that all
such numbers will be stored in only one bucket, which is the bucket-0. Is this scenario better than storing all numbers
in only one bucket? The answer is no. Using multiple buckets helps in the search process only if the numbers that
are stored are uniformly distributed among all buckets. The best-case scenario is when all buckets have only one
number in them. In that case, you will be able to tell if a number exists in the collection by just looking at one number
in one of the buckets. The search performance may degrade as the size of the collection increases even if numbers
are distributed uniformly among the buckets. For example, suppose you have 100 numbers and they are uniformly
distributed among four buckets. In the worst-case scenario, you need to search through 25 numbers in a bucket.
Suppose the numbers increase to 10,000 and they are still uniformly distributed among the four buckets. Now, in the
