Searching ArrayLists

Objective #1: Use a sequential search algorithm with ArrayLists as well as arrays.

• The following algorithm searches through an ArrayList of Bot objects named botList for a Bot that has the name "fred":
  
  *********************** version with an ArrayList *************************
  
  boolean found = false;
  int position = -1;
  
  for (int i = 0; i < botList.size(); i++)
  {
     String next = botList.get(i).getName();
  
     if (next.equals("fred"))
     {
        found = true;
        position = i;
        break;
     }
  }
  
  if (found)
  {
     System.out.println("The key was found in position " + position);
  }
  else
  {
     System.out.println("The key was not found.");
  }
  
  
  
• Another useful algorithm is one that counts the number of occurrences of an object in an ArrayList or a value in array. Here are algorithms that count the number of occurrences of keyObject and the value 99 in an ArrayList and an array:
  
  
  *********************** version with an array *************************
  
  int count = 0;
  
  for (int i = 0; i < numbers.length; i++)
  {
     if (numbers[i] == 99)
     {
        count++;
     }
  }
  
  System.out.println("The key occurs " + count + " times.");
  
  
  *********************** version with an ArrayList *************************
  int count = 0;
  Integer keyObject = 99;   // autoboxing converts int value 99 to an Integer object
  
  for (int i = 0; i < numbersList.size(); i++)
  {
     Integer temp = numbersList.get(i);
  
     if (temp.equals(99)) // or if (temp.intValue() == 99)
     {
        count++;
     }
  }
  
  Notice that you can avoid using the Integer object temp by using
  
  if (numbersList.get(i).equals(99))
  {
     count++;
  }
  
  
  
• Another useful algorithm is one that finds the maximum (or minimum) value in an array or ArrayList. Study the following examples which find the greatest value in an ArrayList or array:
  
  *********************** version with an array *************************
  
  int max = numbers[0];   // or   int max = Integer.MIN_VALUE;
  int position = 0;
  
  for (int i = 1; i < numbers.length; i++)
  {
     if (numbers[i] > max)
     {
        max = numbers[i];
        position = i;
     }
  }
  
  System.out.println("The max value is " + max + " in position " + position);
  
  
  *********************** version with an ArrayList *************************
  
  Bot max = botList.get(0) ;
  int position = 0;
  
  for (i = 1; i < botList.size(); i++)
  {
     Bot temp = botList.get(i);
  
     if (temp.getAge() > max.getAge()) // or to avoid relying on unboxing if (temp.getAge().intValue() > max.getAge().intValue())
     {
        max = temp;
        position = i;
     }
  }
  
  System.out.println("The oldest Bot is " + max.getAge() + " years old and it is found in position " + position);
  
  You can avoid using the temp object with this if statement
  
  if (botList.get(i).getAge() > max.getAge())
  {
     max = botList.get(i);
     position = i;
  }
  
  
• Sometimes you may need to remove a certain element from an array or ArrayList.
  
  *********************** version with an array *************************
  
  // remove the zeros from the array
  int[] numbers = {2, 0, 0, 3, 4};
  
  for (int i = 0; i < numbers.length; i++)
  {
     if (numbers[i] == 0)
     {
        // shift existing numbers to the left
        for (int j = i + 1; j < numbers.length; j++)
           numbers[j] = numbers[j + 1];
     }
  }
  
  
  *********************** version with an ArrayList *************************
  
  ArrayList<Integer> numbers = new ArrayList<Integer>();
  numbers.add(2); numbers.add(0); numbers.add(0); numbers.add(3); numbers.add(4);
  
  for (i = 0; i < numbers.size(); i++)
  {
     if (numbers.get(i) == 0) // or if (numbers.get(i).intValue() == 0)
     {
        numbers.remove(i);
        i--;
     }
  }
  
  Trace the code above to understand why the loop variable i must be decremented. You can avoid this awkward step by using traversing the loop in the other direction or by using a while loop.
  
  for (i = numbers.size() - 1; i >= 0; i--)
  {
     if (numbers.get(i) == 0)
     {
        numbers.remove(i);
     }
  }
  
  or
  
  int i = 0;
  while(i < numbers.size())
  {
     if (numbers.get(i) == 0)
     {
        numbers.remove(i);
     }
     else
     {
        i++;
     }
  }
  

The following information will not be tested on the AP exam or unit tests. Mr. Minich keeps this material in his lecture notes for those students who "want to get ahead" in their study of computer science.

Objective #2: Trace and apply a hash algorithm.

• A lookup table (also known as a key-to-address transformation) can be used to allow very fast searches. Data elements are placed into a lookup table by converting some characteristic of each element into a specific position of the lookup table. Often the lookup table is a one or two-dimensional array.
  
  
• Sometimes, there is no good algorithm or function for mapping each different data element to a different position of the array. That is, two or more elements both map to the same position of the array. This problem is called a collision. If that happens, then there is no easy way to guarantee that someone can find the element they are searching for. They may find one of the other elements that mapped to the same array location.
  
  
• Hashing is a search algorithm that improves upon lookup tables by finding a way to minimize and resolve collisions. A hash function is used to convert a data element to a hash value. The hash function is essentially an assignment statement. For example, to hash a bunch of words into a hash table, you could use a hash function that finds the sum of the Unicode values for each letter in the word. The hash value is used to find a position for the element in a hash table. Like a lookup table, a hash table is simply a data structure such as a one or two-dimensional array. But it could also be an array of linked lists or a linked list of linked lists among other kinds of data structures that we haven't studied. The key difference though between using hashing and using a lookup table it that the hashing algorithm deals with collisions that occur.
  
  
• One way to handle collisions is to use a hash table data structure that allows two or more elements to both occupy the same position. By using a two-dimensional array where the row represents the initial hash values, you can place the original element into column 0 and the colliding element into column 1. A third element that collides to the same hash table row could be placed in column 3 and so one. This method for dealing with collisions is called chaining. Each row number in the two-dimensional array is called a bucket. Instead of a two-dimensional array, the hash table could be a one-dimensional array with a linked list or a binary search tree as a bucket attached to each row of the array.
  
  
• Another way to handle handle collisions is called probing. When a second element hashes to an already occupied hash table position, a probing function is used to find a new slot in the hash table. A real simple probing function would be to increment the position by one and place the second element into the next position in the hash table array. If that position is also occupied then the probing function could be applied again to send the element to the next position that is hopefully empty. A poor probing function such as this one (i.e. incrementing by one) leads to clustering with lots of data elements are settling into the same area of a hash table. It's better to balance the elements out throughout the table so quadratic probing is sometimes used. Where the probing function is index + n ^ 2 for each successive n.
  
  
• A big disadvantage to lookup tables and hashing is the large amount of memory that may be necessary. The size of the one or two-dimensional array used as the lookup or hash table may have to be very large to accomodate a poor hash function. If their is not a lot of data to put into the lookup or hash table, then the table will be very sparse.
  
  
• The time performance for a hash is O(1) in the best case and O(n) in its worst-case.