Collections API based on the following flavors:
Notice, that
Remember: An implementation class can be either Ordered or Unordered and Sorted or Unsorted. However Sorted implementation is always Ordered cause sorting itself is a specific type of ordering:
A
An
However, to add elements to the beginning and remove from it's interior require linear-time O(n)
in
The best way to do it at creation time, to prevent accidental unsynchronized access to the list:
It also implements
Prefer
A
In addition to
However
So, prefer using the
Also prefer to use
but cares only about uniqueness - it doesn't allow duplicates.
Bulk operations are particularly well suited to Sets. e.g.
Choose
that maintains doubly-linked list running through all of its elements.
Use
A
Choose
A
which both could be a type of
A
And like a
However it contains the Collection View methods(
which allow a
Use
or to ask for a
The basic operations of
A
So, if u need use it in concurrency take a look on
Or u can synchronize
and like a
Also,
So,
A
,
The simple
Beyond the simple
| Interface | Description |
|---|---|
Lists | Lists of things ordered by index |
Sets | Groups of Unique things (without duplicates) |
Maps | Key-Value entries with unique Keys |
Queues | Items arranged by the order to be processed (FIFO/LIFO) |
Notice, that
Map-related collections do not implement java.util.Collection:
Remember: An implementation class can be either Ordered or Unordered and Sorted or Unsorted. However Sorted implementation is always Ordered cause sorting itself is a specific type of ordering:
| Type | Details |
|---|---|
| Ordered | U can iterate though it in certain predictable order. (List Implementations and
classes that contain prefix Linked are ordered) |
| Unordered | Means that iteration order might be random. (HashMap, HashSet, HashTable, etc. are unordered) |
| Sorted | Order determined according the sorting rules defined during creation. (classes that contain prefix Tree) are sorted e.g TreeSet, TreeMap |
| Unsorted | Items arranged by the insertion-order, but not sorted by certain rules. |
U always should override
U can use only mutually comparable elements in sorted collections. So, those should have the same type & implement
equals() & hashcode() methods in elements that are used in collections baked on hashcode, those contain Hash prefix.U can use only mutually comparable elements in sorted collections. So, those should have the same type & implement
Comparable functional interface.
Or those should be sorted/searched via the using Comparator.
List Interface
A
List interface is all about index, it provides such methods like
get(int index), indexOf(Object o), add(int index,Object obj), etc.List implementations are ordered by position that u determine during the invocation
of add/set(int index, E element) or by adding it to the end.
ArrayList
It's ordered by index, but not sorted collection.An
ArrayList has dynamic size, so most of the time (except capacity optimization cases) u shouldn't care about it length during creation:)
ArrayList offers constant-time positional access and it's just plain fast.However, to add elements to the beginning and remove from it's interior require linear-time O(n)
in
ArrayList.ArrayList is not synchronized, but if at least one of the threads modifies the list structurally
during concurrent access to it, ArrayList should be synchronized externally.The best way to do it at creation time, to prevent accidental unsynchronized access to the list:
List list = Collections.synchronizedList(new ArrayList(...));
It also implements
RandomAccess marker interface,
otherwords u can use it to fast (constant-time) random access.Prefer
ArrayList over a LinkedList
when u need fast iteration but aren't likely to be doing a lot of insertion & deletion.LinkedList
LikeArrayList a LinkedList is unsynchronized & ordered by index position list that permits all elements (including null), except it's not possible to define initial capacity in LinkedList.A
LinkedList is the list implementation where the elements are doubly-linked to one another.In addition to
List interface the LinkedList class implements Deque that gives you methods for adding and removing from the beginning or end,
which makes it easy choise for implementing a stack or queue.
A
LinkedList offers constant-time for the adding/removing the elements from the begging or the end.
However positional access in LinkedList requires linear-time O(n), that means it iterate more slowly than ArrayList.
So, choose it when u need frequent insertion/deletion operations.Vector
Think aboutVector as about synchronized ArrayList.Vector is the only class other than ArrayList to implement
RandomAccess.However
Vector is deprecated & has loads of legacy operations!So, prefer using the
ArrayList with external syncronization instead of Vector.Also prefer to use
Deque implementation instead of Stack class that is a Vector descendant.Set Interface
Set it's straightforward interface which contains only methods inherited fromCollection,but cares only about uniqueness - it doesn't allow duplicates.
Bulk operations are particularly well suited to Sets. e.g.
s1.containsAll(s2), s1.retainAll(s2), etc.
Copy one set before calling the appropriate bulk operation to non destruct the original set:
Setintersection = new HashSet (s1); intersection.retainAll(s2)
HashSet
AHashSet is an unsorted & unordered Set that permits the null element.HashSet is much faster than TreeSet, it offers constant-time for most operations (add, remove,
contains and size) but no ordering guarantees.HashSet uses the inserted object hashcode, so the more efficient your hashcode() implementation, the faster access you'll get.HashSet when u need collection with no duplicates and you don't care about the order when iterate through it.LinkedHashSet
ALinkedHashSet is ordered (keeps insertion-order) HashSet,that maintains doubly-linked list running through all of its elements.
Use
LinkedHashSet instead of HashSet when you need predictable iteration order - it allows u to iterate through the elements in the order they were inserted.A
LinkedHashSet runs nearly as fast as HashSet, but iteration time is not affected by capacity(cause it's not possible to tune it like in HashSet).
When you use either
Otherwise, the default
HashSet or LinkedHashSet, the entries must override equals() and hashCode() methods!Otherwise, the default
Object.hashCode() method will allow multiple objects, that u might consider meaningfully equal to be added into
your no-duplicates set.TreeSet
ATreeSet is implementation of the SortedSet,
which entries are sorted by natural-order (ascending) or according to sorting rules of Comparator used at the creation time.Choose
TreeSet when u need collection of the unique elements sorted by either natural or the specific order.Map Interface
A
Map allows to map your unique keys (IDs) to the specific values,which both could be a type of
Object.A
Map cares about the keys uniqueness.And like a
Set it's relies on the equals() method to determine whether two keys are the same or different.Maps don't implement Collection interface.keySet, values, entrySet),which allow a
Map to be viewed as a Collection.Use
Map to do things like search for a value based on the key,or to ask for a
Collection either of just the values, of just the keysHashMap
AHashMap it's unsynchronized, unsorted, unordered Map with high performance.
HashMap unlike Hashtable allows one null key and multiple null values in a collection.Map (put, get, containsKey, containsValue, size, and isEmpty) behave exactly like their counterparts in Hashtable.A
HashMap is mach more faster than HashTable but not synchronized!So, if u need use it in concurrency take a look on
ConcurrentHashMap cause HashTable is slow.Or u can synchronize
HashMap externally: Collections.synchronizedMap(hashMap);
Hashtable
Hashtable is like a Vector synchronized & deprecated interface.Hashtable doesn't allow neither null key nor null values!LinkedHashMap
LinkedHashMap offers near HashMap speedand like a
LinkedHashSet guarantee, that iteration order will be the same as insertion-order.Also,
LinkedHashMap provides the removeEldestEntry method which makes it very easy to implement a custom cache via overriding it.TreeMap
Like aTreeSet implement NavigableSet which is descendant of SortedSet,
TreeMap implements NavigableMap which is descendant of SortedMap,therefore it's a sorted either by natural-order or by the rules defined by the used Comparator.So,
TreeMap rely on the same principles as TreeSet, which means your entries should be mutually-comparable.
It consistent with equals, and entries either should implement Comparable interface or be sorted via using some Comparator implementation.
TreeMap & TreeSet contain a batch of extremely useful methods for elements-polling (retrieving and removing the first/last (highest) element).Queue Interface
A
Queue is an ordered Collection designed to hold the elements in order to be processed, that
typically is FIFO (firs-in, first-out).Priority Queue
Unlike the typical basic FIFO/LIFO queues that can be handled byLinkedList,
PriorityQueue is supposed to maintain "priority-in, priority-out" queue.PriorityQueue elements are ordered either by natural-ordering(first elements will be accessed first) or according to Comparatororder represents their relative priority.Deque Interface
The simple
Deque can be used both as FIFO (first-in, first-out) and LIFO (last-in, first-out).Beyond the simple
Queue in a Deque all new elements can be inserted, retrieved and removed at both ends.
LinkedList implements Deque interface in addition to List one.
Very nice article . Thanks for sharing good tutorials. You can see treemap examples on java vogue
ReplyDelete