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.