ArrayList

1. Automatic-resizable array and used in place of array
2. Once size is set can’t be modified
3. Implement List and allow null
4. Maintains Insertion order
5. Allows duplicates
6. ListIterator and Iterator both can be used. Prefer listiterator since it can traverse in both direction and modify the list as well
7. ArrayList is not synchronized so should not be shared between multiple threads.

a.       If multiple threads access concurrently, and one thread modifies the list it MUST be synchronized externally

b.      Else it should be wrapped using Collections.synchronizedList() method. Should be synchronized at the creation time to avoid any unsynchronized access

c.       Using CopyOnWriteArrayList which is creates a fresh copy of underlying array for all operations like add, remove etc,

8. Creating ArrayList

ArrayList<String> arrayList=new ArrayList<>();

ArrayList<String> arrayList1=new ArrayList<String>();

9. Adding Elements

arrayList.add(new Integer(1)); -- Compilation Error

arrayList.add("A");

arrayList.add("B");

arrayList.add("A");

Output: [A,B,A]

10. Size: size() Arraylist size could be different from the backing array size

11. indexOf(obj): returns the first index of object if found else -1. Internally uses .equals() method to find object so either implement hashcode() and .equals() method or Object class’s by default will be used.

12. boolean contains() : search an object in arraylist or we can use Collections.binarySearch().

13. isEmpty(): to check if it is empty

14. remove(): can remove by passing the object or index. Else through iterator also we can remove.

Iterator iterator=arrayList.iterator();

            while (iterator.hasNext()) {

                  String str=iterator.next().toString();

                  if(str.equals("B")){

                  arrayList.remove(1);-- ConcurrentModificationException

                        iterator.remove(); -- B will be removed

                  }

            }

15. boolean addAll(ArrayList): if we want to add copy of existing list or add a list to already existing

ArrayList<String> copyList1=new ArrayList<>();

         copyList1.addAll(arrayList); -- true

         System.out.println(copyList1); -- [arraylist…]

         ArrayList<String> addList1=new ArrayList<>();

         addList1.add("D");

         addList1.addAll(arrayList); -- true

         System.out.println(addList1);-- [D,arraylist …]

16. set(int Index, element): replace
17. clear() : remove all elements from arraylist. It can be used again.
18. Converting arraylist to array

a.       Array list can hold both primitives and objects while arrayList can hold only objects

b.      List<String> arrayList=Arrays.asList(String[])

c.       List<String> arrayList= new ArrayList();
String[] A={“A”,”B”};

Collections.addAll(arrayList, A);

19. mk

Array v/s ArrayList

1. ArrayList is a class and has methods. Array is an object so no methods we can get only length
2. 
   

Iterator || List Iterator

1. Iterator

a.       Belongs to collection framework

b.      Can traverse the collection and access data

c.       List and set provide iterator

d.      Map does not provide iterator but we can apply it on keyset or valueset

e.       boolean hasNext()

f.       object next(): before getting next value of collection check for hasnext()

g.      void remove()

h.      Enumerator does not have remove method

i.        Thread-safe as it does not allow any other thread to modify collection when same thread is iterating in collection. If this happens concurrentModificationException is thrown

j.         

2. ListIterator

a.       Used to traverse collection like Arraylist and hashSet in both direction using methods like previous() and next()

b.      Does not keep current index and its current position is determined by call to next() or previous() based on direction of traversing

c.       Has add() method which can add elements in collection while iterating over it.

Fail Fast

a.       Work on original collection

b.      Fail-fast iterators fail as soon as changes are made in the structure of collection(adding, removing or updating) when one thread is iterating over collection

c.       Modification count is maintained and if thread realizes it is changed and throws ConcurrentModificationException

d.      This is not guaranteed behavior since  it is done on best effort and does not involve synchronization

Fail-Safe

a.       Does not throw any exception when modification is done while one thread is iterating over it since they work on clone of iterator and not the original

Hash Map

1.     String HashMap: works on hashing algorithm

·         Allows null key and values

·         Not ordered collection and iterate over hashmap based on key but keys not guaranteed in order of insert

·         Not synchronized

·         Stores entries in multiple singly linked lists called buckets. Default number of bins is 16 and it is always power of 2

·         Uses inner class Node<K,V> for storing map entries. Map.entry is used which  means each bucket is a combination of key and value.

·         Uses hashcode() and equal() methods on keys for get() and put() operations.

·         Not thread-safe but can get thread-safe using Collections.synchronizedMap method at the cost of performace

·         How hashmap works? 

·         Hashmap load factor: used to figure out when hash map will be rehashed and bucket size increased. By default, load factor=.75 and bucket/capapcity=16. Threshold=load factor* capacity=12. When there are more than 12 mapping bucket size increases to the next power of 2 i.e. 32. If we want to save space, we can increase load factor to .8/.9 but get and set operation will take more time

