Collection Framework
@Author:M.Lakshmikar Reddy
Collection Framework:
A group of collection classes is called a Collection framework.
Before discuss about collection , we know the previous technology to grouping the objects. That technology is arrays.
Disadvantages with Arrays:
The array index size if fixed.
We cannot store different class objects into the same array. Reason is array can store only one data type of elements.
Adding the objects at the end of an array is easy. But , inserting and deleting the elements in the middle of the array is difficult.
Retrieving the elements from an array is easy but after retrieving the elements, if we want to process them then there are no methods available to carry out this.
Once you delete the item in array it kept that one as empty like a[2]=””.
Due to these problems, Programmers want a better mechanism to store a group of objects. The alternative is using an object to store a group of other objects. It means that we can use a class object as an array. Such an Object is called “Collection Object” or “Container Object”.
In fact collection object does not store the physical copies of other objects. The other objects are already available in memory, storing another copy of them into the collection object would be a more wasting of memory. So, JVM does not store the copies of other objects, it simply stores the references of other objects into a collection object.
Collection interface:
This interface can be used to represent a group of objects as a single entity.
It acts as root interface for entire collection framework.
It defines the most commonly used methods which can be applicable for any collection implemented class object
What Do You Do with a Collection?
Add objects to the collection.
Remove objects from the collection.
Find out if an object (or group of objects) is in the collection.
Retrieve an object from the collection (without removing it).
Iterate through the collection, looking at each element (object) one after another.
Flavors of Collection:
Four basic flavors of collections include Lists, Sets, Maps, Queues:
List interface:
List interface is a child interface of Collection interface. This can be used to represent group of individual objects in as a single entity where
Duplicates are allowed
Insertion order is preserved
Set interface:
Set is a child interface of Collection interface. it can be used to represent a group of individual objects as a single entity where
SortedSet:
it is child interface of Set interface. it can be used to represent a group of individual objects in to a single entity where
All the objects are arranged in some sorting order
Duplicates are not allowed.
NavigableSet :
It is child interface of SortedSet and provides several utility methods for navigation purposes
It doesn’t allows duplicates
Insertion order is preserved
It is introduced in 1.6 version
Queue interface:
If we want to represent a group of individual objects prior to processing, then we should go for Queue interface.
It is child interface of Collection interface.
Queues of things to process Ordered by FIFO or by priority.
It has introduced in 1.5 version.
Map interface:
Remember it is not a child Interface of Collection Interface and hence Map and Collection Interfaces doesn’t have any relationship.
It can be used for representing a group of Objects as key, value pairs.
Both keys and values should be objects
Keys can t be duplicated but values can be duplicated.
it has introduced in 1.2 version
SortedMap:
If we want to represent a group of objects as key value pairs where all the entries are arranged according some sorting order of keys then we should go for SortedMap.
It is child interface of Map.
It has introduced in 1.2 version
NavigableMap:
It is child interface of SortedMap and defines several method for navigation purpose
It is introduced in 1.6 version
Maps of things with keys May or may not be ordered and/or sorted;
duplicate keys are not allowed.
Common Collection Classes:
ArrayList: Fast iteration and fast random access.
Vector: It's like a slower ArrayList, but it has synchronized methods.
LinkedList: Good for adding elements to the ends, i.e., stacks and queues.
HashSet: Fast access, assures no duplicates, provides no ordering.
LinkedHashSet: No duplicates; iterates by insertion order.
TreeSet: No duplicates; iterates in sorted order.
HashMap: Fastest updates (key/value pairs); allows one null key,
many null values.
Hashtable: Like a slower HashMap (as with Vector, due to its synchronized
methods). No null values or null keys allowed.
LinkedHashMap: Faster iterations; iterates by insertion order or last accessed;
allows one null key, many null values.
TreeMap: A sorted map.
PriorityQueue: A to-do list ordered by the elements' priority.
Sorting and searching arrays and lists:
Sorting can be in natural order, or via a Comparable or many Comparators.
Implement Comparable using compareTo(); provides only one sort order.
Create many Comparators to sort a class many ways; implement compare().
To be sorted and searched, a List's elements must be comparable.
To be searched, an array or List must first be sorted.
Utility Classes:
Collections and
Arrays
Both of these java.util classes provide
A sort() method. Sort using a Comparator or sort using natural order.
A binarySearch() method. Search a pre-sorted array or List.
Arrays.asList() creates a List from an array and links them together.
Collections.reverse() reverses the order of elements in a List.
Collections.reverseOrder() returns a Comparator that sorts in reverse.
Lists and Sets have a toArray() method to create arrays.
The interface and class hierarchy for collections
Collections come in four basic flavors:
Lists Lists of things (classes that implement List).
Sets Unique things (classes that implement Set).
Maps Things with a unique ID (classes that implement Map).
Queues Things arranged by the order in which they are to be processed.
All the collection classes are in java.util package . The implementation classes of different interfaces are
| Interface type | Implementation classes |
| List | ArrayList LinkedList Vector Stack |
| Set | HashSet TreeSet LinkedHashSet |
| Queue | LinkedList PriorityQueue |
| Map | HashMap TreeMap LinkedHashMap Hashtable IdentityHashMap WeakHashMap |
List Interface:
List is a interfaces which extends to Collection interface.
About List:
List will allow null values
List will allow duplicate values
Order of elements is in which they are entered
Accessing elements by their index
Retrieving the elements using all the ways(for loop, foreach loop, Iterator, List Iterator, Enumeration)
Implementation classes for List interface :
ArrayList
LinkedList
Vector
Stack
Let discuss one by one.
ArrayList
It is class which extends to AbstractList implements to List , RandomAccess, Cloneable, Serializable interfaces
public class ArrayList
implements List
About ArrayList:
ArrayList can increase and decrease size dynamically
ArrayList increase its size every time by 50%.
ArrayList default size is 10.
ArrayList can hold item of different types
ArrayList have Predefined methods to perform operations
ArrayList method are not Synchronized.
If you delete the item from list the space of that index occupies by next item
ArrayList is good for retrieving the elements in specific position
Randomly we can pick the elements
ArrayList is a list backed by an array (Object[])
ArrayList is slow to access elements at the start and the end of the list.
To access elements at middle fast
Example:
import java.util.*;
class ArrayListEx
{
public static void main(String ar[]){
ArrayList al = new ArrayList();
al.add(125);
al.add(0,126);
al.add(0,126);
al.add(0,127);
al.add(128);
al.add(1,129);
al.add(1,129);
al.add(1,129);
al.add(1,130);
al.add(131);
al.add(2,132);
al.add(2,133);
al.add(2,al);
System.out.println(al);
System.out.println(al.get(0));
}
}
Output:
[127, 130, (this collection), 133, 132, 129, 129,129, 126, 126, 125, 128, 131]
127
List:
list will allow null values
list will allow duplicate values
order of elements in which they are enterd
accessing elements by their index is possible
retrieving using all the ways
if want sublist it can posible
Set:
set will not allow duplicate values
order of the elements may change in the set
accessing elements by their index is not possible in case of sets.
retrieving using Iterator's and Enumeration only
if want sublit it won't posible
| List | Set | Map |
| ArrayList | HashSet | HashMap |
| LinkedList | LinkedHashSet | LinkedHashMap |
| Vector | TreeSet | TreeMap |
| Stock | EnumSet | EnumMap |
|
|
| HashTable |
|
|
| IdentityHashMap |
|
|
| WeakHashMap |
| Array | ArrayList |
| The capacity of an Array is fixed
| ArrayList can increase and decrease size dynamically
|
| An Array is a collection of similar items
| ArrayList can hold item of different types |
| An Array can have multiple dimensions
| ArrayList always has exactly one dimension |
| once you delete the item in array it kept that one as empty like a[2]="" | in case of arraylist a[3]index occupies the position of a[2] |
| if you try to insert a[2] value array will throw error if any items reside inside | but in case of arraylist a[2] is inserted in same position but at the same time position of a[2] become a[3] if there is already an item exists |
| It won't have any predefined methods | It have some method to operate. |
| ArrayList | LinkedList |
arrylist is good for retiveing the elements in specific position | LinkedList is slow for retiveing the elements in specific position |
| their is no pointers in case of arraylist | in linkedlist we deal with pointers |
| Randomly we can pick the elements | Sequenced we can pick the elements |
| It is a list backed by an array | LinkedList is backed by a doubly-linked list, not an array |
| slow to access elements at the start and the end of the list | fast to access elements at the start and the end of the list |
| To access elements at middle fast | To access elements at middle slow |
|
| inserting and deleting elements is fast compared to ArrayList. |
| ArrayList | Vecotor |
It is not syncronized | It is syncronized by default |
In case of Single Thread, Using ArrayList is faster than the vector | In case of Multiple threads, Using vector ins faster than the ArrayList |
| ArrayList increases its size every time by 50%. | Vector increases its size every time by doubling it. |
| Arraylist has no default size | while vector has a default size of 10. |
|
|
|
| Linked list | stock |
Used for store and retrive data | Used for evaluation of expressions |
Insertion and deletion of elements from any where is possible | Only in top of stock |
| ArrayList | LinkedList | Vector |
public class ArrayList | public class LinkedList | public class Vector |
| Resizeable Array,unordered, allows duplicates and accepts null values | implemented as a and accepts null values | Growable array of objecs,unordered, allows duplicates and accepts null values.It can grow or shrink as needed |
| not synchronized hence not thread-safe. | Not synchronized | synchronized and thread-safe. |
| Provides Random Access | Provides optimal sequential access. | Provides Random Access |
| Use ArrayList if there is single Thread | Use: Inserts at the beginning or end are very fast.Deletions from the middle are very fast | use Vector class when there are multiple threads in the system |
| HashSet | TreeSet |
To store elements use hash table | use of Comparator |
hashset data is randomly placed | In a treeset data are placed in order. |
Some what slow thean treeset | A treeset is more efficient in case of search element. |
Store diff types of data | Store only similar data |
Initial capacity 16 | 0 |
It is more faster ,because no order and o(1) | Slow O(longn) |
LinkedHashSet:
Order is ----entered order
fast than HashSet
Maps:
| HashMap | HashTable | TreeMap | LinkedHashMap |
| Unidentified Order | Decending Order | Ascending Order | Insertion Order |
| UnSynchronized | Synchronized | UnSynchronized | UnSynchronized |
| The values can be null. But the key should be unique | does not let you have null value for key. | The values can be null. But the key should be unique | The values can be null. But the key should be unique |
| Map (interface) | Maintains key-value associations (pairs) so you can look up a value using a key. |
| HashMap* | Implementation based on a hash table. (Use this instead of Hashtable.) Provides constant-time performance for inserting and locating pairs. Performance can be adjusted via constructors that allow you to set the capacity and load factor of the hash table. |
| LinkedHashMap | Like a HashMap, but when you iterate through it, you get the pairs in insertion order, or in least-recently-used (LRU) order. Only slightly slower than a HashMap, except when iterating, where it is faster due to the linked list used to maintain the internal ordering. |
| TreeMap | Implementation based on a red-black tree. When you view the keys or the pairs, they will be in sorted order (determined by Comparable or Comparator, discussed later). The point of a TreeMap is that you get the results in sorted order. TreeMap is the only Map with the subMap( ) method, which allows you to return a portion of the tree. |
| WeakHashMap | A map of weak keys that allow objects referred to by the map to be released; designed to solve certain types of problems. If no references outside the map are held to a particular key, it may be garbage collected. |
| IdentityHashMap | A hash map that uses == instead of equals( ) to compare keys. Only for solving special types of problems; not for general use. |
HashMap:
The HashMap is a class which is used to perform some basic operations such as inserting, deleting, and locating elements in a Map . The java.util.HashMap class is implemented with and roughly equivalent to a Hashtable except that it is unsynchronized and permits null. It works with the Iterators requires a well-defined implementation of the method hashCode( ).
TreeMap:
The TreeMap implementation is useful when you need to traverse the keys from a collection in a sorted manner. The elements added to a TreeMap must be sortable in order to work properly. It is depend upon the size of the specified collection, it may be faster to add elements to a HashMap , then convert the map to a TreeMap for traversing the sorted keys.
LinkedHashMap:
A LinkedHashMap is implemented using both Hash table and linked list implementation of the Map interface. This implementation differs from HashMap that maintains a doubly-linked list running through all of its entries in it. The orders of its elements are based on the order in which they were inserted into the set (insertion-order).
LinkedHashMap- will preserve the order of insertion. If you iterate through all keys or values in LinkedHashMap, your traversal order would be the same as insertion order. You'll iterate through the items in LinkedHashMap in the order same as the insertion order.
TreeMap- TreeMap keeps the items in order similar to sorting. TreeMap creates a tree structure to keep all items sorted based on their keys. To compare between two keys, it uses compareTo() method of key objects. TreeMap does implement and additional interface, SortedMap.
You should only consider about using TreeMap or LinkedHashMap when you care for some type of ordering of items you put into your Map. Otherwise, just using HashMap is advisable and efficient. Because, HashMap does not have additional overload like TreeMap or HashMap.
In fact, It's not that one kind is better or worse than the others, the choice always should be made based on what you requirements are.
No comments:
Post a Comment