Maps

The SetMap Application

The examples in this and other documents in this section all part of the Java Application SetMap. Download the source archive SetMap.zip and install it as a Java Application with Existing Sources. See the Using NetBeans document for details.

Like others, the SetMap project has multiple Main Classes intended to illustrate various independent features. The simplest way to run the various classes is to right-click the file and select Run File either in the file itself or from the listing in the Projects window.

The Java files from the project which are referenced in this document are:
adapter/
  SetAdapter
  MapAdapter
  NavMapAdapter
util/
  SearchTreeMap
  OpenHashMap
demo/
  MapDemo
  RegularLinkedHashMaps

Maps

A map is something which associates elements from one set of things called keys to elements from another set of things called values. The general name for any such association is a relation. The important point about a map is that the relation is functional in that a key only ever associates to one value, i.e., it never appears twice in the relation (with different values).

Other names for a map are partial function (mathematics) associative list (computer science). Sometimes the term hash refers to a map, but hash connotes a specific implementation of a map which we'll see later.

Java uses the generic interface Map<K,V> as the basis of map implementations. The generic type K refers to the key type and V refers to the value type. The important member functions are these:
put(key,value)      add a key/value pair or replace value for existing key
get(key)            retrieve value for a given key (null if no such key)        
Like the Set interface, the Map interface has stronger extensions: SortedMap<K,V> and NavigableMap<K,V>. Also like sets, there are three Map implementation classes of interest to us:

Map Demo Program

Create a new project, MapDemo, as usual, and make this the starter main class:
demo.MapDemo  
Use each of the top three lines to see any differences in the outcomes.
    Map<String, Integer> people = new TreeMap<>();
//    Map<String, Integer> people = new HashMap<>();
//    Map<String, Integer> people = new LinkedHashMap<>();
Some points to make about the Map operations:
  1. You can have null values, which, unfortunately, can obfuscate the interpretation of the return values of put, get, and remove.
  2. The put(key,value) operation either adds a new (key,value) pair or resets the value. It returns the old value, or null if the key pair was newly added. If null values are permitted then we cannot use the return value as a determination of successful addition.
  3. The get(key) operation returns the associated value and null if the key does not exist. If null values are permitted, then we need to use the boolean containsKey(key) operation to tell for sure if a key is present.
  4. The remove(key) operations removes an existing (key,value) pair and returns the value. If the key is not found then null is returned. Similar to the situation with put, if null values are permitted then we cannot use the return value as a determination of successful deletion.
  5. The functions keySet (returning a Set) and values (returning a Collection) allow you to separate keys and values of a Map.
  6. You can iterate over a Map using on either the keys or the entries themselves. If both keys and values are desired, it is more efficient to iterate over the entries (an O(n) operation) than the by using the keys and retrieving the values (an O(n*log(n)) operation in TreeSets).

A Map is more general than a Set

A map can be used to implement a set. Java actually does this implicitly while other languages like Php, Perl, etc. require that you do so explicitly. For example, think of implementing
Set<String> s = ....
by
Map<String,Integer> m = ...
To say the set contains the strings:
"politics", "beer", "afterlife", "theater"
translates into the presence of these pairs in the map:
("politics",1), ("beer",1), ("afterlife",1), ("theater",1)
The crucial thing is that an element which is in the set appears with a non-null value in the corresponding map. The translation of operations is this using the boolean stat variable:
Set                               Map
---                               ---
stat = s.contains(some_string)    stat = m.containsKey(some_string)
stat = s.add(some_string)         stat = (m.put(some_string,1) == null)
stat = s.remove(some_string)      stat = (m.remove(some_string) != null)
In particular, the non-null values returned by get, put, and remove can be interpreted as the presence of a key element.

TreeMap Implemementation

Our implementation of a TreeMap is similar to that of a SearchTreeSet. The only difference is that the nodes hold a (key,value) pair instead of single data value. A key, which can occur only once in the tree takes on the role of the element in TreeSet. In the binary tree implementation, we maintain the following ordering property at each node:
keys of all
nodes in the
left subtree
of node n
< key at
node n
< keys of all
nodes in the
right subtree
of node n

Support and Implementation Classes

  1. The SetAdapter class used previously:
    adapter.SetAdapter  
  2. A new class, the MapAdapter:
    adapter.MapAdapter  
  3. For the navigable properties of the Trees, we need:
    adapter.NavMapAdapter  
  4. Finally, the implementation class:
    util.SearchTreeMap  

Test this implementation

Once these are installed you can use the MapDemo program above to do a (partial) test by using this definition of the people map:
    Map<String, Integer> people = new SearchTreeMap<>();
