Unit 4

Collection Framework
Purpose: To represent many values by using single object.
Problem: To represent 10k values we declare 10k variables. By doing this the
readability of the program is going to be down and this is worst kind of
programming. To overcome this, we can go for arrays and collections.
Arrays: Student[] s = new Student[10000]; We can represent huge no of
homogeneous type of elements by using single object(variable) with arrays.
Collection Framework: Collection framework defines several interfaces and
classes which can be used to represent a group of individual objects as a single
entity (i.e. collection).
Collection(I): Collection is a group of individual objects as a single entity.
Collection is an interface which is used to represent a group of individual
objects as a single entity.
Collections(C): Collections is a utility class presents in java.util package to
define several utility methods like sorting, searching etc. in collection objects.
Ex: To sort an ArrayList Collections.sort(al); al -> ArrayList Object
Arrays vs Collections:

Arrays Collections
1. Array are fixed in size. 1. Collections are growable in nature.
2. W.r.t memory arrays are not 2. W.r.t memory collections are recommended.
recommended.
3. W.r.t performance arrays are 3. W.r.t performance collections are not
recommended. recommended.
4. Arrays can hold only homogeneous 4. Collections can hold both homogeneous and
elements. heterogeneous elements.
5. Arrays are not implemented based 5. Every collection class is implemented based
on any DS. So, readymade method on some standard DS. So, readymade method
support is not available. support is available.
6. Arrays can hold primitive types and 6. Collections can hold only reference
reference types(objects). types(objects).
7. There are no predefined classes in 7. There are so many predefined classes are
Java API which represents arrays. available in Java API (java.util package) which
represents collections.
 8. We can’t use the cursors to process 8. We can use cursors to process the collection
the array elements. elements.

9 Key Interfaces of Collection Framework:

List (1.2v): List is the child interface of Collection interface. If we want to

represent a group of individual objects as single entity where duplicates are
allowed and insertion order must be preserved, then we go for List.
ArrayList
ArrayList is a resizable array implementation provided by the Java Collections
Framework. It is part of the java.util package and offers dynamic array
capabilities that allow for more flexible and efficient manipulation of data
compared to traditional arrays. Here are some key features and characteristics
of ArrayLists
Properties:
• The underlying DS is resizable array or growable array.
• Duplicates are allowed and Insertion order is preserved.
 • Heterogeneous elements are allowed and null insertion is possible.
• ArrayList is the best choice if our frequent operation is retrieval
operation because ArrayList implements RandomAccess interface and
ArrayList is the worst choice if our frequent operation is insertion or
deletion in the middle because several shift operations will take huge
amount of time.
ArrayList al = new ArrayList();
Creates an empty ArrayList with default initial capacity 10. Once ArrayList
reaches its maximum capacity then a new ArrayList will be created.
ArrayList al = new ArrayList(int initial_capacity);
Creates an empty ArrayList with specified initial capacity.
ArrayList al = new ArrayList(Collection c);
Creates an equivalent ArrayList for the given Collection
Example
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Arraylisttest {
public static void main(String[] args) {
List<String> list =new ArrayList<String>();
list.add("abc");
list.add("xyz");
list.add("mno");
list.add("pqr");
list.add("uvw");
System.out.println(list);
Collections.sort(list);
System.out.println("--------------------list after sorting-----------");
 System.out.println(list); } }
Output:
[abc, xyz, mno, pqr, uvw]
----------list after sorting-------------
[abc, mno, pqr, uvw, xyz]

Note: Usually we can use collections to hold and transfer Objects from one
place to another place, to provide support for this requirement every collection
already implements Serializable and Cloneable Interfaces.
Serializable and Cloneable are marker interfaces in Java. A marker interface is
an interface with no methods or constants inside it. It's used to signal to the
JVM or other tools that the classes implementing these interfaces have certain
properties or should be treated in a specific way.
The Serializable interface is used to enable serialization, which is the process of
converting an object into a byte stream for storage, transmission, or later
reconstruction.
The Cloneable interface is used to indicate that a class allows for cloning, which
is the process of creating a copy of an object.
RandomAccess: RandomAcess interface presents in java.util package and it
doesn’t contain any methods, so it is a marker interface, where required ability
will be provided by JVM automatically.
LinkedList: LinkedList is implemented as a doubly-linked list, where each node
contains a reference to both the previous and next node in the sequence. This
allows for efficient insertions and deletions at both ends and in the middle of
the list.
Properties:
• The underlying DS is Doubly LinkedList.
• Duplicates are allowed and Insertion order is preserved.
• Heterogeneous elements are allowed and null insertion is possible.
• If our frequent operation is insertion or deletion in the middle, then
LinkedList is the best choice. Because the internal structure of the
 LinkedList. LinkedList is the worst choice if our frequent operation is
