Contents

• Memory management
  • Stack and Heap
  • Generations
  • Metaspace
  • Garbage collection
• Collections
  • List
  • Set
  • Map
  • Queue and Dequeue
• Generics
• Parallel processing
• Functional interfaces

Memory management

JVM takes care of memory management leaving only some configuration decisions to developers.

Stack and Heap

These are the two memory spaces in JVM.

Stack

1. Created for each thread, therefore thread safe.
2. Stores local variables, references to the objects on the heap, methods.
3. Memory is freed when the methods finish executing and the variables are no longer needed, ordered (LIFO).
4. Easy, fast access.
5. StackOverFlowError when resources are exhausted, the available memory can be configured with the -Xss option.

Heap

1. Created with an application, it’s shared among all threads.
2. Stores the objects and their fields.
3. Needs complex memory management techniques like Garbage Collectors to free memory space, there is no order or memory allocation pattern.
4. Access is slower.
5. OutOfMemoryError when resources are exhausted, the available memory can be configured with the -Xmx and -Xms options.

Generations

Heap memory stores objects according to their age.

Young Generation

1. Stores new objects.
2. Is cleared with minor garbage collection.
3. If an object lives long enough it is promoted to Old Generation.

Old Generation

1. Stores the objects promoted from Young Generation.
2. Is cleared with major garbage collection.

Metaspace

It is an off-heap memory manager used to allocate memory for class metadata. When a class loader gets collected, all class metadata it accumulated is released.

Garbage collection

Automatic management for clearing the memory from all objects from Young and Old Generations that are no longer needed.

Garbage-First (G1) Garbage Collector is selected by default on most system configurations. This collector is mostly concurrent, it scales well and keeps garbage collection pauses short.

Manual selection of a garbage collector:

1. Adjust the size of the heap space first.
2. If that doesn’t help, follow the Oracle guidelines for selecting a collector:
   • serial collector for application with small data set, run on a single processor, without pause-time requirements;
   • parallel collector when peak app performance is a priority and there are no pause-time requirements;
   • mostly concurrent collector when response time is more important than overall throughput and short collection pauses are required;
   • fully concurrent collector when response time is a high priority.

Collections

The core collection interfaces are shown in the image below:

General facts:

1. Note, that a Map is not a true Collection. However, it’s generally discussed among other collections for the sake of simplicity.
2. Collection interfaces are generic. Therefore, we should specify the type of object contained in the collection we’re declaring.
3. The modification operations in each interface are designated optional. Consult documentation of the selected implementation to make sure you won’t get UnsupportedOperationException by calling a method that isn’t implemented.
4. The Collections.synchronized… methods provides synchronization. e.g. Collections.synchronizedSet(...);.
5. Fail-fast behavior of an iterator cannot be guaranteed in the presence of unsynchronized concurrent modification.

A simple diagram comparing selected aspects of the most used collections:

Below you’ll find short descriptions of the implementations of the collection interfaces.

List

• insertion order
• duplicate values allowed
• we control where in the list each element is inserted and can access elements by their index
• the List.of() and List.copyOf methods return unmodifiable lists
• javadoc

General-purpose implementations

ArrayList

• optimized for storing objects, fast random access
• permits null elements
• resizable, the ensureCapacity method may reduce the amount of incremental reallocation
• fail-fast iterator
• javadoc

LinkedList

• optimized for data manipulation (inserting and deleting elements)
• permits null elements
• when accessed through the Queue interface, acts as a FIFO queue
• fail-fast iterator
• javadoc

Special-purpose implementations

CopyOnWriteArrayList

• a thread-safe variant of ArrayList
• performant if read-only operations vastly outnumber mutative operations and the set size stays small
• we iterate over an immutable snapshot of the content
• the iterator won’t reflect changes to the list since the iterator was created
• all mutative operations are implemented by making a fresh copy
• javadoc

Time complexity

(*) O(1) if a copy is not needed

(**) O(n) if add(index i)

Set

• unique values
• unspecified behaviour if the value of an element is changed in a manner that affects equals (caution when storing mutable objects)
• the Set.of() and Set.copyOf methods return unmodifiable sets
• javadoc

General-purpose implementations

HashSet

• not ordered
• permits the null element
• don’t set the initial capacity too high if iteration performance is important
• useful for counting, reports
• fail-fast iterator
• javadoc

LinkedHashSet

• insertion order
• permits the null element
• iteration times for this class are unaffected by capacity
• fail-fast iterator
• javadoc

TreeSet

• elements are ordered using their natural ordering, or by a Comparator provided at creation time
• element comparison is done using compareTo() method and not equals like in the Set interface
• fail-fast iterator
• javadoc

Special-purpose implementations

EnumSet

• all elements must come from a single enum type
• doesn’t permit the null element (NullPointerException)
• very compact and efficient, operations are likely (though not guaranteed) to be much faster than their HashSet counterparts
• javadoc

CopyOnWriteArraySet

• uses an internal CopyOnWriteArrayList for all of its operations. Thus, it shares the same basic properties.
• javadoc

Concurrent implementations

ConcurrentSkipListSet

