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

We start with an empty list. For each integer, we look for it in the list. If it is not found, it is added to the list and
counted. If it is found, there is nothing to do.
In solving this problem, a major design decision is how to search the list, which, in turn, will depend on how the
list is stored and how a new integer is added. The following are some possibilities:

1. The list is stored in an array, and a new integer is placed in the next available position

in the array. This implies that a sequential search must be used to look for an incoming
integer. This method has the advantages of simplicity and easy addition, but searching
takes longer as more numbers are put in the list.

2. The list is stored in an array, and a new integer is added in such a way that the list is always

in order. This may entail moving numbers that have already been stored so that the new
number may be slotted in the right place.

3. However, since the list is in order, a binary search can be used to search for an incoming

integer. For this method, searching is faster, but insertion is slower than in the previous
method. Since, in general, searching is done more frequently than inserting, this method
might be preferable to the previous method.

4. Another advantage here is that, at the end, the integers will be in order, if this is important.

If method 1 is used, the numbers will have to be sorted.

5. The list is stored as an unsorted linked list so must be searched sequentially. Since the

entire list must be traversed if an incoming number is not present, the new number can be
added at the head or tail; both are equally easy.

6. The list is stored as a sorted linked list. A new number must be inserted “in place” to

maintain the order. Once the position is found, insertion is easy. The entire list does not
have to be traversed if an incoming number is not present, but we are still restricted to a
sequential search.

7. The list is stored in a binary search tree. Searching is reasonably fast provided the tree

does not become too unbalanced. Adding a number is easy—it's only a matter of setting a
couple links. An in-order traversal of the tree will give the numbers in sorted order, if this is
required.

Yet another possibility is the method called hashing . As we will see, this has the advantages of extremely fast
search times and easy insertion.

10.2 Solving the Search and Insert Problem by Hashing
We will illustrate how hashing works by solving the “search and insert” problem for a list of integers. The list will be
stored in an array num[1] to num[n] . In our example, we will assume n is 12 .

num

1 2 3 4 5 6 7 8 9 10 11 12

Initially, there are no numbers in the list. Suppose the first incoming number is 52 . The idea behind hashing is to
convert 52 (usually called the key ) into a valid table location ( k , say). Here, the valid table locations are 1 to 12 .
If there is no number in num[k] , then 52 is stored in that location. If num[k] is occupied by another key, we say a
collision has occurred, and we must find another location in which to try to place 52 . This is called resolving the collision .