Saturday, 7 September 2019

Collections in java

Collection:

Data Structures Are Diverse:

  1. Ordering 
  2. Uniqueness
  3. Pairs





size() Get the number of elements in the Collection 

 isEmpty() True if size() == 0, false otherwise 
add(element) Add the element at the beginning of this collection 

 addAll(collection) Add all the elements of the argument collection to this collection 

 remove(element) Remove the element from this collection 

 removeAll(collection) Remove all the elements of the argument collection to this collection 

 retainAll(collection) Remove all the elements of this collection not in the argument collection 

 contains(element) True if the element is in this collection, false otherwise 

 containsAll(collection) True if all the elements of the argument collection are in this collection 

 clear() Remove all elements from this collection

 List:: 
Lists are collections with iteration order
Each element has an index-

 An index is an int representing its position in the List. We can modify Lists using indices E

 int indexOf(Object o); 
Int lastIndexOf(Object o);

 You can also lookup values by index
List subList(int fromIndex, int toIndex);

 Sublists are views over ranges of lists.

methods::

 void add(int index, E e); 
E get(int index); 
E remove(int index); 
E set(int index, E element); 
boolean addAll(int index, Collection c);

 ArrayList::

  • Java ArrayList class uses a dynamic array for storing the elements.It extends AbstractList class and implements List interface.
  • Java ArrayList class can contain duplicate elements.
  • Java ArrayList class maintains insertion order.
  • Java ArrayList class is non synchronized.
  • Java ArrayList allows random access because array works at the index basis.
  • In Java ArrayList class, manipulation is slow because a lot of shifting needs to be occurred if any element is removed from the array list.
method
   addAll(Collection c)
   


Product.java

package collections;
import java.util.Comparator;
import java.util.Objects;
import static java.util.Comparator.comparing;
public class Product {     
                public static final Comparator<Product>BY_WEIGHT=comparing(Product::getWeight); 
                public static final Comparator<Product>BY_NAME=comparing(Product::getName);       
                /*public static final Comparator<Product> myComparatorForWeight=new Comparator<>() {
                                                public int compare(final  Product p1, final  Product p2) {
                                                                return Integer.compare(p1.getWeight(), p2.getWeight());
                                                }*/         
                private final String name;
                private final int weight;

                public Product(String name, int weight) {
                                this.name = name;
                                this.weight = weight;
                }
                public String getName() {
                                return name;
                }
                public int getWeight() {
                                return weight;
                }
                @Override
                public String toString() {
                                return "Product {" + "name='" + name + '\'' + ",weight='" + weight + '\'' + '}';
                }
                public int hashCode() {
                                return Objects.hash(name, weight);
                }
                public boolean equals(final Object o) {
                                if(!(o instanceof Product))
                                                                return false;
                                Product p =(Product)o;
                               
                                return Objects.equals(name, p.name)
                                                                && Objects.equals(weight,p.weight);
                               
                }
}

public class Shipment implements Iterable<Product>{
               
                private static final int LIGHT_VAN_MAX_WEIGHT = 20;
                public static final int PRODUCT_NOT_PRESENT = -1;      
                private final List<Product> products= new ArrayList<>();             
                private List<Product> lightVanProducts;
                private List<Product> heavyVanProducts;
               
                public void add(Product product) {
                                products.add(product);
                }             
                public void replace(Product odlProduct,Product newProduct) {
                                final int index=products.indexOf(odlProduct);
                                if(index!=PRODUCT_NOT_PRESENT)
                                                products.set(index, newProduct);
                }
                public void prepare() {
                                 // sort our list of products by weight
                                products.sort(Product.BY_WEIGHT);
                                 // find the product index that needs the heavy van
                                 int splitPoint = findSplitPoint();
                                 // assign views of the product list for heavy and light vans
                        lightVanProducts = products.subList(0, splitPoint);
                        heavyVanProducts = products.subList(splitPoint, products.size());
                }
               
                private int findSplitPoint()
    {
        for (int i = 0; i < products.size(); i++)
        {
            final Product product = products.get(i);
            if (product.getWeight() > LIGHT_VAN_MAX_WEIGHT)
            {
                return i;
            }
        }

        return 0;
    }
               
                @Override
                public Iterator<Product> iterator() {
                                return products.iterator();
                }
               
}

Junit
Create testcase-

public class ProductFixtures {
      public static Product door = new Product("Wooden Door", 35);
    public static Product floorPanel = new Product("Floor Panel", 25);
    public static Product window = new Product("Glass Window", 10);
}


