Java Collections Framework Part 2 - Basics

This is the sixth part of the tutorial, and this link goes to the previous post java collections framework part 1

Iterator

An iterator is an object that implements the interface java.util.Iterator, it has three methods hasNext(), next() and remove().

Iterators are used to traverse or access a collection in a standard way, the java.util.Collection interface provides the iterator() method so any collection that implements this interface provides a way to return an iterator.

Example:

 Iterator it = collection.iterator() ;  
 while( it.hasNext() ) {  
  System.out.println(it.next());  
 }  

Iterable

The java.lang.Iterable interface was introduced in Java 5, it just has the iterator() method and

the java.util.Collection interface extends from this interface. The Iterable interface is used in the foreach statement in this way, any class that implements the Iterable interface could be used in the foreach statement.

The advantages of the foreach statement are that the code needed to traverse a collection is reduced and that no casts are needed to access the elements of a collection.

Example

 for(Object o : collection) {
  System.out.println(o);
}

In the example the code looks much more cleaner than before.

A precaution to take with iterators is that they are fail-fast, they check collection has not changed. If they detect a change, a java.util.ConcurrentModificationException exception is thrown.

This means if a collection is modified while it is being iterated a ConcurrentModificationException is thrown.

Generics and collections

Generics were introduced in Java 5, before that collections could hold any kind of object, there was no way to guarantee collection type.

Since collections could hold any type of object, there were no ways to prevente runtime errors such cast exceptions.

Example:

List list = new ArrayList();
list.add(new Person());
String s = (String) list.get(0);

The example would rise a ClassCastException.

With generics collections have a way to do a compile time check by enforcing the type of your collections. All what it needs is just place the type of the collection between angle brackets.

Example:

List <String> list = new ArrayList <String> ();
list.add(new Person());//Compiler error

Another advantage is that since the type is now specified at compile, then the cast for getting an element could be omitted because now the compiler can check if what you are doing is correct.

Example:

List <String> list = new ArrayList <String> ();
String s = list.get(0);

Also collection can be iterated in a for-each statement or with an Iterator with its own type without doing any cast.

Example:

for (String s : list) {
 ...
}
.....
Iterator it = collection.iterator() ;
while( it.hasNext() ) {
  String s = it.next();
}

There is a wildcard in collections and generics the “? “ question mark symbol, you have to be very careful if you used it has many behaviors and restrictions and I would recommend you to do a further research of it.

If it is used alone in a collection, it means it can hold any type of object, but you can not add any element to it, since the compiler doesn't know its exact type.

Example:

List <?> list = new ArrayList <String> ();  
list.add(“Hello world”);//compiler error  

If it is used with the extends keyword, it means it can hold any type that extends or implements the type specified, but still can not add elements to it, since the compiler doesn't know its exact type.

Example:

 List <? extends CharSequence> list = new ArrayList <String> ();//OK  
 List <? extends CharSequence> list = new ArrayList <StringBuffer> ();//OK  

If it is used with the super keyword, it means it can hold any super type of the type specified, in this case elements can be added but of the same type or subtype of the right element in the super expression.

Example:

 class Employee extends Person   
 .......  
 List <? super Employee> list = new ArrayList <Person> ();  
 list.add(new Employee);  

In the exapmle the class Employee extends Person, so the list can add any element of type Employee of a subtype of it.

Java 7 added type inference which says “You can replace the type arguments required to invoke the constructor of a generic class with an empty set of type parameters (<>) as long as the compiler can infer the type arguments from the context”.

Example

 List<String> list = new ArrayList<>();  
 list.add("A");//OK  

As I said before there are many other restrictions with generics so you better check them, before start using them.

The java.util.Collection interface

The Collection interface defines the core functionality of almost every collection, Maps are different.

It defines the following methods:

Adding Elements

boolean add(E e):Ensures that this collection contains the specified element (optional operation).

boolean addAll(Collection<? extends E> c): Adds all of the elements in the specified collection to this collection (optional operation).

Removing Elements

void clear():Removes all of the elements from this collection (optional operation).