retrieval operation.
• LinkedList implements Serializable and Clonable interfaces but not
RandomAccess interface.
Usually we can use LinkedList to implement stacks and queues to provide
support for this requirement LinkedList class defines following specific
methods.
addFirst(), addLast(), getFirst(), getLast(), removeFirst(), removeLast().
LinkedList ll = new LinkedList();
LinkedList l = new LinkedList(Collection c);
Example
public class TestLinkedList {
public static void main(String[] args) {
LinkedList ll = new LinkedList();
ll.add("java");
ll.add(30);
ll.add(null);
ll.add("java");
System.out.println(ll);
ll.set(0, "python");
System.out.println(ll);
ll.removeLast();
ll.addFirst("c++");
System.out.println(ll);
}}
Output
[java, 30, null, java]
[python, 30, null, java]
[c++, python, 30, null]
Vector: Vector is a part of the Java Collection Framework and is included in the
java.util package. It is an implementation of the List interface, providing a
dynamic array that can grow as needed.
Properties:
• The underlying DS is resizable array or growable array.
• Duplicates are allowed and Insertion order is preserved.
• Heterogeneous elements are allowed and null insertion is possible.
• Every method present in the vector is synchronized and hence vector
object is thread safe.
Method of vector
• addElement(Object o) method from Vector(C)
• removeElement(Object o) method from Vector(C)
• removeElementAt(int index) method from Vector(C)
• removeAllElements() method from Vector(C)
• Object firstElement() method from Vector(C) //For Acccessing
Elements.
• Object lastElement() method from Vector(C)
• int size() – how many elements are present in the vector
• int capacity() – how many objects the vector can hold
• Enumeration elements() – to get the objects one by one from the
collection
Vector v = new Vector();
Creates an empty vector object with default initial capacity 10. Once Vector
reaches its max capacity then a new vector will be crated with (double)
capacity = current capacity*2.
Vector v = new Vector(int initial_capacity);
Vector v = new Vector(int initial_capacity, int incremental_capacity);
Vector v = new Vector(Collection c);
Example
import java.util.Vector;
public class TestVector {
public static void main(String[] args) {
Vector v = new Vector();
for(int i=1; i<=10;i++) {
v.addElement(i);
}
System.out.println(v.capacity());
v.addElement("A");
System.out.println(v.capacity());
System.out.println(v);
}
}
Output
10
20
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, A]
Stack Class
Stack is a class presents in java.util package which extends from Vector class.
So, it is the child class of Vector and it is a specially designed for last-in-first-out
(LIFO) order.
Stack s = new Stack();
Method of Stack
push(Object o) – To insert an object into the Stack
pop(Object o) – To remove an object and return the top of the Stack
peek() – To return top of the Stack without removal
empty() – Returns true if the Stack is empty
int search(Object o) – Returns offset if the element is available otherwise
returns -1
Example
import java.util.Stack;
public class TestStack {
public static void main(String[] args) {
Stack s = new Stack();
s.push("A");
s.push("B");
s.push("C");
System.out.println(s);
System.out.println(s.search("A"));
System.out.println(s.search("Z"));
System.out.println(s);
s.pop();
System.out.println(s);
s.pop();
System.out.println(s);
}}
Output
[A, B, C]
3
-1
[A, B, C]
[A, B]
[A]
Cursors: If you want to get object one by one from the collection then we
should go for cursor.
There are 3 types of cursors available in Java. 1. Enumeration 2. Iterator 3.
ListIterator
1. Enumeration(I): We can use Enumeration to get objects one by one from
legacy collection object. We can create Enumeration object by using
elements() method of Vector class.
Ex: Enumeration e = v.elements();
Methods:(i) public boolean hasMoreElements(); (ii) public object
nextElement();
Limitations of Enumeration:
(i)We can apply Enumeration concept only for legacy classes and it is not
a universal cursor.
(ii) By using Enumeration, we can get only read access and we can’t
perform remove operation To overcome above limitations, we should go
for Iterator.
Example:
import java.util.Enumeration;
import java.util.Vector;
public class TestEnum {
public static void main(String[] args) {
Vector v = new Vector();
for(int i =0;i<=5;i++) {
v.addElement(i);
}
System.out.println(v);
Enumeration e = v.elements();
while(e.hasMoreElements())
{
Integer I = (Integer) e.nextElement();
System.out.println(I);
} }}
2. Iterator(I): We can apply Iterator concept for any collection object and
hence it is universal cursor. By using Iterator we can perform both read
and remove operations. We can create Iterator object by using iterator()
method of collection interface.
Ex: Iterator itr = c.iterator();
 Methods: (i) public boolean hasNext(); (ii) public Object next(); (iii) public
