Associative array

Associative array #

An associative array (or dictionary or map) simulates a function with finite domain.

A associative array exposes at least the following methods:

  • lookup (or get) takes a key as input, and returns the value for this key (if any).
  • insert (or put) inserts a pair (key, value). If an entry for this key was already present, then overwrites its value.
  • remove (or delete) deletes the entry for a given key (if any).

Note. Associative arrays are pervasive in programming. Many data structures have been designed over the years whose main purpose is to implement associative arrays efficiently (notably hash maps and a variety of search trees).

in Java #

Java provides an interface Map with 19 native implementations (i.e. 19 different classes that implement this interface). The most commonly used is HashMap.

Note. The interface Map does not extend the interface Collection.

Map is a parameterized type with two parameters: one for the type of its keys, and one for the type of its values. For instance, a map from integers to strings has type Map<Integer, String>.

Syntax #

Here are code snippets for a few operations specified in the interface Map.

  • Create a Map and populate it:
City milan = new City("Milan", 20100);
City florence = new City("Florence", 50100);

// Create an empty map whose keys are zipCodes,
// and whose values are cities
Map<Integer, City> zipCodeToCity = new HashMap<>();

// Adds { 20100 ↦ milan } to the map
zipCodeToCity.put(milan.zipCode, milan);

// Adds { 50100 ↦ florence } to the map
zipCodeToCity.put(florence.zipCode, florence);

// Creates a map identical to the previous one,
// but which cannot be modified
Map<Integer, City> anotherMap = Map.of( milan.zipCode, milan,
                                        florence.zipCode, florence );
  • Retrieve the value associated to a given key:
// Contains (a reference to) Milan
City aCity = zipCodeToCity.get(20100);

// Has value null
City anotherCity = zipCodeToCity.get(88888);
  • Check whether a map contains an entry for a given key:
// Outputs true
System.out.println(zipCodeToCity.containsKey(20100));

// Outputs false
System.out.println(zipCodeToCity.containsKey(88888));
  • Retrieve the number of entries in a map:
// Outputs 2
System.out.println(zipCodeToCity.size());
  • Overwrite an entry in a map:
City bologna = new City("Bologna", 40100);

// Replaces { 20100 ↦ milan } with { 20100 ↦ bologna }
zipCodeToCity.put(20100, bologna);

// Outputs 2
System.out.println(zipCodeToCity.size());

// Adds { 40100 ↦ bologna } to the map
zipCodeToCity.put(bologna.zipCode, bologna);

// Outputs 3
System.out.println(zipCodeToCity.size());

// Replaces { 20100 ↦ bologna } with { 20100 ↦ milan }
zipCodeToCity.put(milan.zipCode, milan);
  • Retrieve the set of keys of a map (note that this is an instance of Set<E>, where E is the type of the keys)
Set<Integer> keys = zipCodeToCity.keySet();

// Outputs true
System.out.println(keys.contains(20100));
  • Retrieve a collection with all values in the map, in no specific order (may contain duplicates):
Collection<City> values = zipCodeToCity.values();

// Outputs true
System.out.println(values.contains(milan));

// Outputs 3
System.out.println(values.size());

// Adds { 99999 ↦ milan } to the map
zipCodeToCity.put(99999, milan);

// Outputs 4
System.out.println(zipCodeToCity.values().size());
  • Wrap the map into a set of entries (a.k.a. “key-value” pairs):
// Creates a "wrapper" Set around the map.
// No data is duplicated.
// Each element of this set has type Entry<Integer,City>
Set<Entry<Integer,City>> entries = zipCodeToCity.entrySet();

// Iterates over entries
for (Entry<Integer, City> entry : entries){
    // Holds the entry's key
    Integer zipCode = entry.getKey();
    // Holds the entry's value
    City city = entry.getValue();
}

Again, we refer to the Javadoc for an exhaustive documentation.

Comparing keys #

The identity of two keys in Java is determined by the method equals, analogously to what we saw already for the identity of two elements in a set.

For instance, consider once again the classes City and SmartCity that we used in the section on sets, where SmartCity overrides equals (and hashCode), whereas City does not:

City trento = new City("Trento", 38100);
City trentoAgain = new City("Trento", 38100);
Country italy = new Country("Italy");

Map<City, Country> cityToCountry = new HashMap();
cityToCountry.put(trento, italy);
cityToCountry.put(trentoAgain, italy);

// Outputs 2
System.out.println(cityToCountry.size());

SmartCity smartTrento = new SmartCity("Trento", 38100);
SmartCity smartTrentoAgain = new SmartCity("Trento", 38100);

Map<SmartCity, Country> smartCityToCountry = new HashMap();
smartCityToCountry.put(smartTrento, italy);
smartCityToCountry.put(smartTrentoAgain, italy);

// Outputs 1
System.out.println(smartCityToCountry.size());

Usage #

Write a Java method int countRepeatedChars(char[] chars) that takes as input an array of characters, and returns the number of characters that appear multiple times in this array.

For instance, for the input array [a,e,b,c,b,a,d,b], the method should return 2.

int countRepeatedChars(char[] chars) {

    // key: character
    // value: number of occurrences of this character
    Map<Character, Integer> charToOcc = computeCharToOccMap(chars);

    // return value
    int repeatedChars = 0;
    // count the number of entries in the map with a value > 1
    for (Integer occ  : charToOcc.values()){
        if(occ > 1){
            repeatedChars++;
        }
    }
    return repeatedChars;
}

/**
* Auxiliary method.
*
* Returns a map that associates each character to its number of occurrences
*/
private Map<Character, Integer> computeCharToOccMap(char[] chars) {

    // create an empty map
    Map<Character, Integer> charToOcc = new HashMap<>();

    // for each character in the input array
    for (char character : chars) {
        // retrieve the number of occurrences seen so far for this character
        Integer occ = charToOcc.get(character);
        // increment this number by 1
        occ = (occ == null) ? 1 : occ + 1;
        // update the map for this character
        charToOcc.put(character, occ);
    }
    return charToOcc;
}

Consider the implementation of our game that we used previously in our exercise with sets. Assume in addition that the class Unit has an attribute color of type String.

Write a (Java) method void printNumberOfUnitsByColor(Unit[][] board) that takes a board as input, and prints the number of unit of each color, in any order.

For instance, for the board below:

The method could print:

blue: 1
yellow: 2
red: 2
void printNumberOfUnitsByColor(Unit[][] board) {

    // key: a color
    // value: the set of all units with this color
    Map<String, Set<Unit>> colorToUnits = new HashMap<>();

    for (Unit[] row : board) {
        for (Unit unit : row) {
            if (unit != null) {
                updateMap(unit, colorToUnits);
            }
        }
    }
    // for each entry in the map
    for (Entry<String, Set<Unit>> entry : colorToUnits.entrySet()) {
        // print the color and the number of units
        System.out.println(
            entry.getKey() + ": " + entry.getValue().size()
        );
    }
}

/**
 * Auxiliary method
 */
private void updateMap(Unit unit, Map<String,Set<Unit>> colorToUnits){

    // retrieve the set of units seen so for the color
    // of the current unit
    Set<Unit> units = colorToUnits.get(unit.color);
    if (units == null) {
        // if this is the first unit seen with this color,
        // then create an entry (in the map) for this color
        units = new HashSet<>();
        colorToUnits.put(unit.color, units);
    }
    units.add(unit);
}