The issue is that the SearchTreeMap implementation does not implement the remove function, and so you will get an UnsupportedOperationException thrown for its usage.

SearchTreeMap Details

It's useful to compare what we're doing here with the SearchTreeSet class discussion in the TreeSets document. The SearchTreeMap nodes are defined by this inner class:
private static class Node<K,V> {
  K key;
  V value;
  Node<K,V> left, right;
 
  Node(K key, V value, Node<K,V> left, Node<K,V> right) {
    this.key = key;
    this.value = value;
    this.left = left;
    this.right = right;
  }
}
In particular SearchTreeMap nodes contains (key,value) pairs as opposed to SearchTreeSet nodes which contain only data values. The SearchTreeMap data members are the same as in SearchTreeSet:
private Node<K,V> root = null;
private int size = 0;
private Comparator<? super E> cmp = null;
The Map-based put function replaces the Set-based add function.
private Node<K,V> search(Node<K,V> n, K key) {
  if (n == null) {
    return null;
  }
  int comp = myCompare(key, n.key);
  if (comp < 0) {
    return search(n.left, key);
  }
  if (comp > 0) {
    return search(n.right, key);
  }
  return n;
}
 
@Override
public V get(Object obj) {
  K key = (K) obj;
  Node<K,V> n = search(root, key);
  if (n == null) {
    return null;
  }
  return n.value;
}
 
@Override
public boolean containsKey(Object obj){
  K key = (K) obj;
  return search(root, key) != null;
}
 
private Node<K,V> put(Node<K,V> n, K key, V value) {
  if (n == null) {
    return new Node<>(key, value, null, null);
  }
  int comp = myCompare(key, n.key);
  if (comp < 0) {
    n.left = put(n.left, key, value);
    return n;
  }
  if (comp > 0) {
    n.right = put(n.right, key, value);
    return n;
  }
  // we will never reach here based on the usage in public put
  // if we did, there would be no way to send back the "old value"
  return n;
}
 
@Override
public V put(K key, V value) {
  Node<K,V> n = search(root, key);
  if (n == null) {                  // key was not in tree
    root = put(root, key, value);   // we must add it
    ++size;           
    return null;
  }
  else {  // key was in tree, we replaced value
    V old_value = n.value;
    n.value = value;
    return old_value;  // return the old value
  }
}

HashMaps

The HashMap and LinkedHashMap follow the same structure as HashSet and LinkedHashSet. Start with this simple main function in the MapDemo class.
demo.RegularLinkedHashMaps  

Implementation

The user-defined OpenHashMap is an open-hashing implementation of the Map interface defining the most basic functions in the spirit of the OpenHashSet used in the HashSets document.
util.OpenHashMap  
You can use the MapDemo program above to do a (partial) test by using this definition of the people map:
    Map<String, Integer> people = new OpenHashMap<>();
The issue is that in that the keySet and other functions are not implemented.

Internal Structure

The internal structure is and code is pretty much like what was used for the HashSet class. The major difference being the Node class in which keys taking the place of set elements and each key has an associated value.
private static class Node<K,V> {
  K key;
  V value;
  Node<K,V> next;
  Node(K key, V value, Node<K,V> next) {
    this.key = key;
    this.value = value;
    this.next = next;
  }
}
For example, using the key/value pairs entered in the demo function,
(fashion,5),  (radio,17),    (technology,7),  (television,10),
(movies,8),   (business,3),  (wine,15),       (science,11)
A depiction of the internal structure using our implementation would be this:
Underlying our public functions is the search helper function which locates the correct pointer in the node chain for a given key (or null if not found).
private static Node<K,V> search(Object obj) {
  int num = hash(obj);
  Node<K,V> n = bucket[num];
  while (n != null) {
    if (n.key.equals(obj)) {
      break;
    } 
    n = n.next;
  }
  return n;
}
The public put(key,value) operation adds a new key/value pair if the key doesn't exist. If the key does exist, the old value is replaced by the new one.
public V put(K key, V value) {
  Node<K,V> foundAt = search(key);
 
  if (foundAt != null) {
    V old_value =  foundAt.value;
    foundAt.value = value;
    return old_value;
  } 
  else {
    ++size;
    float load = (float) size / capacity;
 
    if (load > loadFactor) {
      rehash();
    }
    int num = hash(key);
    bucket[num] = new Node<>(key, value, bucket[num]);
    return null;
  }
}
The get function is simpler:
public V get(Object obj) {
  Node<K,V> foundAt = search(obj);
  if (foundAt != null) {
    return foundAt.value;
  } 
  else {
    return null;
  }
}


© Robert M. Kline