void remove();
Limitations of Iterator:
(i) By using Enumeration and Iterator we can always move only forward
direction and we can’t move backward direction these are single
direction cursors but not bidirectional cursors.
(ii) By using Iterator, we can perform only read and remove operations
and we can’t perform replacement and addition of new objects
To overcome above limitations, we should go for ListIterator
Example:
import java.util.ArrayList;
import java.util.Iterator;
public class TestItr {

public static void main(String[] args) {

ArrayList al = new ArrayList();
for(int i =0;i<=5;i++) {
al.add(i);
}
System.out.println(al);
Iterator itr = al.iterator();
while(itr.hasNext()) {
Integer I = (Integer)itr.next();
System.out.println(I);
}}}

3. ListIterator: By using ListIterator we can move either forward direction

or backward direction and hence it is bidirectional cursor. By using
ListIterator we can perform replacement and addition of new objects
along with read and remove operations. We can create ListIterator by
using listIterator() method of List interface.
Ex: ListIterator ltr = l.listIteratorI(); // ‘l’ is any List object
Methods: ListIterator is the child interface of Iterator and hence all
methods present on Iterator by default available to ListIterator.
ListIterator defines the following 9 methods.
Forward Operation Backward Operation Other Operation
public boolean hasNext() public boolean public void add(Object
public Object next() hasPrevious() o)
 public int nextIndex() public Object previous() public void remove()
public int previousIndex() public void set(Object o)
Example:
import java.util.ArrayList;
import java.util.ListIterator;
public class ListItrTest {
public static void main(String[] args) {
ArrayList al = new ArrayList();
al.add("A");
al.add("B");
al.add("c");
al.add("D");
System.out.println(al);
ListIterator itr = al.listIterator();
while (itr.hasNext()) {
String s = (String) itr.next();
System.out.println(s);
} }}
Comparison between Enumeration, Iterator and ListIterator:
Property Enumeration Iterator ListIterator
Where we can Only for legacy For any collection For only List object
apply classes object
version 1.0 v 1.2 v 1.2 v
Movement Single directional Single directional Bidirectional
Allowed Only Read Read & Remove Read, Remove, Add,
Operations Replace
How can we By using elements() By using iterator() By using ListIterator()
get? method of Vector(C) method of of List(I)
Collection(I)

Set(I): Set is the child interface of Collection interface. If we want to represent

a group of individual objects as single entity where duplicates are not allowed
and insertion order not preserved, then we go for Set.
HashSet(C): HashSet is a class presents in java.util package which implements
from Set, Cloneable and Serializable interfaces.
Properties:
• The underlying DS is Hashtable.
 • Duplicate objects are not allowed, Insertion order is not preserved and it
is based on hash code of objects.
• Heterogeneous elements are allowed and null insertion is possible (only
once).
• If our frequent operation is search, then HashSet is the best choice.
HashSet h = new HashSet(); Creates an empty HashSet object with default
initial capacity 16 and default fill ratio 0.75
Fill Ratio (or) Load Factor: After filling how much ratio a new HashSet object
will be created, this ratio is called Fill Ratio. For example fill ratio 0.75 means
after filling 75% ratio a new HashSet object will be created automatically.
Example
import java.util.HashSet;
public class TestHashSet {
public static void main(String[] args) {
HashSet h = new HashSet();
h.add("B");
h.add("c");
h.add("B");
h.add("D");
h.add(10);
h.add(null);
System.out.println(h);
}}
Output:
[D, c, B, 10, null]
LinkedHashSet(C): LinkedHashSet is a class presents in java.util package which
extends (inherits) from HashSet class and implements from Set, Cloneable and
Serializable interfaces.
HashSet vs LinkedHashSet: It is exactly same as HashSet including constructors
and methods except the following differences.
HashSet LinkedHashSet
The underlying DS is Hash table. The underlying DS is LinkedList and
Hash table
Insertion order not preserved. Insertion order preserved.
Introduced in 1.2v Introduced in 1.4v