public class ShipmentTest {

                private Shipment shipment = new Shipment();
               
                @Test
                public void shouldAddItems() throws Exception{
                                shipment.add(door);
                                shipment.add(window);
                                shipment.add(floorPanel);
                                assertThat(shipment,hasItems(new Product("Wooden Door", 35),new Product("Floor Panel", 25)));
                                //assertThat(shipment, contains(door, window));
                }
               
                @Test
                public void shouldReplaceItems() throws Exception{
                                shipment.add(door);
        shipment.add(window);
       
        System.out.println("shipment is==>"+shipment);
        shipment.replace(door, floorPanel);
        System.out.println("after replacement shipment is==>"+shipment);
        assertThat(shipment, hasItem(floorPanel));
                }
               
                @Test
                public void shouldNotReplaceMissingItems() throws Exception
                {
                                shipment.add(window);
                                shipment.replace(door, floorPanel);
                                assertThat(shipment, hasItem(window));
                }
                @Test
    public void shouldIdentifyVanRequirements() throws Exception
    {
                                shipment.add(door);
        shipment.add(window);
        shipment.add(floorPanel);

        shipment.prepare();
        assertThat(shipment.getLightVanProducts(), contains(window));
    }
}



import org.junit.Test;

import java.util.Arrays;
import java.util.List;
import java.util.Objects;

import static org.hamcrest.CoreMatchers.*;
import static org.hamcrest.Matchers.hasProperty;
import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;
import static org.junit.Assert.assertThat;

public class ListTest {

    @Test
    public void testAssertList() {

        List<Fruit> list = Arrays.asList(
                new Fruit("Banana", 99),
                new Fruit("Apple", 20)
        );

        //Test equals
        assertThat(list, hasItems(
                new Fruit("Banana", 99),
                new Fruit("Apple", 20)
        ));

        assertThat(list, containsInAnyOrder(
                new Fruit("Apple", 20),
                new Fruit("Banana", 99)
        ));

        //Test class property, and its value
        assertThat(list, containsInAnyOrder(
                hasProperty("name", is("Apple")),
                hasProperty("name", is("Banana"))
        ));

    }

    public class Fruit {

        public Fruit(String name, int qty) {
            this.name = name;
            this.qty = qty;
        }

        private String name;
        private int qty;

        public int getQty() {
            return qty;
        }

        public void setQty(int qty) {
            this.qty = qty;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        //Test equal, override equals() and hashCode()
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Fruit fruit = (Fruit) o;
            return qty == fruit.qty &&
                    Objects.equals(name, fruit.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name, qty);
        }
    }


}

Java LinkedList class


  • Java LinkedList class uses doubly linked list to store the elements. It extends the AbstractList class and implements List and Deque interfaces.
  • Java LinkedList class can contain duplicate elements.
  • Java LinkedList class maintains insertion order.
  • Java LinkedList class is non synchronized.
  • In Java LinkedList class, manipulation is fast because no shifting needs to be occurred.
  • Java LinkedList class can be used as list, stack or queue.
ArrayList
LinkedList
1) ArrayList internally uses dynamic array to store the elements.
LinkedList internally uses doubly linked list to store the elements.
2) Manipulation with ArrayList is slow because it internally uses array. If any element is removed from the array, all the bits are shifted in memory.
Manipulation with LinkedList is faster than ArrayList because it uses doubly linked list so no bit shifting is required in memory.
3) ArrayList class can act as a list only because it implements List only.
LinkedList class can act as a list and queue both because it implements List and Deque interfaces.
4) ArrayList is better for storing and accessing data.
LinkedList is better for manipulating data.

Java HashSet class


  • uses hashtable to store the elements.It extends AbstractSet class and implements Set interface.

Java LinkedHashSet class:

  • contains unique elements only like HashSet. It extends HashSet class and implements Set interface.
  • maintains insertion order.

Java TreeSet class

  • contains unique elements only like HashSet. The TreeSet class implements NavigableSet interface that extends the SortedSet interface.
  • maintains ascending order.

Java Queue Interface


It is an ordered list of objects with its use limited to insert elements at the end of the list and deleting elements from the start of list i.e. it follows the FIFO or the First-In-First-Out principle.
most common classes are the PriorityQueue and LinkedList in Java.
both the implementations are not thread safe. 

PriorityBlockingQueue is one alternative implementation if thread safe implementation is needed.