• insertion, removal, and access operations safely execute concurrently by multiple threads
• elements are ordered using their natural ordering, or by a Comparator provided at creation time
• doesn’t permit the null element
• iterating in ascending order is faster that in descending order
• javadoc

Time complexity

Map

• unique keys
• unspecified behaviour if the key is changed in a manner that affects equals (caution when using mutable objects as keys)
• a map’s contents can be viewed as a set of keys (keySet), collection of values (values), or set of key-value mappings (entrySet)
• the Map.of(), Map.copyOf and Map.ofEntries methods return unmodifiable maps
• javadoc

General-purpose implementations

HashMap

• not ordered
• permits null values and null key
• don’t set the initial capacity too high if iteration performance is important
• useful for counting by the key, local cache
• fail-fast iterator
• javadoc

LinkedHashMap

• insertion order
• in access-ordered linked hash maps, merely querying the map with get is a structural modification and affects iteration order
• fail-fast iterator
• javadoc

TreeMap

• elements are ordered using their natural ordering, or by a Comparator provided at creation time
• element comparison is done using compareTo() method and not equals like in the Set interface
• fail-fast iterator
• javadoc

Special-purpose implementations

EnumMap

• all keys must come from a single enum type
• maps are maintained in the natural order of their keys (the order in which the enum constants are declared)
• doesn’t permit null keys (NullPointerException), permits null values
• very compact and efficient
• weakly consistent iterator
• javadoc

IdentityHashMap

• intentionally violates Map’s general contract, designed for use only in the rare cases wherein reference-equality semantics are required
• a typical use of this class is topology-preserving object graph transformations (e.g. serialization or deep-copying) or maintaining proxy objects (e.g. maintaining a proxy object for each object in the program being debugged)
• fail-fast iterator
• javadoc

WeakHashMap

• an entry will automatically be removed when its key is no longer in ordinary use
• fail-fast iterator
• javadoc

Concurrent implementations

ConcurrentHashMap

• even though all operations are thread-safe, retrieval operations do not entail locking, and there is not any support for locking the entire table in a way that prevents all access
• all arguments to all task methods must be non-null
• javadoc

ConcurrentSkipListMap

• insertion, removal, update and access operations safely execute concurrently by multiple threads
• elements are ordered using their natural ordering, or by a Comparator provided at creation time
• doesn’t permit null keys or values
• iterating keys in ascending order is faster that in descending order
• weakly consistent iterator
• javadoc

Time complexity

Queue and Dequeue

• Queue: usually FIFO, whatever the ordering used, the head of the queue is the element that would be removed by a call to remove or poll
• Dequeue: both FIFO or LIFO, all new elements can be inserted, retrieved and removed at both ends
• Queue javadoc, Dequeue javadoc

General-purpose implementations

LinkedList

• see List

PriorityQueue

• heap implementation
• elements are ordered using their natural ordering, or by a Comparator provided at creation time
• iterator doesn’t guarantee order, use Arrays.sort(pq.toArray()) if you need ordered traversal
• doesn’t permit null elements
• javadoc

ArrayDeque

• efficient, resizable array implementation of the Deque interface
• has no capacity restrictions, grows as necessary to support usage
• doesn’t permit null elements
• faster than Stack when used as a stack, faster than LinkedList when used as a queue
• fail-fast iterator
• javadoc

Concurrent implementations

ConcurrentLinkedQueue, ConcurrentLinkedDequeue, LinkedBlockingQueue, LinkedBlockingDequeue, ArrayBlockingQueue, PriorityBlockingQueue, DelayQueue, SynchronousQueue, LinkedTransferQueue,

Time complexity

Generics

• Enable types to be parameters when defining classes, interfaces and methods:

public class Box<T> {
    
    private T t;

    public void set(T t) { this.t = t; }
    public T get() { return t; }
}

• Eliminate casting:

List list = new ArrayList();
list.add("hello");
String s = (String) list.get(0);

List<String> list = new ArrayList<String>();
list.add("hello");
String s = list.get(0); // no cast

• Provide type checks at compile time making code more stable.

Type Parameter Naming Conventions

• E - Element (used extensively by the Java Collections Framework)
• K - Key
• N - Number
• T - Type
• V - Value
• S,U,V etc. - 2nd, 3rd, 4th types
• ? - wildcard

Type erasure

• replace all type parameters in generic types with their bounds or Object if the type parameters are unbounded,
• insert type casts if necessary to preserve type safety,
• generate bridge methods to preserve polymorphism in extended generic types.

Restrictions

With generics, you can’t:

• instantiate Generic Types with Primitive Types
• create Instances of Type Parameters
• declare Static Fields Whose Types are Type Parameters
• use Casts or instanceof With Parameterized Types
• create Arrays of Parameterized Types
• create, Catch, or Throw Objects of Parameterized Types
• overload a Method Where the Formal Parameter Types of Each Overload Erase to the Same Raw Type

Questions and Exercises: Generics

Parallel processing

Speedups for parallel compared to sequential forms are common but not guaranteed. Parallel operations involving brief functions on small maps may execute more slowly than sequential forms if the underlying work to parallelize the computation is more expensive than the computation itself. Similarly, parallelization may not lead to much actual parallelism if all processors are busy performing unrelated tasks.

Functional interfaces

Reference