Java Collections Framework

Oracle Guide

Tutorial

The Interface Collection has many implementations and a hierarchy quite wide.

Implementations Types

Internal management

Implementations

Interfaces	Hash table Implementations	Resizable array Implementations	Tree Implementations	Linked list Implementations	Hash table + Linked list Implementations
Set	HashSet	-	TreeSet	-	LinkedHashSet
List	-	ArrayList	-	LinkedList	-
Queue	-	-	-	-	-
Deque	-	ArrayDeque	-	LinkedList	-
Map	HashMap	-	TreeMap	-	LinkedHashMap

Concurrent Modification

When one or more thread is iterating over the collection, in between, one thread changes the structure of the collection (either adding the element to the collection or by deleting the element in the collection or by updating the value at particular position in the collection) is known as Concurrent Modification

Fail fast Iterator

Fail fast iterator while iterating through the collection , instantly throws Concurrent Modification Exception if there is structural modification of the collection . Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. Fail-fast iterator can throw ConcurrentModificationException in two scenarios :

Single Threaded Environment

After the creation of the iterator , structure is modified at any time by any method other than iterator's own remove method.

Multiple Threaded Environment

If one thread is modifying the structure of the collection while other thread is iterating over it .

You can consult documentation in Oracle any collection this says: Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

So what would be a way to validate?

Iterator read internal data structure (object array) directly . The internal data structure(i.e object array) should not be modified while iterating through the collection. To ensure this it maintains an internal flag "mods" .Iterator checks the "mods" flag whenever it gets the next value (using hasNext() method and next() method). Value of mods flag changes whenever there is an structural modification. Thus indicating iterator to throw ConcurrentModificationException.

Fail Safe Iterator

Fail Safe Iterator makes copy of the internal data structure (object array) and iterates over the copied data structure. Any structural modification done to the iterator affects the copied data structure. So , original data structure remains structurally unchanged .Hence , no ConcurrentModificationException throws by the fail safe iterator.

Two issues associated with Fail Safe Iterator are :

Overhead of maintaining the copied data structure i.e memory.
Fail safe iterator does not guarantee that the data being read is the data currently in the original data structure.

According to Oracle docs , fail safe iterator is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don’t want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException.The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove(), set(), and add()) are not supported. These methods throw UnsupportedOperationException.

Example Fail Fast

Does not throw because of only one element is in collection	Throw exception

Example Fail Safe

Table Comparative Information

	Fail Fast Iterator	Fail Safe Iterator
Examples	ArrayList,Vector,HashMap,HashSet	CopyOnWriteArrayList,ConcurrentHashMap
Throw ConcurrentModification Exception	Yes	No
Memory Overhead	No	Yes
Clone object	No	Yes

Implementations by Interface

Interface	Implementation Class		Interface	Implementation Class
List	AbstractList AbstractSequentialList ArrayList AttributeList CopyOnWriteArrayList LinkedList RoleList RoleUnresolvedList Stack Vector		Set	AbstractSet ConcurrentSkipListSet CopyOnWriteArraySet EnumSet HashSet JobStateReasons LinkedHashSet TreeSet
Map	AbstractMap Attributes AuthProvider ConcurrentHashMap ConcurrentSkipListMap EnumMap HashMap Hashtable IdentityHashMap LinkedHashMap		Map	PrinterStateReasons Properties Provider RenderingHints SimpleBindings TabularDataSupport TreeMap UIDefaults WeakHashMap

Comparative Internal

S = Synchronized

TEX = Throws Exception on Repeat

RE= Repeated Element

FF= Fail - Fast

