Set VS List VS Map in Java

Collections in Java

A collection is an object that groups multiple elements into a single unit. The Java Collections Framework is a unified architecture for representing and manipulating collections. It contains the interfaces, their implementations, and algorithms to process the data stored in a collection.

In Java, we have a Collection interface extended by other interfaces such as List, Set, and Queue. Apart from the Collection interface, we have a Map interface. The Map does not implement the Collection interface because it stores key-value pairs, and the classes that come under the Collection interface store only values.

Methods of Collection interface are —

int size(): This method returns the number of element collection has.

boolean isEmpty(): If the collection is empty then this method will return true else it will return false.

boolean add(E e): This method add the object we pass as argument in collection.

boolean remove(Object o): Removes the argument object from the collection and returns true if the object exists in collection. Else returns false.

boolean contains(Object o): Returns true if the object exists in the collection.

There few more methods as well like Iterator<E> iteroator(), Object[] toArray(), boolean containsAll(Collection<?> c), boolean addAll(Collection<? extends E> c), boolean removeAll(Collection<?> c) etc.

We can understand by seeing all this methods that these are generic method and collection is a generic type.

Let’s first talk about List —

List is an interface which extends the Collection interface. We can guess by its name that its job is to contain list of elements by maintaining insertion Order. List is implemented by ArrayList, Vector and LinkedList collections. LinkedList also implements the Queue interface. We can see in the picture that every list has their own way to store and contain elements.

ArrayList is the most widely used implementation of the List interface. Some of the salient features of an ArrayList are:

1. Elements are stored in the order of insertion.
2. It allows the storage of duplicate elements.
3. ArrayList also supports null elements.

The default constructor does not take any argument and creates a List of size zero. Below is the syntax to create ArrayList using the default constructor.

List list = new ArrayList();

The LinkedList class in Java implements the List and the Deque interface. Some of the salient features of a LinkedList are:

1. The elements are inserted in the order of insertion.
2. It supports duplicate elements.
3. We can add any number of null elements.

The default constructor does not take any argument and creates a LinkedList of size zero. Below is the syntax to create LinkedList using the default constructor.

List<Integer> list = new LinkedList<Integer>();

The ArrayList and LinkedList data structures are not thread-safe. This means that if we are working in an environment where multiple threads are simultaneously adding or removing elements from a list, it may not work as intended. If a thread is iterating over a list and, in the meantime, another thread tries to add an element to the list, then ConcurrentModificationException will be thrown.

Now, if we want to use a list in a multi-threaded environment, we have few options. The first option is using a Vector. The Vector is a legacy class in which all the methods are synchronized. Since for each operation, such as add or remove, the entire list is locked, it is slow. Hence it is no longer used.

The second option is making our list thread-safe by using the Collections.synchronizedList() method. The problem with this method is that it also locks the entire list for each operation. So, there is no performance benefit.

To overcome these issues CopyOnWriteArrayList was introduced. This is a thread-safe list with high performance. In this lesson, we will focus on how it is used.

Set is also a data structure like List. But we cannot store any duplicate element inside it. It has all the methods of List. Though we can not get random access of an element from Set like we can from List. It does not have get method. If we element already exits and we try to insert it again then the add method will return false. HashSet, LinkedHashSet are the concrete implications of Set interface. TreeSet implements SortedSet interface which extends the Set interface.

HashSet is a class in the java.utils package which implements the Set interface. Some of the features of HashSet are:

1. HashSet does not allow duplicate elements.
2. HashSet allows only one null element.
3. The elements are inserted in random order in a HashSet.
4. A HashSet is internally backed by a HashMap.

The simplest way to create a HashSet is by using the no-arg constructor. This constructor creates a HashSet with an initial capacity of 16 and a load factor of 0.75.

Below is the code syntax to create a HashSet.

Set<Integer> set= new HashSet<>();

Load factor is a number that defines when a Set should be resized. If the load factor is 0.75, then the Set should be resized when it is 75% full.

Java TreeSet class implements the Set interface that uses a tree for storage. It inherits the AbstractSet class and implements the NavigableSet interface.

Some of the features of TreeSet are:

1. TreeSet does not allow duplicate elements.
2. TreeSet class doesn’t allow null elements.
3. Since elements are stored in a tree, the access and retrieval times are quite fast in a TreeSet.
4. The elements are stored in ascending order in a TreeSet.

Map in Java —

Map in Java

Map is key-value pair collection in java. Map interface does not extend the Collection interface. It works separately and sometimes called as dictionary or associative array. In map every key is mapped with a value. It is like a linear array. Only difference is array has integer index but map can have key of any type like integer, string or object.

HashMap is a class in the java.utils package that implements the Map interface. It is used to store the key-value pair. Let’s suppose we need to store the stock prices of some companies. In this case, we can use a HashMap. The company name will be the key and the stock price will be the value.

Some of the features of HashMap are:

1. The keys should be unique.
2. HashMap allows only one null key.
3. The values can be null or duplicate.
4. The keys are stored in random order.

Below is the code syntax to create a HashMap. It states that the key is a String type and the value is an Integer type.

Map<String, Integer> map = new HashMap<>();

TreeMap is a class in the java.utils package that stores the keys in sorted order. Some of the features of TreeMap are:

1. The entries in TreeMap are sorted in the natural ordering of its keys.
2. It does not allow null keys, however there can be null values.
3. The TreeMap is not thread-safe, although it can be made thread-safe using the synchronizedMap() method of the Collections class.

Since a TreeMap stores the keys in sorted order, the objects that we are storing in the TreeMap should either implement the Comparable interface or we should pass a Comparator while creating the TreeMap object.

A HashMap does not maintain insertion order and TreeMap stores the elements in sorted order. Now, if we want to store the elements in a Map in insertion order, then a LinkedHashMap can be used. LinkedHashMap is a class in the java.utils package that implements the Map interface and extends the HashMap class. It is similar to HashMap with the additional feature of maintaining the order of elements inserted into it.

Some of the important features of a LinkedHashMap are:

1. It does not allow duplicate keys.
2. It may have one null key and multiple null values.
3. It is non-synchronized.

We can make our Map thread-safe by using the synchronizedMap() method of the Collections class. This method returns SynchronizedMap in which all the methods are synchronized. There are lots of differences between a ConcurrentHashMap and a SynchronizedMap, which we will discuss next.

Although all the basic operations such as insert, fetch, replace, and remove in a ConcurrentHashMap are similar to the HashMap. But we will discuss them so that you are not confused about how to perform these operations in a ConcurrentHashMap.