UF 06: JAVA¶

Sets and Maps¶

Alta Formazione Professionale - ITT Marconi

March 2021

Set¶

  • mutable collection
  • unordered
  • distinct elements
  • elements should be immutable
  • Java interface: Set
  • main Java implementation: HashSet
In [1]:
Set<String> hset = new HashSet<String>();  // String: immutable elements
 
hset.add("platform");  // mutable collection
hset.add("rpg");
hset.add("strategy");
Out[1]:
true
In [2]:
System.out.println(hset);    // unordered collection

[rpg, strategy, platform]
In [3]:
for (String element : hset){     // unordered collection -> unpredictable order!
    System.out.println(element);
}

rpg
strategy
platform

hset.get(0)  // no order -> no way to get first element!

|   hset.get(0)
cannot find symbol
  symbol:   method get(int)
In [4]:
hset.add("beat'em up");
Out[4]:
true
In [5]:
hset.add("beat'em up");   // distinct elements -> duplicates are silently discarded
Out[5]:
false
In [6]:
hset.remove("strategy");
Out[6]:
true
In [7]:
hset.remove("strategy");  // removals fail silently
Out[7]:
false
In [8]:
System.out.println(hset);  // no duplicates

[beat'em up, rpg, platform]

Search is constant time¶

-> does not depend on set size

In [9]:
hset.contains("rpg")   // super fast
Out[9]:
true

Victims of inequality¶

In [10]:
public class PoorMonster {
    
    // stuff that matters    
    public String name = "";
    public int lifepoints = 0;  
    
    //  Java rituals 
    
    @Override
    public String toString() {
        return "PoorMonster{" + "name=" + name + ", lifepoints=" + lifepoints + '}';
    }    
    
    // NO hashCode NOR equals !
}
In [11]:
PoorMonster poor1 = new PoorMonster();
poor1.name = "Mr Poor";
poor1.lifepoints = 1;

PoorMonster poor2 = new PoorMonster();
poor2.name = "Mr Poor";
poor2.lifepoints = 1;
Out[11]:
1
In [12]:
Set<PoorMonster> poorset = new HashSet<PoorMonster>();  

poorset.add(poor1);
poorset.add(poor1);

System.out.println(poorset);

[PoorMonster{name=Mr Poor, lifepoints=1}]
In [13]:
poorset.add(poor2);
Out[13]:
true
In [14]:
System.out.println(poorset);   // We've got duplicates !

[PoorMonster{name=Mr Poor, lifepoints=1}, PoorMonster{name=Mr Poor, lifepoints=1}]

All equal monsters should be equal¶

Using Monster defined as in classes slides

In [15]:
import java.util.Objects;

public class Monster {
    
    // stuff that matters    
    public String name = "";
    public int lifepoints = 0;    
    
    // Java rituals  ......................
    
    @Override
    public String toString() {
        return "Monster{" + "name=" + name + ", lifepoints=" + lifepoints + '}';
    }    
    @Override
    public int hashCode() {
        int hash = 3;
        hash = 89 * hash + Objects.hashCode(this.name);
        hash = 89 * hash + this.lifepoints;
        return hash;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Monster other = (Monster) obj;
        if (this.lifepoints != other.lifepoints) {
            return false;
        }
        if (!Objects.equals(this.name, other.name)) {
            return false;
        }
        return true;
    }        
}
In [16]:
Monster cerberus1 = new Monster();
cerberus1.name = "Cerberus";
cerberus1.lifepoints = 7;

Monster cerberus2 = new Monster();
cerberus2.name = "Cerberus";
cerberus2.lifepoints = 7;

Monster zombo = new Monster();
zombo.name = "Zombo";
zombo.lifepoints = 4;
Out[16]:
4
In [17]:
Set<Monster> mset = new HashSet<Monster>();
 
mset.add(cerberus1);
Out[17]:
true
In [18]:
System.out.println(mset)

[Monster{name=Cerberus, lifepoints=7}]
In [19]:
mset.add(cerberus2);
Out[19]:
false
In [20]:
System.out.println(mset)

[Monster{name=Cerberus, lifepoints=7}]
In [21]:
mset.add(zombo);
System.out.println(mset)

[Monster{name=Cerberus, lifepoints=7}, Monster{name=Zombo, lifepoints=4}]
In [22]:
mset.contains(cerberus1);
Out[22]:
true
In [23]:
mset.contains(cerberus2);
Out[23]:
true
In [24]:
mset.remove(cerberus1);
Out[24]:
true
In [25]:
mset.remove(cerberus2);  // silent fail
Out[25]:
false

Beware the mutant¶

mutant-goblin

In [26]:
Monster mutantGoblin1 = new Monster();
mutantGoblin1.name = "Mutant Goblin";
mutantGoblin1.lifepoints = 3;  // NOTE 3
Out[26]:
3
In [27]:
Monster mutantGoblin2 = new Monster();
mutantGoblin2.name = "Mutant Goblin";
mutantGoblin2.lifepoints = 5;  // NOTE 5
Out[27]:
5
In [28]:
System.out.println(mutantGoblin1);
System.out.println(mutantGoblin2);

Monster{name=Mutant Goblin, lifepoints=3}
Monster{name=Mutant Goblin, lifepoints=5}
In [29]:
Set<Monster> brokenSet = new HashSet<Monster>();

brokenSet.add(mutantGoblin1);
brokenSet.add(mutantGoblin2);

System.out.println(brokenSet);

[Monster{name=Mutant Goblin, lifepoints=3}, Monster{name=Mutant Goblin, lifepoints=5}]

So far so good but ....

In [30]:
mutantGoblin1.lifepoints = 5;    //  Watch out !
Out[30]:
5
In [31]:
System.out.println(brokenSet);

[Monster{name=Mutant Goblin, lifepoints=5}, Monster{name=Mutant Goblin, lifepoints=5}]

Very bad! We broke the set!

Sets: Take away¶

  • Never mutate an item in a Set
  • Elements in a Set SHOULD be immutable

If you really need to mutate an element:

  1. remove the element
  2. modify it
  3. readd

Keep things in order¶

  • LinkedHashSet: maintains insertion order
  • TreeSet: maintains order given by a Comparator

More info: see this link

Readings: MIT Mutability & Immutability

Maps¶

  • mutable collections
  • allow to rapidly associate elements called keys to some values

Keys:

  • (should be) immutable
  • unordered
  • there cannot be duplicates

-> keys behave like items of a set

Values:

  • can be anything
  • can be duplicated

Given a key, we can find the corresponding value very fast

In [32]:
Monster cerberus1 = new Monster();
cerberus1.name = "Cerberus";
cerberus1.lifepoints = 7;

Monster zombo = new Monster();
zombo.name = "Zombo";
zombo.lifepoints = 4;

Monster mutantBlob = new Monster();
mutantBlob.name = "Mutant Blob";
mutantBlob.lifepoints = 6;     // NOTE 2
Out[32]:
6
In [33]:
HashMap<String, Monster> castle = new HashMap();

castle.put("lab", cerberus1);
castle.put("pit", zombo);
castle.put("tower", mutantBlob);

System.out.println(castle);  // iteration is by keys, unpredictable order!

{pit=Monster{name=Zombo, lifepoints=4}, lab=Monster{name=Cerberus, lifepoints=7}, tower=Monster{name=Mutant Blob, lifepoints=6}}
In [34]:
for (String key : castle.keySet()){   // unpredictable order!
    System.out.println(key + ": " +  castle.get(key));    
}

pit: Monster{name=Zombo, lifepoints=4}
lab: Monster{name=Cerberus, lifepoints=7}
tower: Monster{name=Mutant Blob, lifepoints=6}

Search by key is constant time¶

-> does not depend on map size!

In [35]:
System.out.println(   castle.get("pit")  )   // very fast!

Monster{name=Zombo, lifepoints=4}
In [36]:
castle.put("pit", mutantBlob);  // silent key replacement
Out[36]:
Monster{name=Zombo, lifepoints=4}
In [37]:
System.out.println(castle);   // values can be duplicated

{pit=Monster{name=Mutant Blob, lifepoints=6}, lab=Monster{name=Cerberus, lifepoints=7}, tower=Monster{name=Mutant Blob, lifepoints=6}}
In [38]:
castle.get("pit").lifepoints = 900;   // mutating values is fine
Out[38]:
900
In [39]:
System.out.println(castle)      // even if we have more references to same object

{pit=Monster{name=Mutant Blob, lifepoints=900}, lab=Monster{name=Cerberus, lifepoints=7}, tower=Monster{name=Mutant Blob, lifepoints=900}}
In [40]:
System.out.println(  castle.get("playground")  )   // silent fail

null

What about mapping Monster to String?¶

We can!

In [41]:
HashMap<Monster, String> dungeon = new HashMap();

dungeon.put(cerberus1, "hall");
dungeon.put(zombo, "lab");

System.out.println(dungeon);

{Monster{name=Cerberus, lifepoints=7}=hall, Monster{name=Zombo, lifepoints=4}=lab}
In [42]:
dungeon.put(cerberus1, "corridor");  // we can reassign key/value
Out[42]:
hall
In [43]:
System.out.println(dungeon);

{Monster{name=Cerberus, lifepoints=7}=corridor, Monster{name=Zombo, lifepoints=4}=lab}
In [44]:
dungeon.put(cerberus2, "pit");  // if objects have equals() method, key will be replaced
Out[44]:
corridor
In [45]:
System.out.println(dungeon);

{Monster{name=Cerberus, lifepoints=7}=pit, Monster{name=Zombo, lifepoints=4}=lab}

Beware the poor key¶

poor-goblin

Remember poor monsters don't have .equals(Object) nor hashCode()

In [46]:
HashMap<PoorMonster, String> village = new HashMap();   // we inverted key/value types

PoorMonster beggarGoblin1 = new PoorMonster();
beggarGoblin1.name = "Beggar Goblin";
beggarGoblin1.lifepoints = 2;  

PoorMonster beggarGoblin2 = new PoorMonster();
beggarGoblin2.name = "Beggar Goblin";
beggarGoblin2.lifepoints = 2;
Out[46]:
2
In [47]:
village.put(beggarGoblin1, "street");  // works
System.out.println(village);

{PoorMonster{name=Beggar Goblin, lifepoints=2}=street}
In [48]:
village.put(beggarGoblin1, "market" );  // works, replaces key/value
System.out.println(village);

{PoorMonster{name=Beggar Goblin, lifepoints=2}=market}
In [49]:
village.put(beggarGoblin2, "jail");  // no .equals(Object) -> different keys!
System.out.println(village);

{PoorMonster{name=Beggar Goblin, lifepoints=2}=market, PoorMonster{name=Beggar Goblin, lifepoints=2}=jail}

Beware the mutant key¶

mutant-goblin

In [50]:
Monster zombo = new Monster();
zombo.name = "Zombo";
zombo.lifepoints = 4;

Monster mutantGoblin1 = new Monster();
mutantGoblin1.name = "Mutant Goblin";
mutantGoblin1.lifepoints = 3;  // NOTE 3

Monster mutantGoblin2 = new Monster();
mutantGoblin2.name = "Mutant Goblin";
mutantGoblin2.lifepoints = 5;  // NOTE 5
Out[50]:
5
In [51]:
HashMap<Monster, String> brokenMap = new HashMap();

brokenMap.put(mutantGoblin1, "torture room");
System.out.println(brokenMap);

{Monster{name=Mutant Goblin, lifepoints=3}=torture room}
In [52]:
brokenMap.put(mutantGoblin2, "jail" );
System.out.println(brokenMap);

{Monster{name=Mutant Goblin, lifepoints=3}=torture room, Monster{name=Mutant Goblin, lifepoints=5}=jail}
In [53]:
brokenMap.get(mutantGoblin1)
Out[53]:
torture room

Maps: Danger zone¶

In [54]:
mutantGoblin1.lifepoints = 5  // WARNING: we're mutating attributes of a key!!!
Out[54]:
5
In [55]:
System.out.println(brokenMap);

{Monster{name=Mutant Goblin, lifepoints=5}=torture room, Monster{name=Mutant Goblin, lifepoints=5}=jail}
  • Monster class has proper .equals(Object) and hashCode() methods...
  • ...yet we end up with two equal keys !!!