Collections

From Rasim SEN - Knowledge Base/Java/Springframework/Microservices/Cloud-AWS/AI
Jump to: navigation, search

Collections in java is a framework that provides an architecture to store and manipulate the group of objects.

All the operations that you perform on a data such as searching, sorting, insertion, manipulation, deletion etc. can be performed by Java Collections.

Java Collection simply means a single unit of objects. Java Collection framework provides many interfaces (Set, List, Queue, Deque etc.) and classes (ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, TreeSet etc).


collection-hierarchy.png

Methods of Collection interface

There are many methods declared in the Collection interface. They are as follows:


No.MethodDescription
1public boolean add(Object element) is used to insert an element in this collection.
2public boolean addAll(Collection c)is used to insert the specified collection elements in the invoking collection.
3public boolean remove(Object element)is used to delete an element from this collection.
4public boolean removeAll(Collection c)is used to delete all the elements of specified collection from the invoking collection.
5public boolean retainAll(Collection c)is used to delete all the elements of invoking collection except the specified collection.
6public int size()return the total number of elements in the collection.
7public void clear()removes the total no of element from the collection.
8public boolean contains(Object element)is used to search an element.
9public boolean containsAll(Collection c)is used to search the specified collection in this collection.
10public Iterator iterator()returns an iterator.
11public Object[] toArray()converts collection into array.
12public boolean isEmpty()checks if collection is empty.
13public boolean equals(Object element)matches two collection.
14public int hashCode()returns the hashcode number for collection.

Iterator interface

Iterator interface provides the facility of iterating the elements in forward direction only.

Methods of Iterator interface

There are only three methods in the Iterator interface. They are:

No.MethodDescription
1public boolean hasNext()It returns true if iterator has more elements.
2public Object next()It returns the element and moves the cursor pointer to the next element.
3public void remove()It removes the last elements returned by the iterator. It is rarely used.

Set

EnumSet

HashSet

LinkedHashSet

TreeSet

SortedSet

List

ArrayList

LinkedList

Vector

Stack

Queue

PriorityQueue

Deque

ArrayDeque

Map

HashMap

LinkedHashMap

IdentityHashMap

WeakHashMap

SortedMap

TreeMap

Generics

Big O Notation

Big O is the way of measuring the efficiency of an algorithm and how well it scales based on the size of the dataset. Imagine you have a list of 10 objects, and you want to sort them in order. There’s a whole bunch of algorithms you can use to make that happen, but not all algorithms are built equal. Some are quicker than others but more importantly the speed of an algorithm can vary depending on how many items it’s dealing with. Big O is a way of measuring how an algorithm scales. Big O references how complex an algorithm is.


Collection Interview Questions and Answers

How HashMap works internally ?

HashMap works on the principle of Hashing. To understand Hashing , we should understand the three terms first

  • Hash Function
  • Hash Value
  • Bucket

What is Hash function?

hashCode() method which returns an integer value is the Hash function. The important point to note that, this method is present in Object class.

This is the code for the hash function(also known as hashCode method) in Object Class :

public native int hashCode();

What is Hash value?

HashCode method return an int value.So the Hash value is just that int value returned by the hash function.

What is bucket?

A bucket is used to store key value pairs. A bucket can have multiple key-value pairs. In hash map, bucket used is simply a linked list to store objects.

So how does hashMap works internally?

We know that Hash map works on the principle of hashing which means

HashMap get(Key k) method calls hashCode method on the key object and applies returned hashValue to its own static hash function to find a bucket location(backing array)

What if when two keys are same and have the same HashCode?

If key needs to be inserted and already inserted hashkey’s hashcodes are same, and keys are also same(via reference or using equals() method) then override the previous key value pair with the current key value pair. The other important point to note is that in Map ,Any class(String etc.) can serve as a key if and only if it overrides the equals() and hashCode() method.

What is collision in HashMap?

Collisions happen when 2 distinct keys generate the same hashCode() value. Multiple collisions are the result of bad hashCode() algorithm.

The more the collisions the worse the performance of the hashMap.

There are many collision-resolution strategies – chaining, double-hashing, clustering.

However, java has chosen chaining strategy for hashMap, so in case of collisions, items are chained together just like in a linkedList.