2.     How HashMap works: Elements are stored in singly linked list called buckets.

a.       Put(K,V): when we put the element. Hashcode() of key is used to identify if already a key with same hashcode exists.

If it does (collision), equals() method is used on key to check if it is same. If equals() method return true then the value is overwritten else a new node(key+value) is added to the singly linked list.

If hashcode() for the key does not exist, then the value is inserted in hashmap.

It returns the previous value associated with that key and if no value associated then null.

System.out.println(hashMap.put("E", "Egg0")); -- null

hashMap.put("E", "Egg1");

System.out.println(hashMap.put("E", "Egg")); -- Egg1 System.out.println(hashMap.get("E")); -- Egg

b.      get(K): hashcode() is used to identify the bucket. If only 1 value exists it is returned. Else, it iterates over linked list of that bucket to check for equals()  method. If it finds something with equals() method as true it returns that value(from key value pair stored) else returns null

3.     Collision in hashmap: when 2 keys return same hashcode() i.e. same bucket location, this is termed as collision. It can be resolved by equals() method on key. Using final and immutable with proper equals() and hashcode() method implementation helps in better performance by reducing collision. Immutability also allows caching their hashcode of different keys which makes overall retrieval process very fast and suggest that String and various wrapper classes e.g. Integer very good keys in Java HashMap

4.     If size of threshold defined by load factor: load factor is by default .75 which means once 75% of buckets in hashmap are full, it is re-sized i.e. a new bucket array of twice the size is created and then starts putting the old elements in new bucket array. This is known as rehashing

5.     Race-condition: in multi-threaded environment, if 2 threads try to resize hash map at the same time. This can result in an infinite loop.

6.     Handling null: Hashmap allows both null key and value and key-value pair. Null keys are always mapped to index 0 and hashcode() and equals() method are not used in null keys case

7.     Popular methods:

 HashMap<String,String> hashMap= new HashMap<>();

hashMap.clear();

hashMap.put("A", "Apple");

hashMap.put("D", "Dog");

hashMap.put("C", "Cat");

hashMap.put("E", "Egg1");

hashMap.put("B","Boy");

System.out.println(hashMap.size()); -- 5

System.out.println(hashMap.remove("C")); --Cat *uses hash code of key*

System.out.println(hashMap.remove("F")); -- null

*remove(key,value)uses hash code of key and equals on key to compare value*

System.out.println(hashMap.remove("B", "Ball")); -- false

System.out.println(hashMap.remove("B", "Boy")); -- true

System.out.println(hashMap.replace("A", "An"));--Apple*uses hash code of key*

System.out.println(hashMap.replace("Z", "An")); -- null

*replace(key,oldvalue,newvalue)uses hash code of key and equals on key to compare oldvalue and if found then put new value*

System.out.println(hashMap.replace("A", "An","AS")); -- true

System.out.println(hashMap.replace("A", "An","AS")); -- false

System.out.println(hashMap.containsKey("A")); -- true

System.out.println(hashMap.containsValue("A")); -- false

System.out.println(hashMap); -- {A=AS, D=Dog, E=Egg1}

System.out.println(hashMap.size()); -- 3

8.     Do not have iterator by default. Iterated using keySet or EntrySet

         Set entrySet1=hashMap.entrySet();

         Iterator iterator1=entrySet1.iterator();

         while(iterator1.hasNext()){

            System.out.println(iterator1.next());

            }

          Iterator iterator2=hashMap.keySet().iterator();

         while(iterator2.hasNext()){

            System.out.println(iterator2.next()); -- first key

            String key=iterator2.next().toString();- 2nd key

            System.out.println("Key: "+key+" Value: "+ hashMap.get(key));

            }

            A=AS

D=Dog

E=Egg1

A    

Key: D Value: Dog

E

Exception in thread "main"

3.     Remove method of iterator v/s remove of collection: While iterating over collection, if we use remove() of collection error will be thrown. For such scenarios remove() of iterator should be used.

       Set entrySet1=hashMap.entrySet();

       Iterator iterator1=entrySet1.iterator();

       while(iterator1.hasNext()){

            hashMap.remove("A"); 

            }

       

       Exception in thread "main" java.util.ConcurrentModificationException

.

Hash Map

1.     String HashMap: works on hashing algorithm

·         Allows null key and values

·         Not ordered collection and iterate over hashmap based on key but keys not guaranteed in order of insert

·         Not synchronized

·         Stores entries in multiple singly linked lists called buckets. Default number of bins is 16 and it is always power of 2

·         Uses inner class Node<K,V> for storing map entries. Map.entry is used which  means each bucket is a combination of key and value.

