Scientific Programming II

ModSim

Maps

In computer science, an associative array/dictionary/Map is a data structure represented by a collection of key/value pairs. Arrays, like int[] or String[] can be thought of as a Map with only increasing integer keys. Maps are very widely used in the real world, such as associating a username with a password or an ID number with a database entry.

According to Wikipedia,

The operations that are usually defined for an associative array are:

• Add or insert: add a new (key, value) pair to the collection, binding the new key to its new value. The arguments to this operation are the key and the value.
• Reassign: replace the value in one of the (key, value) pairs that are already in the collection, binding an old key to a new value. As with an insertion, the arguments to this operation are the key and the value.
• Remove or delete: remove a (key, value) pair from the collection, unbinding a given key from its value. The argument to this operation is the key.
• Lookup: find the value (if any) that is bound to a given key. The argument to this operation is the key, and the value is returned from the operation. If no value is found, some associative array implementations raise an exception.

We will explore a simple implementation of a Map, which while not very efficient, is very easy to understand and implement. It should have the following methods at minimum:

• public void set(K key, V val) - Add a key-value pair to the Map
• public V get(K key) - Get the value associated with a key
• public void updateValueForKey(K key, V val) - Update the value associated with a key
• public String toString() - Convert the Map to a String