Note: In general, we can use LinkedHashSet to develop cache based

applications where duplicates are not allowed and insertion order preserved.
import java.util.LinkedHashSet;
public class TestHashSet {
public static void main(String[] args) {
LinkedHashSet h = new LinkedHashSet();
h.add("B");
h.add("c");
h.add("B");
h.add("D");
h.add(10);
h.add(null);
System.out.println(h);
}}
Output:
[B, c, D, 10, null]
SortedSet(I): SortedSet is the child interface of Set interface. If we want to
represent a group of individual objects as single entity where duplicates are not
allowed but all objects should be inserted according to some sorting order,
then we go for SortedSet.
SortedSet interface defines the following specific methods.
(a) Object first() - returns first element of the SortedSet
(b) Object last() - returns last element of the SortedSet
(c) SortedSet headSet(Object obj) – returns SortedSet whose elements are <obj
(d) SortedSet tailSet(Object obj) - returns SortedSet whose elements are >= obj
(e) SortedSet subSet(Object obj1, Object obj2) - returns SortedSet whose
elements are >= obj1 and < obj2
(f) Comparator comparator() – return Comparator object that describes
underlying sorting technique like ascending, descending etc.
(a) first() – 100 (b) last – 120 (c) headSet(106) – {100,101,104} (d) tailSet(106) –
{106,110,115,120} (e) subSet(101,115) – {101,104,106,110}
NavigableSet(I): NavigableSet is the child interface of SortedSet and it defines
several methods for navigation purposes.
TreeSet is a class in Java's java.util package that implements the NavigableSet
interface. It is part of the Java Collections Framework and provides a set
implementation that stores elements in a sorted order. The elements are
sorted either by their natural ordering or by a comparator provided at set
creation time.
Methods
• first(): Returns the first (lowest) element.
• last(): Returns the last (highest) element.
• ceiling(E e): Returns the least element greater than or equal to the given
element, or null if no such element exists.
• floor(E e): Returns the greatest element less than or equal to the given
element, or null if no such element exists.
• higher(E e): Returns the least element strictly greater than the given
element, or null if no such element exists.
• lower(E e): Returns the greatest element strictly less than the given
element, or null if no such element exists.
• pollFirst(): Retrieves and removes the first (lowest) element, or returns
null if the set is empty.
• pollLast(): Retrieves and removes the last (highest) element, or returns
null if the set is empty.
 Example
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
TreeSet<Integer> treeSet = new TreeSet<>();
// Adding elements
treeSet.add(5);
treeSet.add(1);
treeSet.add(10);
treeSet.add(3);
// Displaying the TreeSet
System.out.println("TreeSet: " + treeSet); // Output: [1, 3, 5, 10]
// Navigational methods
System.out.println("First: " + treeSet.first()); // Output: 1
System.out.println("Last: " + treeSet.last()); // Output: 10
System.out.println("Ceiling(4): " + treeSet.ceiling(4)); // Output: 5
System.out.println("Floor(4): " + treeSet.floor(4)); // Output: 3
System.out.println("Higher(5): " + treeSet.higher(5)); // Output: 10
System.out.println("Lower(5): " + treeSet.lower(5)); // Output: 3
// Polling methods
System.out.println("Poll First: " + treeSet.pollFirst()); // Output: 1
System.out.println("Poll Last: " + treeSet.pollLast()); // Output: 10
}}
Comparable(I): It is present in java.lang package and it contains only one
method compareTo().
public int compareTo(Object o)
Ex: obj1.compareTo(obj2); //compareTo() method is used to compare two objects.
obj1 the object which is to be inserted, obj2 the object which is already inserted.
(a) returns -ve value if obj1 comes before obj2
(b) returns +ve value if obj1 comes after obj2
(c) returns 0 if obj1 is equals to obj2
Example:
public class Emp implements Comparable<Emp>{
int id;
String name;
public Emp(int id, String name) {
super();
this.id = id;
this.name = name; }
public int getId() {
return id; }
public void setId(int id) {
this.id = id; }
public String getName() {
return name; }
public void setName(String name) {
this.name = name; }
public Emp() {
super(); }
public String toString() {
return "Emp [id=" + id + ", name=" + name + "]"; }
public int compareTo(Emp ee) {
return this.id-ee.id;
// return this.getName().compareTo(ee.getName());
} }
 import java.util.Collections;