·         Uses hashcode() and equal() methods on keys for get() and put() operations.

·         Not thread-safe but can get thread-safe using Collections.synchronizedMap method at the cost of performace

·         How hashmap works? 

·         Hashmap load factor: used to figure out when hash map will be rehashed and bucket size increased. By default, load factor=.75 and bucket/capapcity=16. Threshold=load factor* capacity=12. When there are more than 12 mapping bucket size increases to the next power of 2 i.e. 32. If we want to save space, we can increase load factor to .8/.9 but get and set operation will take more time

2.     How HashMap works: Elements are stored in singly linked list called buckets.

a.       Put(K,V): when we put the element. Hashcode() of key is used to identify if already a key with same hashcode exists.

If it does (collision), equals() method is used on key to check if it is same. If equals() method return true then the value is overwritten else a new node(key+value) is added to the singly linked list.

If hashcode() for the key does not exist, then the value is inserted in hashmap.

It returns the previous value associated with that key and if no value associated then null.

System.out.println(hashMap.put("E", "Egg0")); -- null

hashMap.put("E", "Egg1");

System.out.println(hashMap.put("E", "Egg")); -- Egg1 System.out.println(hashMap.get("E")); -- Egg

b.      get(K): hashcode() is used to identify the bucket. If only 1 value exists it is returned. Else, it iterates over linked list of that bucket to check for equals()  method. If it finds something with equals() method as true it returns that value(from key value pair stored) else returns null

3.     Collision in hashmap: when 2 keys return same hashcode() i.e. same bucket location, this is termed as collision. It can be resolved by equals() method on key. Using final and immutable with proper equals() and hashcode() method implementation helps in better performance by reducing collision. Immutability also allows caching their hashcode of different keys which makes overall retrieval process very fast and suggest that String and various wrapper classes e.g. Integer very good keys in Java HashMap

4.     If size of threshold defined by load factor: load factor is by default .75 which means once 75% of buckets in hashmap are full, it is re-sized i.e. a new bucket array of twice the size is created and then starts putting the old elements in new bucket array. This is known as rehashing

5.     Race-condition: in multi-threaded environment, if 2 threads try to resize hash map at the same time. This can result in an infinite loop.

6.     Handling null: Hashmap allows both null key and value and key-value pair. Null keys are always mapped to index 0 and hashcode() and equals() method are not used in null keys case

7.     Popular methods:

 HashMap<String,String> hashMap= new HashMap<>();

hashMap.clear();

hashMap.put("A", "Apple");

hashMap.put("D", "Dog");

hashMap.put("C", "Cat");

hashMap.put("E", "Egg1");

hashMap.put("B","Boy");

System.out.println(hashMap.size()); -- 5

System.out.println(hashMap.remove("C")); --Cat *uses hash code of key*

System.out.println(hashMap.remove("F")); -- null

*remove(key,value)uses hash code of key and equals on key to compare value*

System.out.println(hashMap.remove("B", "Ball")); -- false

System.out.println(hashMap.remove("B", "Boy")); -- true

System.out.println(hashMap.replace("A", "An"));--Apple*uses hash code of key*

System.out.println(hashMap.replace("Z", "An")); -- null

*replace(key,oldvalue,newvalue)uses hash code of key and equals on key to compare oldvalue and if found then put new value*

System.out.println(hashMap.replace("A", "An","AS")); -- true

System.out.println(hashMap.replace("A", "An","AS")); -- false

System.out.println(hashMap.containsKey("A")); -- true

System.out.println(hashMap.containsValue("A")); -- false

System.out.println(hashMap); -- {A=AS, D=Dog, E=Egg1}

System.out.println(hashMap.size()); -- 3

8.     Do not have iterator by default. Iterated using keySet or EntrySet

         Set entrySet1=hashMap.entrySet();

         Iterator iterator1=entrySet1.iterator();

         while(iterator1.hasNext()){

            System.out.println(iterator1.next());

            }

          Iterator iterator2=hashMap.keySet().iterator();

         while(iterator2.hasNext()){

            System.out.println(iterator2.next()); -- first key

            String key=iterator2.next().toString();- 2nd key

            System.out.println("Key: "+key+" Value: "+ hashMap.get(key));

            }

            A=AS

D=Dog

E=Egg1

A    

Key: D Value: Dog

E

Exception in thread "main"

3.     Remove method of iterator v/s remove of collection: While iterating over collection, if we use remove() of collection error will be thrown. For such scenarios remove() of iterator should be used.

       Set entrySet1=hashMap.entrySet();

       Iterator iterator1=entrySet1.iterator();

       while(iterator1.hasNext()){

            hashMap.remove("A"); 

            }

       

       Exception in thread "main" java.util.ConcurrentModificationException

.