Class	S	Data	Default	FF	Extend	RE	TEX
HasSet	No	HashMap<E,Object> map = new HashMap<>()	Empty	Yes	AbstractSet	No	No
LinkedHashSet	No	HashMap<E,Object> map = new LinkedHashMap<>()	16 and 0.75 Factor	Yes	HashSet	No	No
TreeSet	No	new TreeMap<E,Object>() Implements -> NavigableMap<E,Object> m	Empty	Yes	AbstractSet	No	No
AttributeList	No	Object[] elementData	Empty	No	ArrayList	Yes	No
ArrayList	No	transient Object[] elementData	Empty	Yes	AbstractList	Yes	No
LinkedList	No	Object[] elementData	Empty	Yes	AbstractSequentialList	Yes	No
Vector	Yes	Object[] elementData	10	Yes	AbstractList	Yes	No
TreeMap	No	transient Entry<K,V> root Entry<K,V> left; Entry<K,V> right; Entry<K,V> parent;	Empty	Yes	AbstractMap	No	No
HashMap	No	transient Node<K,V>[] table transient Set<Map.Entry<K,V>> entrySet;	Empty	Yes	AbstractMap	No	No
HashTable	Yes	Entry<?,?>[] table	Empty - 11 and 0.75 Factor	Yes	Dictionary	No	No
LinkedHashMap	No	LinkedHashMap.Entry<K,V> head; LinkedHashMap.Entry<K,V> tail;	Empty	Yes	HashMap	No	No

Do not you know ?

HasSet, LinkedHashSet and TreeSet internally have HashMap, LinkedHashMap and NavigableMap respectively. The most interesting thing here is that to emulate Map they use Dummy Object as value

HasSet is a simple structure Map<T, Dummy> T = Object to insert in Set collection

AttributeList, ArrayList, LinkedList, Vector are Arrays of data

Trees like TreeSet and TreeMap applying Tree concept

LinkedHashSet and LinkedHashMap use the reference behavior

ArrayList

ArrayList	LinkedList

LinkedList VRS ArrayList

ArrayList is more quickly for search elements because of Index based. LinkedList is more dificult since even elements has references for the next object the memory has elements in many parts then the next object could be in wide parts

LinkedList has better use of memory, when they need to grow. But your inserting/searching/removing approach can be slow when the List is big. The thing here is take in consideration what is better performance respoonse / performance memory. Everything is linked to amount of elements.

If ArrayList is little practically growth is not much difference remember ArrayList has to growth move elements, create new object array

I will be working with profiling in order to give all of you an example with number comparations

Comparation ArrayList Vrs LinkedList

Class 1.000.000	Methods


Records: 1 000 000 ArrayList has initialization with default constructor () Proccesor I7 2,7Ghz	ArrayList Creation Time: 8 Seconds Memory: 1670 LinkedList Creation Time: 5 Seconds Memory:1730
Records: 2 000 000 ArrayList has initialization with default constructor () Proccesor I7 2,7Ghz	ArrayList Creation Time: 15 Seconds Memory: 3300 LinkedList Creation Time: 12 Seconds Memory:3300
Records: 2 150 000 ArrayList has initialization with default constructor () Proccesor I7 2,7Ghz	ArrayList Creation Time: 16 Seconds Memory: 3550 LinkedList Creation Time: 12 Seconds Memory:3550
Records: 2 200 000 ArrayList has initialization with default constructor () Proccesor I7 2,7Ghz	ArrayList Creation Time: 20 Seconds Memory: 3850 LinkedList Creation Time: 12 Seconds Memory:3650
Records: 2 200 000 ArrayList has initialization with amount (2200000) Proccesor I7 2,7Ghz	ArrayList Creation Time: 18 Seconds Memory: 3650
Records: 1 000 000, 2 000 000, 2 200 000 Proccesor I7 2,7Ghz ArrayList and LinkedList iterate for all members in collection I have done a test of contais Method	ArrayList and LinkedList never reaching to 1 Second In other words they do not have any difference

Thanks to: https://dzone.com/articles/java-collection-performance and leolewis for the next work this is an evidence of the collections performances https://github.com/leolewis/sandbox/blob/master/src/org/leo/benchmark/Benchmark.java