public class ComparableTest {
public static void main(String[] args) {
ArrayList<Emp> al = new ArrayList<Emp>();
Emp e1 = new Emp();
e1.setId(109);
e1.setName("Bhalu");
al.add(e1);
Emp e2 = new Emp();
e2.setId(34);
e2.setName("Lalu");
al.add(e2);
Emp e3 = new Emp();
e3.setId(21);
e3.setName("Ankit");
al.add(e3);
System.out.println(al);
Collections.sort(al);
System.out.println("Using comparable "+al); }}
Comparator(I): Comparator present in java.util package and it defines 2 methods
Compare() and equals().
1. public int compare(Object obj1, Object obj2)
(a) returns -ve value if obj1 comes before obj2 (
(b) returns +ve value if obj1 comes after obj2
(c) returns 0 if obj1 is equals to obj2
2. public boolean equals(Object o)
When ever we are implementing Comparator interface complusory we should
provide implementation only for compare() method and we are not required to
provide implementation for equals() method because it is already available from
Object class through inheritance.
Example:
import java.util.ArrayList;
import java.util.Collections;
public class ComparatorTest {
public static void main(String[] args) {
ArrayList<Emp> al = new ArrayList<Emp>();
Emp e1 = new Emp();
e1.setId(109);
e1.setName("Bhalu");
al.add(e1);
Emp e2 = new Emp();
e2.setId(34);
e2.setName("Lalu");
al.add(e2);
Emp e3 = new Emp();
e3.setId(21);
e3.setName("Ankit");
al.add(e3);
Collections.sort(al , new IdComparator());
System.out.println("Using comparator by Id "+al);
Collections.sort(al , new NameComparator());
System.out.println("Using comparable by Name "+al); }}
Sort By ID create class IdComparator
import java.util.Comparator;
public class IdComparator implements Comparator<Emp>
{
public int compare(Emp e1, Emp e2) {
return e1.getId()-e2.getId();
}}
Sort By Name create class NameComparator
import java.util.Comparator;
public class NameComparator implements Comparator<Emp> {
public int compare(Emp e1, Emp e2) {
return e1.getName().compareTo(e2.getName());
}}
Queue(I): Queue is the child interface of Collection. If we want to represent a group
of individual objects prior to processing, then we should go for Queue. For example,
before sending SMS messages all mobile numbers we have to store in some DS. In
which order we added mobile numbers in the same order only messages should be
delivered. For this FIFO requirement Queue is the best choice.
• add(E e): Inserts the specified element into the queue if possible, returning
true upon success and throwing an exception if the queue is full.
• offer(E e): Inserts the specified element into the queue if possible, returning
true upon success and false if the queue is full.
• remove(): Retrieves and removes the head of the queue, throwing an
exception if the queue is empty.
• poll(): Retrieves and removes the head of the queue, returning null if the
queue is empty.
• element(): Retrieves, but does not remove, the head of the queue, throwing
an exception if the queue is empty.
• peek(): Retrieves, but does not remove, the head of the queue, returning null
if the queue is empty.
import java.util.LinkedList;
import java.util.Queue;
public class TestQueue {
public static void main(String[] args) {
Queue q = new LinkedList();
q.offer(12);
q.offer(54);
q.offer(90);
 q.offer(23);
System.out.println(q);
Integer i = (Integer) q.poll();
System.out.println(i); }}
PriorityQueue(C): PriorityQueue is a class presents in java.util package. The priority
can be either default natural sorting order or customized sorting order defined by
Comparator.
Properties:

• Insertion order is not preserved and it is based on some priority.

• Duplicate objects are allowed.
• Null is not allowed even as the first element also.
import java.util.PriorityQueue;
import java.util.Queue;
public class TestPriorityQueue {
public static void main(String[] args) {
PriorityQueue q = new PriorityQueue();
q.offer(10);
q.offer(20);
q.offer(15);
q.offer(12);
q.offer(3);
System.out.println(q);
Integer i = (Integer) q.poll();
System.out.println(i);
}}
Output:
[3, 10, 15, 20, 12]
3
BlockingQueue(I): BlockingQueue is a type of queue that supports operations that
wait for the queue to become non-empty when retrieving an element, and wait for
space to become available in the queue when storing an element. These queues are
part of the java.util.concurrent package and are designed for use in concurrent
programming where multiple threads may be adding and removing elements.
PriorityBlockingQueue: PriorityBlockingQueue is an unbounded blocking queue that
uses the same ordering rules as PriorityQueue. Elements are ordered according to
their natural ordering, or by a Comparator provided at queue construction time,
depending on which constructor is used.
The put() method never blocks since the queue is unbounded, but the take() method
can block if the queue is empty.
import java.util.concurrent.PriorityBlockingQueue;
public class TestPriorityBQ {
public static void main(String[] args) throws InterruptedException {
PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>();
queue.add(4);
queue.add(1);
queue.add(3);
System.out.println(queue.take()); // Outputs 1
System.out.println(queue.take()); // Outputs 3
System.out.println(queue.take()); // Outputs 4 }}
LinkedBlockingQueue: LinkedBlockingQueue is a bounded blocking queue backed by
linked nodes. The optional capacity bound can be specified at the time of creation. If
not specified, it will default to Integer.MAX_VALUE.
The put() method blocks if the queue is full, and the take() method blocks if the
queue is empty.
import java.util.concurrent.LinkedBlockingQueue;
public class TestLinkedBQ{
public static void main(String[] args) throws InterruptedException {
LinkedBlockingQueue<Integer> queue = new LinkedBlockingQueue<>(2);
queue.put(1);
 queue.put(2);
System.out.println(queue.take()); // Outputs 1
queue.put(20);
System.out.println(queue);
System.out.println(queue.take()); // Outputs 2 }}
Output:
1
[2, 20]
2
Map(I): Map is not child interface of Collection. If we want represent a group of
objects as key value pairs then we should go for Map interface.
Key Value
101 A
102 B
103 C

Both keys and values are objects only. Duplicate keys are not allowed but duplicate
values are allowed.
Methods
(a) Object put(Object key, Object value) – to add one key value pair to the Map. If
the key is already present, then old value will be replaced with new value and
returns old value.
Ex: m.put(101, “A”); // Add this entry to the Map and returns null
m.put(101, “B”);// Replace ‘A’ with ‘B’, has same key and returns ‘A’
(b) void putAll(Map p) - Add the specified Map to current Map /Ex: m1.add(m2)
(c) Object get(Object key) – Returns the value associated with specified key.
(d) Object remove(Object key) – Removes the entry associated with specified key.
(e) boolean containsKey(Object key) - Search the specified key in the Map.
(f) boolean containsValue(Object value) - Search the specified value in the Map.
(g) boolean isEmpty()
(h) int size()
(i) void clear() – All key value pairs will be removed from the Map.
Collection Views of Map Methods:
(j) Set keySet() - returns the Set containing all the keys
(k) Collection values() – returns the Set containing all the values
(l) Set entrySet() - return the Set view containing all the keys and values
Entry(I): Entry is the sub interface of Map. We will be accessed it by Map.Entry name.
A Map is a group of key value pairs and each key value pair is called an entry. Hence,
Map is considered as a collection of entry objects. Without existing Map object, there
is no chance of existing entry object.
Methods:
(a) Object getKey() – used to obtain key
(b) Object getValue() - used to obtain value
(c) Object setValue(Object o) - used to replace the old value with new value
HashMap(C): HashMap is a class presents in java.util package which implements from
Map, Cloneable, Serializable interfaces.
Properties:
• The underlying DS is Hash table.
• Insertion order is not preserved and it is based on hash code of keys.
• Duplicate keys are not allowed, but values can be duplicated.
• Heterogeneous objects are allowed for both key and value.
• Null is allowed for key (only once). Null is allowed for value (any no of tomes).
 • HashMap is the best choice if our frequent operation is search operation.
(a) HashMap m = new HashMap();
Creates an empty HashMap with default initial capacity 16 and default fill ratio 0.75.
(b) HashMap m = new HashMap(int initial_capacity);
(c) HashMap m = new HashMap(int initial_capacity, float fill_ratio);
(d) HashMap m1 = new HashMap(Map m2);
Creates HashMap object ‘m1’ by using the elements of the given Map object m2.
Example:
import java.util.HashMap;
import java.util.Map;
public class HashMapExample {
public static void main(String[] args) {
// Creating a HashMap using the Map interface
HashMap<String, Integer> map = new HashMap<>();
// Adding key-value pairs to the HashMap
map.put("Apple", 10);
map.put("Banana", 20);
map.put("Orange", 30);
// Retrieving a value associated with a key
int appleCount = map.get("Apple");
System.out.println("Count of Apple: " + appleCount);
// Iterating over the key-value pairs
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}}}
Output:
Count of Apple: 10
Banana is available.
Key: Apple, Value: 10
Key: Orange, Value: 30
Key: Banana, Value: 20
LinkedHashMap(C): LinkedHashMap is a class presents in java.util package which
extends (inherits) from HashMap class and implements from Map, Cloneable and
Serializable interfaces.
Example:
import java.util.LinkedHashMap;
import java.util.Map;
public class LinkedHashMapExample {
public static void main(String[] args) {
// Creating a LinkedHashMap using the Map interface
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
// Adding key-value pairs to the LinkedHashMap
linkedHashMap.put("Apple", 10);
linkedHashMap.put("Banana", 20);
linkedHashMap.put("Orange", 30);
linkedHashMap.put("Grapes", 40);
// Retrieving a value associated with a key
int appleCount = linkedHashMap.get("Apple");
System.out.println("Count of Apple: " + appleCount);
// Iterating over the key-value pairs
System.out.println("Entries in the LinkedHashMap:");
for (Map.Entry<String, Integer> entry : linkedHashMap.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
// Removing a key-value pair
linkedHashMap.remove("Orange");
// Checking the size of the LinkedHashMap
 System.out.println("Size of LinkedHashMap after removing Orange: " +
linkedHashMap.size());
// Iterating over the key-value pairs again to show the current state
System.out.println("Entries in the LinkedHashMap after removal:");
for (Map.Entry<String, Integer> entry : linkedHashMap.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
} }}
Output:
Count of Apple: 10
Entries in the LinkedHashMap:
Key: Apple, Value: 10
Key: Banana, Value: 20
Key: Orange, Value: 30
Key: Grapes, Value: 40
Size of LinkedHashMap after removing Orange: 3
Entries in the LinkedHashMap after removal:
Key: Apple, Value: 10
Key: Banana, Value: 20
Key: Grapes, Value: 40
== vs equals():
In general, == operator meant for reference comparison (address comparison)
whereas equals() method meant for content comparison.
Ex: Integer i1 = new Integer(10); i1
Integer i2 = new Integer(10); i2
SOP(i1 == i2); // false
SOP(i1.equals(i2)); // true
SortedMap(I): SortedMap is the child interface of Map interface. If we want to
represent a group of key value pairs according to some sorting order of keys, then we
should go for SortedMap.
SortedMap interface defines the following specific methods.
(a) Object firstKey() - returns first element of the SortedMap
(b) Object lastKey() - returns last element of the SortedMap
(c) SortedSet headMap(Object key) – returns SortedMap whose elements are < key
(d) SortedSet tailMap(Object key) - returns SortedMap whose elements are >= key
(e) SortedSet subMap(Object key1, Object key2) - returns SortedMap whose
elements are >= key1 and < key2
(f) Comparator comparator() – return Comparator object that describes underlying
sorting technique like ascending, descending etc. If we are using default natural
sorting order, then we will get null.
NavigableMap(I): NavigableMap is the child interface of SortedMap. It defines
several methods for navigation purposes. NavigableMap defines the following
methods.
(a) floorKey(e) - Returns the greatest key less than or equal to the given key, or null if
none.
(b) lowerKey(e) - Returns the greatest key strictly less than the given key.
(c) ceilingKey(e) - Returns the least key greater than or equal to the given key, or null
if none.
(d) higherKey(e) - Returns the least key strictly greater than the given key, or null if
none.
(e) pollFirstEntry() – remove and return first element
(f) pollLastEntry() – remove and return last element
(g) descendingMap() – returns NavigableMap in reverse order
TreeMap(C): TreeMap is a class presents in java.util package which implements from
NavigableMap, Cloneable, Serializable interfaces.
Properties:
The underlying DS is Red-Black tree.
Insertion order is not preserved and it is based on some sorting order of keys.
Duplicate keys are not allowed, but values can be duplicated.
If we are depending on default natural sorting order, then keys should be
homogeneous and comparable otherwise we will get RE as ClassCastException.
If we are defining our own sorting by Comparator, then keys need not be
homogeneous and comparable. We can take heterogeneous non-comparable objects
also.
Whether we are depending on default natural sorting or customized sorting order
there are no restrictions for values. We can take heterogeneous non-comparable
objects also.
Null Acceptance:
(i) For non-empty TreeMap if we are trying to insert an entry will ‘null’ key then we
will get RE as NullPointerException.
(ii) For empty TreeMap as the first entry with ‘null’ key is allowed but after inserting
that entry if we are trying to insert any other entry then we will get RE as
NullPointerException.
Note: The above ‘null’ acceptance rule applicable until 1.6v only. From 1.7v on
wards ‘null’ is not allowed for key. But for values we can use ‘null’ any no of times
there is no restriction whether it is 1.6v or 1.7v.
Example:
import java.util.Map;
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
// Creating a TreeMap
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Adding entries to the TreeMap
treeMap.put(13, "Three");
treeMap.put(10, "One");
treeMap.put(2, "Two");
treeMap.put(15, "Five");
treeMap.put(4, "Four");
 // Displaying the TreeMap
System.out.println("TreeMap: " + treeMap);
// Iterating through the TreeMap
for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()); }
System.out.println(treeMap. firstKey());
System.out.println(treeMap. headMap(3));
System.out.println(treeMap.tailMap(4));
System.out.println(treeMap.subMap(3,5));
System.out.println("floor "+treeMap.floorKey(4));
System.out.println("lower "+treeMap.lowerKey(5));
System.out.println("ceiling "+treeMap.ceilingKey(5));
System.out.println("pollFirstEntry "+treeMap.pollFirstEntry());
System.out.println("TreeMap: " + treeMap);
}}
Hashtable(C): Hashtable is a class presents in java.util package which
extends(inherits) from Dictionary class and implements from Map, Cloneable,
Serializable interfaces.
) Properties:
• The underlying DS is Hash table.
• Insertion order is not preserved and it is based on hash code of keys.
• Duplicate keys are not allowed, but values can be duplicated.
• Heterogeneous objects are allowed for both keys and values.
• ‘null’ is not allowed for both key and values otherwise we will get RE as
NullPointerException.
• Every method present in Hash table is synchronized and hence Hashtable
object is thread safe.