boolean remove(Object o): Removes a single instance of the specified element from this collection, if it is present (optional operation).

boolean removeAll(Collection<?> c): Removes all of this collection's elements that are also contained in the specified collection (optional operation).

boolean retainAll(Collection<?> c): Retains only the elements in this collection that are contained in the specified collection (optional operation).

Contents of collection

boolean contains(Object o): Returns true if this collection contains the specified element.

boolean containsAll(Collection<?> c): Returns true if this collection contains all of the elements in the specified collection.

boolean isEmpty(): Returns true if this collection contains no elements.

int size(): Returns the number of elements in this collection.

Processing contents

Iterator<E> iterator(): Returns an iterator over the elements in this collection.

Object[] toArray(): Returns an array containing all of the elements in this collection.

<T> T[] toArray(T[] a): Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.

Go to part 3

Java Collections Framework Part 1 - Intro

Continuing with another series of articles about java, now I'm going to try to explain the java collections framework, hoping you can get something from it.

A collection in java is an object that represents a data structure which groups data or other objects.

The collection framework is a set of interfaces and classes from the packages java.util and java.util.concurrent, some of the core interfaces are Collection, Set, List, Map, Queue, SortedSet, SortedMap, and so on. Each one of these interfaces has a model or structure for organizing objects.

The next figure shows the interface and class hierarchy of the interfaces and classes in the collection framework.

The basic operations in a collection are add, remove and find an object, also iterate objects through the collection.

The main types of collections are List, Set , Queue and Map. List, Set, Queue extend from the Collection interface, and Map doesn't, a brief description of each type of collection is the following:

List: A list is a collection that groups objects with an order, assigns an index to each element.

Set: A set is a collection that groups object without an order and without duplicates, each element is unique.

Queue: A queue is a collection that groups objects with a certain order, they are arranged by the order in which they are processed.

Map: A map is a collection that associates each object with an identifier, it uses key-value associations to store and retrieve elements, also the identifiers must be unique.

Each of this type is represented by an interface in the collection framework as the previous figure shows, and an implementation of a collection (concrete class) implements one of this interface to define its type, but it can implement other interfaces to add or achieve another behavior.

A collection can be sorted, unsorted, ordered and unordered.

An ordered collection is a collection that can be iterated in a specific order, lists are indexed so they can be iterated through their index, another order would be the LIFO (Last-In, First-Out) or FIFO (First-In, First-Out) collections.

A sorted collection is a collection that its elements were set by a rule, like a natural order, its position in the collection is determined by a condition or rule set by the programmer. To achieve this the collection framework uses the java.lang.Comparable interface and the java.util.Comparator interface.

There are some restrictions or recommendations in the implementation of the elements of some collections such as the ones that no duplicate are allowed or its elements are sorted. So is good to know some of these before getting into these collections.

The equals() method of the java.lang.Object class tests if two objects are equal, if this method is not overridden in an object its behavior is given by its default implementation which only tests if two objects reference are the same like the “==” operator. To provide a better implementation of the equals() it must be overridden and test if the variables of an object are the same to one that is compared to .

