# Java: Maps

### Key-Value pairs

Key-value pairs are stored in maps.

### Map interfaces

- Map implemented by HashMap and TreeMap
- SortedMap implemented by TreeMap.
- Map.Entry which describes access methods to the key-value pairs.

### Implementing classes

A number of classes implement the Map interface, including HashMap, TreeMap, LinkedHashMap, WeakHashMap, ConcurrentHashMap, and Properties. The most generally useful class is HashMap.

- `java.util.HashMap` is implemented with a hash table. Access time is O(1). Entries are unsorted.
- `java.util.LinkedHashMap` is implemented with a hash table. Access time is O(1). Entries are sorted in either entry order or order of last access, which is useful for implementing a LRU (least recently used) caching policy.
- `java.util.TreeMap` is implemented as a balanced binary tree. Access time is O(log N). Entries are sorted.

## Map interface methods

Here are some of the most useful Map methods. `m` is a Map, `b` is a boolean, `i` is an int, `set` is a Set, `col` is a Collection, `key` is an Object used as the key used to store a value, `val` is an Object stored as the value associated with the key.

Result | Method | Description
--- | --- | ---
Adding key-value pairs to a map
`obj =` | `m.put(key, val)` | Creates mapping from `key` to `val`. It returns the previous value (or null) associated with the key.
| `m.putAll(map2)` | Adds all key-value entries from another map, map2.
Removing key-value pairs from a map
`` | `m.clear()` | Removes all elements from a Map
`obj =` | `m.remove(key)` | Deletes mapping from `key` to anything. Returns previous value (or null) associated with the key.
Retrieving information from the map
`b =` | `m.containsKey(key)` | Returns true if `m` contains a key `key`
`b =` | `m.containsValue(val)` | Returns true if `m` contains `val` as one of the values
`obj =` | `m.get(key)` | Returns value corresponding to `key`, or `null` if there is no mapping. If `null` has been stored as a value, use `containsKey` to see if there is a mapping.
`b =` | `m.isEmpty()` | Returns `true` if `m` contains no mappings.
`i =` | `m.size()` | Returns number of mappings in `m`.
Retrieving all keys, values, or key-value pairs (necessary for iteration)
`set =` | `m.entrySet()` | Returns set of Map.Entry values for all mappings.
`set =` | `m.keySet()` | Returns Set of keys.
`col =` | `m.values()` | Returns a Collection view of the values in `m`.

## Map.Entry interface methods

Each element is a map has a key and value. Each key-value pair is saved in a `java.util.Map.Entry` object. A set of these map entries can be obtained by calling a map's `entrySet()` method. Iterating over a map is done by iterating over this set.

Assume in the following table that `me` is a `Map.Entry` object.

Result | Method | Description
--- | --- | ---
`obj =` | `me.getKey()` | Returns the key from the pair.
`obj =` | `me.getValue(key)` | Returns the value from the Map pair.
`obj =` | `me.setValue(val)` | This is an optional operation and may not be supported by all `Map.Entry` objects. Sets the value of the pair, which modifies the `Map` which it belongs to. Returns the orginal value.

## HashMap class constructors

In addition to implemented the Map interface methods, HashMap has the following constructors.

Result | Constructor | Description
--- | --- | ---
`hmap =` | `new HashMap()` | Creates a new HashMap with default initial capacity 16 and load factor 0.75.
`hmap =` | `new HashMap(initialCapacity)` | Creates a new HashMap with the specified initial int capacity.
`hmap =` | `new HashMap(initialCapacity, loadFactor)` | Creates a new HashMap with the specified capacity which will not exceed a specified (float) load factor.
`hmap =` | `new HashMap(mp)` | Creates a new HashMap with elements from the Map mp

## SortedMap interface methods

The SortedMap interface is used by TreeMap and adds additional methods to reflect that a TreeMap is sorted.

Result | Method | Description
--- | --- | ---
`comp =` | `comparator()` | Returns Comparator used to compare keys. null if natural ordering used (eg, String).
`obj =` | `firstKey()` | Key of first (in sorted order) element.
`obj =` | `lastKey()` | Key of last (in sorted order) element.
`smp =` | `headMap(obj)` | Returns SortedMap of all elements less than obj.
`smp =` | `tailMap(obj)` | Returns SortedMap of all elements greater than or equal to obj.
`smp =` | `subMap(fromKey, toKey)` | Returns SortedMap of all elements greater than or equal to fromKey and less than toKey.

## TreeMap class constructors

TreeMap implements the Map and SortedMap interface methods. In constrast to HashMap, TreeMap keeps the balanced binary tree in sorted order by key. If the key has a natural order (eg, String) this is ok, but often you will supply a Comparator object that tells how two keys compare. It has the following constructors.

Result | Constructor | Description
--- | --- | ---
`tmap =` | `new TreeMap()` | Creates new TreeMap. Keys sorted by natural order.
`tmap =` | `new TreeMap(comp)` | Creates new TreeMap using Comparator comp to sort keys.
`tmap =` | `new TreeMap(mp)` | Creates new TreeMap from Map mp using natural ordering.
`tmap =` | `new TreeMap(smp)` | Creates new TreeMap from SortedMap smp using key ordering from smp.