• Hashtable is the best choice if our frequent operation is search operation.

(a) Hashtable h = new Hashtable(); Creates an empty Hashtable object with default
initial capacity 11 and default fill ratio 0.75.
(b) Hashtable h = new Hashtable(int initial_capacity); Creates an empty Hashtable
object with specified initial capacity and default fill ratio 0.75
(c) Hashtable h = new Hashtable(int initial_capacity, float fill_ratio);
(d) Hashtable h = new Hashtable(Map m);
Creates an equivalent Hashtable object for the given Map. This constructor meant for
inter conversion between map objects.
Example:
import java.util.Hashtable;
public class HashTableExample {
public static void main(String[] args) {
// Creating a HashTable instance
Hashtable<String, Integer> hashTable = new Hashtable<>();
hashTable.put("key4", 1);
hashTable.put("key2", 2);
hashTable.put("key3", 3);
System.out.println("HashTable : " + hashTable);
Integer value1 = hashTable.get("key1");
System.out.println("Get key1: " + value1); // Output: 1
// Attempting to retrieve a value for a non-existing key "key4"
Integer value4 = hashTable.get("key4");
System.out.println("Get key4: " + value4); // Output: null
// Deleting a key-value pair using the key "key2"
hashTable.remove("key2");
// Printing the HashTable after deleting "key2"
System.out.println("HashTable after deleting key2: " + hashTable);
// Updating the value associated with "key1"
hashTable.put("key1", 10);
// Printing the HashTable after updating "key1"
 System.out.println("HashTable after updating key1: " + hashTable); }}
