Java: Collections and Maps

Data-Structures are to a Developer as what a Chisel-and-Hammer is to a Sculptor.

# Collections in Java

## Descriptions:

Collections framework is a large set of data structures used for managing data in Java
Collection is a group of individual objects represented as a single unit. Java provides
Collection Framework which defines several classes and interfaces to represent a group
of objects as a single unit.

## Types:

- Map
- Set
- List

## Map:

### Introduction

Map is generic interface for a key-value pair data structure
Takes place of the Dictionary class, which was a purely abstract class and not an Interface.

### Types:

Known Sub-Interfaces:
- Bindings, ConcurrentMap, ConcurrentNavigableMap, LogicalMessageContext,
MessageContext, NavigableMap, SOAPMessageContext, SortedMap

All Known Implementing Classes:
- AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap,
HashMap, Hashtable, IdentityHashMap, LinkedHashMap,
PrinterStateReasons, Properties, Provider, RenderingHints, SimpleBindings, TabularDataSupport,
TreeMap, UIDefaults, WeakHashMap

#### Notable Implementations:

- HashMap : Hash-table based implementation of Map.
HashMap extends AbstractMap and implements Map alongwith Serializable and Clonable
HashMap is un-synchronized. Not thread safe.
HashMap allows one NULL key and multiple NULL values.
HashMap performance depends on initial-capacity and load-factor.
Initial-Capacity: No of buckets allowed
Load-Factor: How full the Map is allowed to be build before its capacity is
automatically increased. When total number of entries
reach (current capacity*load-factor) then the HashMap is rehashed such
that number of buckets is twice.
Default load-factor : 0.75
- TreeMap : A Red-Black Tree based Navigable Map implementation.
Map is sorted as per natural ordering of its keys, or based on Comparator
provided at Map creation time.
Performance guaranteed is log(n) for containsKey, get, put and remove methods.
Extends AbstractMap and implements NavigableMap, alongwith Serializable and Clonable
TreeMap is un-synchronized. Not thread-safe.

- Hashtable : Maps a key to a value.
Stores non-null value as key or value.
Extends Dictionary class.
Does not allow any NULL key or NULL values
Hashtable performance depends on initial-capacity and load factor.
Capacity: Total number of buckets allowed
Load-Factor: How full the Hashtable is allowd to be build before its capacity is automatically increased. When total number of entries
reach (current capacity*load-factor) then the Hashtable is rehasehd such that number of buckets is increased.
Default load-factor: 0.75

Hashtable is Thread safe (synchronized).
If Map is not used across threads, its recommended to use HashMap instead of Hashtable.

- ConcurrentHashMap : A hashtable which provides concurrency of retrievals and
high concurrency for updates, without blocking entire table.
Retrieval operations do not block. So, may overlap with update operations
(including put and remove).
So, retrievals reflect the current state of Map at the time of operation
being performed.
Iterators are designed such that they work for one thread at a time.
Table is dynamically expanded when there are too many collisions.