Example

 public class Person {  
      private String name;  
      ...  
       public boolean equals(Object obj) {  
           if (this == obj) {  
             return true;       
           }  
           if (!obj instanceof Person) {  
             return false;  
           }  
           .......  
           return this.name.equalsIgnoreCase((((Person)obj).name);  
      }  
 }  

In the example, the equals() test for if the name of the objects is the same then both objects are equal.

The hashCode() method of the java.lang.Object class returns a hashcode for the object and its contract says If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result, if two objects are unequal() it is recommended to return different values.

In order to accomplish this restriction of two equal objects return the same hashcode, it is recommended to use in the hashcode() the same instance variables used in the equals().

Example

 public class Person {  
      private String name;  
      ...  
       public boolean equalsIgnoreCase(Object obj) {  
           if (this == obj) {  
             return true;       
           }  
           if (!obj instanceof Person) {  
             return false;  
           }  
           .......  
           return this.name.equals(((Person)obj).name);  
      }  
      public int hashCode() {   
           return this.name.hashCode();   
      }  
 }  

In the example two equals objects would return the same hashcode and two different objects would return different hashcodes.

You have to know that there is more about these methods or contracts, but for the purpose of the blog with this basic information is alright.

These methods are used in the “hash“ collections that don't allow duplicate elements.

The java.lang,Comparable interface must be implemented by elements of a collection that is sorted, it helps to give a natural order to the collection. It only has the compareTo() method, it compares ans object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

Example:

 public class Person implements Comparable <Person>{  
      private String name;  
      ......       
      public int compareTo(Person p) {   
           return this.name.compareTo(p);   
      }  
 }  

In the expample since the name attribute is a String an Strings implement the comparable interface the is ok to call this method on the attribute.

Go to part 2

Java Concurrency Part 7

This is the seventh and final part of the tutorial, and this link goes to the previous post java concurrency part 6

Utility Classes For Synchronization

A semaphore has a counter that allows the access to a shared resource, it is similar to the Lock interface but when a thread wants to acquire a semaphore it checks its counter and if it is greater than zero, then the thread acquires the semaphore and it decrements the counter. But if the counter is zero the thread waits until the counter is incremented.

Example:

 public class Resource {  
      Semaphore semaphore = new Semaphore(2);//Indicates two threads can access the resource at the same time.  
      public void lock() {  
           semaphore.acquire();//If the counter is zero the thread sleeps otherwise it decrements it and gets the access  
           System.out.println(“Begining thread ” + Thread.currentThread().getName() + “has the lock”);  
           try {                           
                Thread.sleep(10000);  
           } catch (InterruptedException e) {  
                e.printStackTrace();  
           }  
           System.out.println(“Ending thread ” + Thread.currentThread().getName() + “has the lock”);  
           semaphore.release();//Release the semaphore and increments the counter  
      }  
 }  
 .......  

In the example the acquire() method obtains the semaphore if the counter is greater than zero, otherwise it waits until it increments and decrements the counter, then the thread that obtains the semaphore execute the resource and finally it executes the release() method and increments the counter.

If the semaphore initializes its counter with a value of one then it is called a binary semaphore and it behaves just like the java.util.concurrent.locks.Lock interface.

CountDownLatch

The CountDownLatch can be used to make one thread wait until N threads have completed some action, or some action has been completed N times. It has a count and it is initialized with an integer value, this count is the number actions to wait for.

The CountDownLatch has the method countdown() method which decreases the internal count, and the await() method blocks or puts to sleep a thread until the count reaches zero.

Example:

 public class Test implements Runnable {  
   //CountDownLatch controls the answer of 10 questions  
   private final CountDownLatch controller = new CountDownLatch(10);  
   public void setQuestionAnswered(){  
     controller.countDown();// Decrements the counter   
   }  

   public void run() {  
      try {  
       controller.await();// Wait for all the question to be answered  
       // Starts the test evaluation  
     } catch (InterruptedException e) {  
       e.printStackTrace();  
     }  
   }    
 }  

In the example the task Test will wait to evaluate until all the questions of the test are answered.

Other tasks will call the setQuestionAnswered() which calls the countDown(), decreasing the counter, since the CountDownLatch is initialized with a value of 10, the countDown() method has to be called 10 times in order to proceed after the await() method to evaluate the test.

CyclicBarrier

The CyclicBarrier allows to a set of threads to all wait for each other or to reach a common barrier point, it is simlar to the CountDownLatch class, but it has some diferences. It is also initialized with an integer value known as parties or the number of threads involve, but it has an optional parameter which is a Runnable that will be executed when the threads arrive the common point.

The CyclicBarrier has the await() method which blocks until all the parties invoke this method.

Example:

 public class Test implements Runnable {    
   private CountDownLatch controller = new CountDownLatch(10);  
   private CyclicBarrier cyclicBarrier;  
   public Test(CyclicBarrier cyclicBarrier) {  
      this.cyclicBarrier = cyclicBarrier;  
   }  
   public void setQuestionAnswered(){  
     controller.countDown();  
   }  
   @Override  
   public void run() {  
      try {  
       controller.await();  
       // Starts the test evaluation  
       cyclicBarrier.await();//WAITS FOR ALL THREADS OR PARTIES  
     } catch (InterruptedException e) {  
       e.printStackTrace();  
     }  
   }    
   public double getTestResult() {  
   }  
 }  
 ..........  
 final Test [] tests = new Test[10];  
 CyclicBarrier cyclicBarrier = new CyclicBarrier(10,  
       new Runnable(){  
           public void run() {  
                //Get the media or average of the tests  
                ..........  
           }                                
      });  
 for(int i=0; i<tests.length; i++)  
      tests[i] = new Test(cyclicBarrier);  
 ..........  

In the example the same Test class used as in the previous example, but here the CyclicBarrier will get the average or media result from all the tests. When all the Test thread finish the exam the CyclicBarrier will execute the Runnable object that is passed as parameter and will get the average of the tests.

Phaser

The Phaser class is similar to CyclicBarrier and CountDownLatch but more flexible, the tasks or threads synchronize in steps or phases. The parties registered to synchronize on a phaser may vary over time, it can dynamically change with the methods register(), bulkRegister().

The arriveAndDeregister() mehtod notifies the phasar that a task has finished and will not participate in future phases decreasing the number of parties.

The arriveAndAwaitAdvance() method makes a task wait for all the participants to finish.

Example:

 public class Task implements Runnable {      
   private Phaser phaser;  
   public Task(Phaser phaser) {  
      this. phaser = phaser;  
  }  
   @Override  
   public void run() {  
      try {  
       phaser.arriveAndAwaitAdvance();  
      //Start phase1       
      phaser.arriveAndAwaitAdvance();  
      //Start phase2  
      phaser.arriveAndAwaitAdvance();  
      //Start phase3            
     } catch (InterruptedException e) {  
       e.printStackTrace();  
     }  
   }    
 }  
 ..........  
 final Task [] tasks = new Task[10];  
 Phaser phaser = new Phaser(10);  
 for(int i=0; i<tasks .length; i++)  
      tasks[i] = new Task(phaser);       
 ..........  

In the example the phaser is set to 10 parties, when all the tasks reach the first arriveAndAwaitAdvance() they will start the phase 1 and then they will have to wait to all threads again before they start phase 2, and so on.

Exchanger

The Exchanger class synchronizes two threads in a point, when both get to this point they swap or interchange an object. An Exchanger may be viewed as a bidirectional form of a SynchronousQueue.

The Exchanger class has the exchange() method which interchanges data between threads.

The producer consumer example can be implemented with this mechanism.

Example:

 public class Consumer extends Thread {  
      private Exchanger <String> exchanger;  
      public Consumer(Exchanger exchanger) {  
           this.exchanger = exchanger;  
      }  
      public void run() {  
           String message = "";  
           while (!message.equalsIgnoreCase("end")) {  
                //message = mb.take();  
                try {  
                     message = exchanger.exchange(message);//Waits and exchanges messages with the producer;  
                     System.out.print(message + " ");  
                } catch (InterruptedException e) {  
                     e.printStackTrace();  
                }  
           }            
      }       
 }  
 public class Producer extends Thread {  
      private Exchanger exchanger;  
      public Producer(Exchanger exchanger) {  
           this.exchanger = exchanger;  
      }  
      public void run() {  
           String [] messages = {"Hello", "world", "end"};  
           for (String msg:messages) {  
                try {  
                     exchanger.exchange(msg);//Waits and exchanges messages with the consumer;                 
                } catch (InterruptedException e) {  
                     e.printStackTrace();  
                }  
           }  
      }            
 }  
 .......  
      Exchanger <String> exchanger = new Exchanger<String>();   
           Consumer consumer = new Consumer(exchanger);  
           Producer producer = new Producer(exchanger);  
           consumer.start();  
           producer.start();  
 .......  

This example is similar to the one in the part 4, but instead of having a class that acts as a monitor, here the Exchanger does that job and synchronizes the messages between the threads.

Java Concurrency Part 6

This is the sixth part of the tutorial, and this link goes to the previous post java concurrency part 5

Fork/Join Framework

The fork/join framework is an implementation of the ExecutorService interface that uses a different approach, it solves tasks splitting them into smaller tasks recursively.

The fork/join framework implements the work-stealing algorithm, this algorithm says worker threads that run out of things to do can steal tasks from other threads that are still busy. Put it in another way, it says a thread that is waiting for the finalization of other threads, looks for threads that have not been executed and executes them.

Basically there are two operations, one to divide a task into smaller tasks “fork”, and other to wait for the tasks to finalize “join”.

The java.util.concurrent.ForkJoinPool class implements the ExecutorSevice interface and also implements the work-stealing algorithm.

The java.util.concurrent.ForkJoinTask class implements the Future interface, is an abstract class for the tasks that execute within the ForkJoinPool, provides the fork() method to arrange asynchronous execution and the join() method for proceed until the task's result has been computed.

Example:

 public class IncrementTask extends RecursiveAction {      
   private int [] array;  
   private int first;  
   private int last;  

   public IncrementTask(int [] array, int first, int last) {  
     this.array = array;  
     this.first = first;  
     this.last = last;  
   }  
   protected void compute() {  
     if (last - first < 10) {  
       increment();  
       System.out.println("Completed from "+first+", to: "+last);  
     } else {  
       int middle = (last + first) / 2;  
       System.out.println("Pending tasks: " + getQueuedTaskCount());  
       IncrementTask it1 = new IncrementTask(array, first, middle + 1);  
       IncrementTask it2 = new IncrementTask(array, middle + 1, last);  
       invokeAll(it1, it2); //Waits for the finalization of these tasks  
     }  
   }  
   private void increment() {  
     for (int i = first; i < last; i++) {  
       array[i] = ++array[i];        
     }      
   }  
 }  
 ...............  
     int array [] = new int [100];  
     Random random = new Random();  
     for (int i=0; i<array.length; i++) {  
       array[i] = random.nextInt(10000);  
     }      
     System.out.print("Array: {");   
     for (int i=0; i<array.length; i++) {      
       System.out.print(array[i] + ", ");  
     }  
     System.out.print(" }");   
     IncrementTask task = new IncrementTask(array, 0, array.length);      
     ForkJoinPool pool = new ForkJoinPool();      
     pool.execute(task);      
     do {  
       System.out.println("Threads active: " + pool.getActiveThreadCount());        
       try {  
         TimeUnit.MILLISECONDS.sleep(5);  
       } catch (InterruptedException e) {  
         e.printStackTrace();  
       }  
     } while (!task.isDone());      
     pool.shutdown();  
     if (task.isCompletedNormally()) {  
       System.out.println("The process has completed normally");  
     }  
     System.out.print("Array incremented: {");   
     for (int i=0; i<array.length; i++) {      
       System.out.print(array[i] + ", ");  
     }  
     System.out.print(" }");   
 ...............  

In the example the IncrementTask class extends the java.util.concurrent.RecursiveAction class, this task implements its logic int the compute() method, it increments the value of the elements of an array of integers. But it only increments 10 elements per task, if the size of the array is bigger than that, it creates two subtasks and executes them through the invokeAll() method of the RecursiveAction class. In this way the tasks are calling recursively.

The RecursiveAction class extends the ForkJoinTask class, it has the invokeAll() method which executes subtasks and waits for its finalization before continuing, while it is waiting for the subtasks to end, the worker thread takes another task and excutes it.

The Fork/Join framework provides another class to return a value from a task, the java.util.concurrent.RecursiveTask this class behaves just like the RecursiveAction class but its compute() method returns a value.

Example:

 public class SumTask extends RecursiveTask <Integer> {  
   private int [] array;  
   private int first;  
   private int last;  
   public SumTask(int[] array, int first, int last) {  
     this.array = array;  
     this.first = first;  
     this.last = last;  
   }  
   protected Integer compute() {  
     int sum = 0;  
     if (last - first < 10) {  
       sum = add();  
       System.out.println("Completed from "+first+", to: "+last);  
     } else {  
       int middle = (last + first) / 2;  
       System.out.println("Pending tasks: " + getQueuedTaskCount());  
       SumTask st1 = new SumTask(array, first, middle + 1);  
       SumTask st2 = new SumTask(array, middle + 1, last);  
       invokeAll(st1, st2);        
       try {  
         sum += st1.get();  
         sum += st2.get();  
       } catch (Exception ex) {  
         ex.printStackTrace();  
       }         
     }      
     return sum;  
   }  
   private Integer add() {  
     int sum = 0;  
     for (int i = first; i < last; i++) {  
       sum += array[i];        
     }      
     return sum;  
   }  
 }  
 ......................  
     int array [] = new int [100];  
     Random random = new Random();  
     for (int i=0; i<array.length; i++) {  
       array[i] = random.nextInt(100);  
     }      
     System.out.print("Array: {");   
     for (int i=0; i<array.length; i++) {      
       System.out.print(array[i] + ", ");  
     }  
     System.out.print(" }");   
     SumTask task = new SumTask(array, 0, array.length);      
     ForkJoinPool pool = new ForkJoinPool();      
     pool.execute(task);      
     do {  
       System.out.println("Threads active: " + pool.getActiveThreadCount());        
       try {  
         TimeUnit.MILLISECONDS.sleep(5);  
       } catch (InterruptedException e) {  
         e.printStackTrace();  
       }  
     } while (!task.isDone());      
     pool.shutdown();  
     if (task.isCompletedNormally()) {  
       System.out.println("The process has completed normally");  
     }  
     try {   
       System.out.print("Array sum is:" + task.get());  
     } catch (Exception ex) {  
       ex.printStackTrace();;  
     }  
 ......................  

In the example the SumTask class extends the RecursiveTask class with Integer as its type, the SumTask will add all the elements of an array. But it only adds 10 elements per task, if the size of the array is bigger than that, then it creates two subtasks and executes them through the invokeAll() method of the RecursiveTask class just as the previous example, but in contrast to the previos example each task returns the sum of the 10 elements, and if subtasks were created then adds the result of the subtasks.

The value from the subtasks is obtained with the get() method from the Future interface.

Until now all the tasks have been executed synchronously, when a task calls the invokeAll() method it waits until the tasks sent to execute through this method finish, with this the work-stealing algorithm is implemented, assigning a new task to the worker when the task is waiting.

Tasks also can be executed asynchronous with the fork() and join() methods of the ForkJoinTask calss, the fork() method executes asynchronously a subtask continuing with the execution of the task, and the join() method waits for the result of the subtask.

Using this mechanism the work-stealing algorithm can not be implemented since the task continues executing when creates a subtask.

Example:

 public class SumTaskAsync extends RecursiveTask <Integer> {  
   private int [] array;  
   private int first;  
   private int last;  
   public SumTaskAsync(int[] array, int first, int last) {  
     this.array = array;  
     this.first = first;  
     this.last = last;  
   }  
   protected Integer compute() {  
     int sum = 0;  
     if (last - first < 10) {  
       sum = add();  
       System.out.println("Completed from "+first+", to: "+last);  
     } else {  
       int middle = (last + first) / 2;  
       System.out.println("Pending tasks: " + getQueuedTaskCount());  
       SumTask st1 = new SumTask(array, first, middle + 1);        
       SumTask st2 = new SumTask(array, middle + 1, last);  
       st1.fork();  
       st2.fork();//Continues with execution        
       sum += st1.join();//Waits for the result  
       sum += st2.join();  
     }  
     return sum;  
   }  
   private Integer add() {  
     int sum = 0;  
     for (int i = first; i < last; i++) {  
       sum += array[i];        
     }      
     return sum;  
   }  
 }  

In the example the SumTaskAsync executes its subtasks asynchronous using the fork() and join() methods.

Go to part 7