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 interfaceCollection
.
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>
, whereE
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);
}