Few important characteristics of Queue are:
·         The Queue is used to insert elements at the end of the queue and removes from the beginning of the queue. It follows FIFO concept.
·         The Java Queue supports all methods of Collection interface including insertion, deletion etc.
·         LinkedList, ArrayBlockingQueue and PriorityQueue are the most frequently used implementations.
·         If any null operation is performed on BlockingQueues, NullPointerException is thrown.

·         BlockingQueues have thread-safe implementations.
·         The Queues which are available in java.util package are Unbounded Queues
·         The Queues which are available in java.util.concurrent package are the Bounded Queues.
·         All Queues except the Deques supports insertion and removal at the tail and head of the queue respectively. The Deques support element insertion and removal at both ends.

Methods in Queue:
1.    add()- This method is used to add elements at the tail of queue. More specifically, at the last of linkedlist if it is used, or according to the priority in case of priority queue implementation.
2.    peek()- This method is used to view the head of queue without removing it. It returns Null if the queue is empty.
3.    element()- This method is similar to peek(). It throws NoSuchElementException when the queue is empty.
4.    remove()- This method removes and returns the head of the queue. It throws NoSuchElementException when the queue is impty.
5.    poll()- This method removes and returns the head of the queue. It returns null if the queue is empty.
6.    size()- This method return the no. of elements in the queue.

The Queue interface basically orders the element in FIFO(First In First Out)manner.
Methods of Queue Interface :
  1. public boolean add(object);
  2. public boolean offer(object);
  3. public remove();
  4. public poll();
  5. public element();
  6. public peek();

PriorityQueue class:
The PriorityQueue class provides the facility of using queue. But it does not orders the elements in FIFO manner.


 HashSet & Sorted Set

public class Product
{

    public static final Comparator<Product> BY_NAME = comparing(Product::getName);

    public static final Comparator<Product> BY_WEIGHT = comparing(Product::getWeight);

    private final String name;
    private final int weight;

    public Product(String name, int weight)
    {
        this.name = name;
        this.weight = weight;
    }

    public String getName()
    {
        return name;
    }

    public int getWeight()
    {
        return weight;
    }

    @Override
    public String toString()
    {
        return "Product{" +
            "name='" + name + '\'' +
            ", weight=" + weight +
            '}';
    }

    public boolean equals(final Object o)
    {
        if (!(o instanceof Product)) return false;

        final Product product = (Product) o;

        return Objects.equals(weight, product.weight)
            && Objects.equals(name, product.name);
    }

    public int hashCode()
    {
        return Objects.hash(name, weight);
    }
}






Supplier.java

package com.monotonic.collections;

import java.util.ArrayList;
import java.util.List;

public class Supplier
{
    private final String name;
    private final List<Product> products = new ArrayList<>();

    public Supplier(String name)
    {
        this.name = name;
    }

    public String getName()
    {
        return name;
    }

    public List<Product> products()
    {
        return products;
    }

    @Override
    public String toString()
    {
        return "Supplier{" +
            "name='" + name + '\'' +
            ", products=" + products +
            '}';
    }
}



How to synchronize arraylist in java to make it completely thread safe with examples and programs in java.
Remove duplicate elements in arraylist using LinkedHashSet
The LinkedHashSet is the best approach for removing duplicate elements in an arraylist. LinkedHashSet does two things internally :
Remove duplicate elements
Maintain the order of elements added to it

public class RemoveDuplicate {

    public static void main(String args[]) {
          
         Integer[] x = new Integer[] {1, 1, 2, 3, 3, 3, 4, 5, 6, 6, 6, 7, 8};
   // ArrayList with duplicate elements
    ArrayList<Integer> numbersList =
          new ArrayList<>(Arrays.asList(x));
    
    System.out.println(numbersList);
    
    LinkedHashSet<Integer> hasset = new LinkedHashSet<>(numbersList);
    ArrayList<Integer> listWithoudDuplicate= new ArrayList<>(hasset);
    System.out.println(hasset);
    System.out.println(listWithoudDuplicate);
    //using java8 stream api
    List<Integer> listWithoutDupl=numbersList.stream().distinct().collect(Collectors.toList());
    System.out.println(listWithoutDupl);
    }

}



Is synchronizing ArrayList using Collections.synchronizedList is completely thread-safe in java?
Answer is No.


How to synchronize arraylist in java to make it completely thread safe in java
Solution 1 = iterator returned by synchronizedArrayList won't be synchronized, so during iteration we must keep synchronizedArrayList in synchronization block to avoid ConcurrentModificationException in java.

