Java Collections

List

• Iterable: allow using with for each loop.
• Fail-fast iterator: concurrent modification by multiple threads will throw ConcurrentModificationException.

• ArrayList: dynamic array.
  • Slower than standard array (resizing operation copies all of the elements)
  • Similar to vector in C-C++.
  • Not synchronized in multi-thread environment. Use CopyOnWriteArrayList or Vector if we want synchronization.
• CopyOnWriteArrayList: clone the array before perform operations, only good for read operation.
• Vector: implements List interface and has some legacy methods.
• Stack: a subclass of Vector that implements the stack data structure.
• LinkedList: implemented using double linked list data structure.
  • Also support methods with index (because it implements AbstractList).
  • Slower than ArrayList when it comes to accessing individual elements.
  • Requires additional memory for pointer.

Map

• Interfaces: Map and SortedMap.
• Implementations: HashMap, LinkedHashMap, TreeMap.
• Can not contain duplicate elements.
• Allows null key and null value: HashMap and LinkedHashMap.
• Maintains orders of insertion: TreeMap and LinkedHashMap.

• HashMap:
  • Unsorted.
  • Unsynchronized. Solution: Collections.synchronizedMap(new HashMap(...)).
  • Only one null key.
  • Implemented using linked list. Each node has 4 fields: int hash, K key, V value, Node next.
• TreeMap:
  • Sorted according to the natural ordering of keys or by a pre-defined Comparator.
  • Unsynchronized. Solution: Collections.synchronizedSortedMap(new TreeMap(...)).
  • Not allow null keys, but multiple null values can be associated with different keys.
  • Implemented using a Red-Black tree (a type of self-balacing binary search tree). Each node in the tree has:
    • 3 Variables (K key=Key, V value=Value, boolean color=Color)
    • 3 References (Entry left = Left, Entry right = Right, Entry parent = Parent)
• LinkedHashMap: an extension of HashMap and
  • Elements can be accessed by insertion order (need more CPU and memory).
  • Unsynchronized. Solution: Collections.synchronizedMap(new LinkedHashMap(...)).
  • Implemented using doubly-linked list. Each node has the following fields: hash (to make search and insert operation faster), before, key, value and after (for retrieving elements in insertion order).
• ConcurrentHashMap: better choice when there are more reads than writes.
  • Uses HashTable as underlying data structure.
  • Divides object into 16 segments (16 is called concurrency-level and it is default value) and lock the particular segment when a thread performs update operation on that segment.
    • At a time, 16 update operations can be performed by threads.
    • This is called segment locking or bucket locking.
  • Not allow null keys and null values.
• HashTable: a legacy class in which all methods are synchronized using synchronized keyword.

Set

• All the classes of the Set interface are internally backed up by Map.
• Only need to pass a value instead of key-value pair. The value acts as the key and for its value, Java use a constant variable. So in the key-value pair, all the values will be the same.

• HashSet
  • Order of elements is not guaranteed.
  • Null elements are allowed.
  • Duplicate values are not allowed.
  • Implemented using HashMap.
• LinkedHashSet:
  • Maintains insertion order (need more CPU and memory).
  • Extends HashSet but uses doubly-linked list across all elements.

Difference between LinkedHashMap and LinkedHashSet:

Categories	LinkedHashMap	LinkedHashSet
Operation	Used to store key-value pairs.	Used to store collection of things
Duplicates	Take unique and no duplicate keys but can take duplicate values	Stores no duplicate element
Implements	HashMap	HashSet
Example	Map<String, Integer> lhm = new LinkedHashMap<String, Integer>();	Set<String> lhs = new LinkedhashSet<String>();

• SortedSet:
  • All of the elements must implement Comparable interface and must be mutually comparable (two objects accepts each other as the argument to their compareTo method).
• NavigableSet: implementation of SortedSet for navigating through the set.
• TreeSet:
  • Objects are stored in sorted and ascending order. We also can iterate in descending order.
  • Implementation of NavigableSet.
  • Implemented using self-balancing tree.

Queue

• PriorityQueue:
  • Elements are ordered by
    • Natural ordering (an element with a maximum ASCII value will have the highest priority).
    • A pre-defined comparator.
  • Not allow null values.
  • Is not thread-safe.
  • Implemented using priority heap.

Example:

• PriorityBlockingQueue:
  • Uses the same ordering rules as PriorityQueue.
  • Not allow null values.
  • Thread-safe.

---

Resources

• Collections in Java - GeeksforGeeks