Output:
HashTable : {key4=1, key3=3, key2=2}
Get key1: null
Get key4: 1
HashTable after deleting key2: {key4=1, key3=3}
HashTable after updating key1: {key4=1, key3=3, key1=10}

Difference Between HashMap and HashTable

HashMap and Hashtable are both data structures used to store key-value pairs,
but they have some key differences:
1. Thread Safety:
HashMap: Not thread-safe. It is not synchronized, meaning that if multiple
threads access a HashMap concurrently and at least one of the threads
modifies it, external synchronization is needed.
Hashtable: Thread-safe. It is synchronized, meaning it can be safely used by
multiple threads without additional synchronization. Each method in Hashtable
is synchronized.
2. Performance:
HashMap: Generally faster because it is unsynchronized. The lack of
synchronization overhead makes it more suitable for single-threaded
applications or where manual synchronization is used.
Hashtable: Slower due to synchronization overhead, making it less performant
in scenarios where thread safety is not required.
3. Null Values:
HashMap: Allows one null key and multiple null values.
Hashtable: Does not allow null keys or values. Attempting to use null will result
in a NullPointerException.
4. Legacy:
HashMap: Part of the Java Collections Framework since Java 1.2.
Hashtable: A legacy class from the original version of Java (JDK 1.0). Although it
has been retrofitted to implement the Map interface, it is generally
recommended to use newer collections like HashMap.