Solution 2 = Use CopyOnWriteArrayList, it is completely thread-safe, also Iterator & listIterator returned by CopyOnWriteArrayList are completely thread-safe in java.

public class ArrayListSynchronizationFailsExample {
   public static void main(String[] args) {
          final List<Integer> arrayList = new ArrayList<Integer>();
          final List<Integer> synchronizedArrayList;
          // Let's make arrayList synchronized
          synchronizedArrayList = Collections.synchronizedList(arrayList);
         
          //Thread 1 will add elements in synchronizedArrayList
          Thread t1 = new Thread(new Runnable() {
                 public void run() {
                       for (int i = 0; i <= 3; i++) {
                              synchronizedArrayList.add(i);
                              try {
                                     Thread.sleep(100);
                              } catch (InterruptedException e) {
                                     e.printStackTrace();
                              }
                       }
                 }
          }, "thread-1");
         
          t1.start();
          //Thread 2 will iterate on synchronizedArrayList
          Thread t2 = new Thread(new Runnable() {
                 public void run() {
                       Iterator<Integer> it = synchronizedArrayList.iterator();
                       while (it.hasNext()) {
                              try {
                                     Thread.sleep(100);
                              } catch (InterruptedException e) {
                                     e.printStackTrace();
                              }
                              System.out.println(it.next());//throws ConcurrentModificationException
                       }
                 }
          }, "thread-2");
          t2.start();
   }
}
/*OUTPUT
Exception in thread "thread-2" java.util.ConcurrentModificationException
   at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
   at java.util.ArrayList$Itr.next(Unknown Source)
   at ArrayListSynchronizationFails$2.run(ArrayListSynchronizationFails.java:43)
   at java.lang.Thread.run(Unknown Source)
*/

main thread started thread-1, thread-1 added 0 (i.e. i=0) in synchronizedArrayList, then thread-1 went for sleep(100), meanwhile


main thread started thread-2, thread-2 obtained iterator on
synchronizedArrayList, then thread-2 entered while loop, then thread-2 went for sleep(100),


sleep time was up and thread-1 again entered running state and added 1 (i.e. i=1) in synchronizedArrayList, then thread-1 went for sleep(100),


sleep time was up and thread-2 again entered running state and it.next() throws ConcurrentModificationException , because arraylist was modified by thread-1 after obtaining iterator on synchronizedArrayList.

Example/ Program 2  (elaborate Solution 1) to show that iterator returned by synchronizedArrayList won't be synchronized, so during iteration we must keep synchronizedArrayList in synchronization block to avoid ConcurrentModificationException in java >

public static void main(String[] args) {
          final List<Integer> arrayList = new ArrayList<Integer>();
          final List<Integer> synchronizedArrayList;
          // Let's make arrayList synchronized
          synchronizedArrayList = Collections.synchronizedList(arrayList);
          //Thread 1 will add elements in synchronizedArrayList
          Thread t1 = new Thread(new Runnable() {
                 public void run() {
                       for (int i = 0; i <= 3; i++) {
                              synchronizedArrayList.add(i);
                              try {
                                     Thread.sleep(100);
                              } catch (InterruptedException e) {
                                     e.printStackTrace();
                              }
                       }
                 }
          }, "thread-1");
          t1.start();
          //Thread 2 will iterate on synchronizedArrayList
          Thread t2 = new Thread(new Runnable() {
                 public void run() {
                       Iterator<Integer> it = synchronizedArrayList.iterator();
                       synchronized (synchronizedArrayList) { //synchronization block
                              while (it.hasNext()) {
                                     try {
                                            Thread.sleep(100);
                                     } catch (InterruptedException e) {
                                            e.printStackTrace();
                                     }
                                     System.out.println(it.next());
                              }
                       }
                      
                 }
          }, "thread-2");
          t2.start();
   }
}
/*output
0
*/

Let’s discuss what happened in above program >
main thread started thread-1, thread-1 added 0 (i.e. i=0) in synchronizedArrayList, then thread-1 went for sleep(100), meanwhile

 main thread started thread-2, it obtained lock on synchronizedArrayList object, then thread-2 obtained iterator on synchronizedArrayList, then thread-2 entered while loop, then thread-2 went for sleep(100),

 sleep time was up and thread-1 entered running state but add(i) method on synchronizedArrayList was synchronized(you must know that only iterator returned on synchronizedArrayList is not thread safe, rest of the methods are completely thread-safe), so thread-1 waited for thread-2 to release lock on synchronizedArrayList object,

 as soon as thread-2 released lock on synchronizedArrayList object thread-1 added 1 (i.e. i=1) in synchronizedArrayList, it further completed for loop and we didn’t encountered  ConcurrentModificationException.


Example/ Program 3  (elaborate Solution 2) to show that iterator returned by CopyOnWriteArrayList will be thread-safe, so during iteration we don’t need any synchronization block and  ConcurrentModificationException will not be thrown in java >
CopyOnWriteArrayList is completely thread-safe in java. We does not need to synchronize it explicitly.
Iterator & listIterator returned by CopyOnWriteArrayList are also completely thread-safe in java.
package Collection.synchornize.problem;

import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteArrayListSynchronizationSucceedsExample {
      public static void main(String[] args) {
            final List<Integer> copyOnWriteArrayList = new CopyOnWriteArrayList<Integer>();
            //Thread 1 will add elements in CopyOnWriteArrayList
        Thread t1 = new Thread(new Runnable() {

               public void run() {
                     for (int i = 0; i <= 3; i++) {
                            copyOnWriteArrayList.add(i);
                            try {
                                   Thread.sleep(100);
                            } catch (InterruptedException e) {
                                   e.printStackTrace();
                            }
                     }
               }
        }, "thread-1");
       
        t1.start();
      //Thread 2 will iterate on CopyOnWriteArrayList
        Thread t2 = new Thread(new Runnable() {
               public void run() {
                     Iterator<Integer> it = copyOnWriteArrayList.iterator();
                     while (it.hasNext()) {
                            try {
                                   Thread.sleep(100);
                            } catch (InterruptedException e) {
                                   e.printStackTrace();
                            }
                            System.out.println(it.next());
                     }

               }
        }, "thread-2");
        t2.start();


      }
}


Note : output of all above mentioned programs may vary on different machines, because of unpredictable behaviour of thread scheduler.
FAIL-FAST
Iterator returned by ArrayList are fail-fast, means any structural modification made to ArrayList during iteration will throw ConcurrentModificationException in java.
·                     Some important classes whose returned iterator is fail-fast, means any structural modification made to these classes during iteration will throw ConcurrentModificationException >

·         Iterator returned by ArrayList are fail-fast, means any structural modification made to ArrayList during iteration will throw ConcurrentModificationException in java.public class ConcurrentModificationArrayListExample {
   public static void main(String[] args) {
      List<String> list = new ArrayList<String>();
      list.add("a");
       list.add("b");
       list.add("c");
      
       Iterator<String> iterator = list.iterator();
      
       while(iterator.hasNext()){
       
        String str = iterator.next();
        System.out.print(str+" ");
       
        if(str.equals("b"))
          list.add("b2");   //will throw ConcurrentModificationException
       
       }
      
       System.out.println("\nAfter iteration list is : "+list);
      
   }
}
/*OUTPUT
a b Exception in thread "main" java.util.ConcurrentModificationException
   at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
   at java.util.ArrayList$Itr.next(Unknown Source)
   at com.javaMadeSoEasy.ConcurrentModificationArrayListExample.main(ConcurrentModificationArrayListExample.java:20)
*/



Iterator returned by CopyOnWriteArrayList are fail-safe, means any structural modification made to CopyOnWriteArrayList during iteration won’t throw any Exception in java.

public class ConcurrentModificationCopyOnWriteArrayListExample {
   public static void main(String[] args) {
      List<String> list = new CopyOnWriteArrayList<String>();
      list.add("a");
       list.add("b");
       list.add("c");
      
       Iterator<String> iterator = list.iterator();
      
       while(iterator.hasNext()){

        String str = iterator.next();
        System.out.print(str+" ");
       
        if(str.equals("b"))
          list.add("b2");   //No ConcurrentModificationException
       
       }
      
       System.out.println("\nAfter iteration list is : "+list);
      
   }
}
/*OUTPUT
a b c
After iteration list is : [a, b, c, b2]
*/

What is modCount? What is structural modifications in java?
The number of times this list has been structurally modified. Any changes to size of list are called structural modifications in java.
Which method cause structural modifications in java?
add() and remove() method changes size of list. Hence, cause structural modifications.
Every time any of these methods is called modCount is incremented by 1.

Additionally, you may also be interested in knowing what will happen if add() and remove() methods are called subsequently in java?

Posted by at
Labels:

No comments:

Post a Comment

Note: only a member of this blog may post a comment.

Subscribe to: Post Comments (Atom)