Two different objects may share a hash: a collision, and it is normal
The same fields
Objects.hash(titulo, autor, paginas)
record
record Libro(String titulo, String autor, int paginas)
Correct equals, hashCode and toString, generated by the compiler
equals without hashCodeequals(Libro o) instead of equals(Object o)compareTo returning a - b== to compare StringMutating an object stored in a HashSetremove inside a for-eachcompareTo inconsistent with equals
1 Step
Immutable Libro
titulo Β· autor Β· paginas
2 Step
equals + hashCode
Over the three fields
3 Step
Comparable
Natural order by title
4 Step
HashSet
Discards the duplicate
5 Step
Comparator
Three different orders
6 Step
TreeSet
The compareTo trap
Consistency
compareTo returns 0 exactly when equals returns true
1 Β· for-each = Iterator2 Β· CME is not about threads3 Β· removeIf Β· it.remove()4 Β· Comparable vs Comparator5 Β· compareTo: only the sign6 Β· equals + hashCode together7 Β· equals(Object o)8 Β· TreeSet decides with compareTo9 Β· record gives it for free
First debt: what hides behind the for-each and why ConcurrentModificationException is thrown.
Second: how to sort a collection of your own objects with Comparable and Comparator.
Third: why a HashSet sometimes keeps duplicates.
Three debts from the previous lesson
First debt: what hides behind the for-each and why ConcurrentModificationException is thrown. Second: how to sort a collection of your own objects with Comparable and Comparator. Third: why a HashSet sometimes keeps duplicates.
All three share one root: collections ask your objects questions.
If your objects answer wrongly, everything fails silently: no exceptions, no warnings.
The same root
All three share one root: collections ask your objects questions. If your objects answer wrongly, everything fails silently: no exceptions, no warnings.
The for-each you have used since the arrays lesson is syntactic sugar.
The compiler translates it into an Iterator and a while.
The for-each is syntactic sugar
The for-each you have used since the arrays lesson is syntactic sugar. The compiler translates it into an Iterator and a while.
ForEach.javajava
for(String nombre : nombres){System.out.println(nombre);}// what the compiler generates:Iterator<String> it = nombres.iterator();while(it.hasNext()){String nombre = it.next();System.out.println(nombre);}
An Iterator is an object with just three methods: hasNext(), next() and remove().
It works with for-each only if it implements Iterable, which requires one method: iterator().
An Iterator has three methods
An Iterator is an object with just three methods: hasNext(), next() and remove(). It works with for-each only if it implements Iterable, which requires one method: iterator().
That is why ArrayList, HashSet and ArrayDeque are walked with the same syntax.
The for-each does not talk to the collection: it talks to its iterator.
The same syntax for everything
That is why ArrayList, HashSet and ArrayDeque are walked with the same syntax. The for-each does not talk to the collection: it talks to its iterator.
nombres.iterator() returns an object with a cursor that starts before the first element.
The cursor does not point at an element: it lives in the gap between two.
The iterator is created
nombres.iterator() returns an object with a cursor that starts before the first element. The cursor does not point at an element: it lives in the gap between two.
Before every iteration hasNext() is called: is there any element left to return?
next() returns the element right after the cursor and moves it forward one place.
That way, iteration after iteration, the cursor hops gap by gap to the end.
hasNext() and next()
Before every iteration hasNext() is called: is there any element left to return? next() returns the element right after the cursor and moves it forward one place. That way, iteration after iteration, the cursor hops gap by gap to the end.
With the cursor at the end, hasNext() returns false and the loop ends.
The third method, remove(), deletes the last element next() returned.
No more elements
With the cursor at the end, hasNext() returns false and the loop ends. The third method, remove(), deletes the last element next() returned.
This code looks reasonable, but it fails: it deletes from the list while the for-each walks it.
Let us see step by step what Java detects and why it complains.
Deleting inside the for-each
This code looks reasonable, but it fails: it deletes from the list while the for-each walks it. Let us see step by step what Java detects and why it complains.
Tareas.javajava
List<String> tareas =newArrayList<>(List.of("estudiar","descansar","practicar","leer"));for(String t : tareas){if(t.startsWith("d")){tareas.remove(t);// β ConcurrentModificationException}}
Terminalbash
java TareasException in thread "main" java.util.ConcurrentModificationException at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java)
The for-each creates an Iterator, which memorizes the listβs modCount: its change counter.
Today it is 0: the list has not been modified since the traversal began.
The iterator memorizes modCount
The for-each creates an Iterator, which memorizes the listβs modCount: its change counter. Today it is 0: the list has not been modified since the traversal began.
The loop reaches βdescansarβ and calls tareas.remove(t): the list changes behind the iteratorβs back.
Its modCount becomes 1, but the iterator still remembers 0.
On the next iteration next() compares the counters: they differ and it throws ConcurrentModificationException.
The list changes from outside
The loop reaches βdescansarβ and calls tareas.remove(t): the list changes behind the iteratorβs back. Its modCount becomes 1, but the iterator still remembers 0. On the next iteration next() compares the counters: they differ and it throws ConcurrentModificationException.
The first correct way is to delete through the iterator itself: it.remove().
The loop advances with next() up to βdescansarβ, the element to delete.
Deleting with the iterator itself
The first correct way is to delete through the iterator itself: it.remove(). The loop advances with next() up to βdescansarβ, the element to delete.
it.remove() deletes the last returned element and updates the iteratorβs counter.
List and iterator now agree on modCount = 1: the traversal is still valid.
The elements shift left and the cursor keeps going without skipping any.
it.remove() keeps everything in sync
it.remove() deletes the last returned element and updates the iteratorβs counter. List and iterator now agree on modCount = 1: the traversal is still valid. The elements shift left and the cursor keeps going without skipping any.
The two correct ways: it.remove() with an explicit iterator, or removeIf.
removeIf exists since Java 8 and is the one you will use 95 % of the time.
The two correct ways
The two correct ways: it.remove() with an explicit iterator, or removeIf. removeIf exists since Java 8 and is the one you will use 95 % of the time.
Tareas.javajava
// Option 1: the explicit iteratorIterator<String> it = tareas.iterator();while(it.hasNext()){if(it.next().startsWith("d")){it.remove();// deletes AND stays consistent}}// Option 2: removeIf β since Java 8tareas.removeIf(t -> t.startsWith("d"));
The name is misleading: it has nothing to do with threads or concurrency.
It happens the same in a single-threaded program: the list changed during the traversal.
The exception protects you from walking a structure that changed under your feet.
It has nothing to do with threads
The name is misleading: it has nothing to do with threads or concurrency. It happens the same in a single-threaded program: the list changed during the traversal. The exception protects you from walking a structure that changed under your feet.
If you sort a list of your own objects, Java stops you: Libro is not Comparable.
And it is right: sort by what? Title, author, pages, year? It cannot guess.
Java cannot sort your objects
If you sort a list of your own objects, Java stops you: Libro is not Comparable. And it is right: sort by what? Title, author, pages, year? It cannot guess.
Libros.javajava
List<Libro> libros =newArrayList<>();Collections.sort(libros);// ERROR: Libro is not Comparable
Terminalbash
javac Libros.javaLibros.java:9: error: no suitable method found for sort(List<Libro>)
Comparable defines the natural order: the one that makes sense when nobody asks for another.
a.compareTo(b) negative: a goes first. Zero: equivalent. Positive: a goes after.
The exact value does not matter: only the sign does.
What compareTo returns
Comparable defines the natural order: the one that makes sense when nobody asks for another. a.compareTo(b) negative: a goes first. Zero: equivalent. Positive: a goes after. The exact value does not matter: only the sign does.
You implement Comparable<Libro> and write compareTo: here the natural order is by title.
With that, Collections.sort, TreeSet, TreeMap and Arrays.sort just work.
Implementing Comparable
You implement Comparable<Libro> and write compareTo: here the natural order is by title. With that, Collections.sort, TreeSet, TreeMap and Arrays.sort just work.
Libro.javajava
publicclassLibroimplementsComparable<Libro>{privatefinalString titulo;privatefinalString autor;privatefinalint paginas;@OverridepublicintcompareTo(Libro otro){returnthis.titulo.compareTo(otro.titulo);// natural order: by title}}
The classic trap: returning this.edad - otro.edad. With large values the subtraction overflows the int.
The sign comes out wrong and the list ends up misordered, with no exception at all.
Always use Integer.compare(a, b).
The subtraction trap
The classic trap: returning this.edad - otro.edad. With large values the subtraction overflows the int. The sign comes out wrong and the list ends up misordered, with no exception at all. Always use Integer.compare(a, b).
Persona.javajava
// Classic trap: the subtraction can overflow the intreturnthis.edad - otro.edad;// Always like this:returnInteger.compare(this.edad, otro.edad);
Comparable has a limit: you can only have one natural order per class.
And what if sometimes you want to sort by pages and other times by author?
That is what Comparator is for: an order that lives outside the class. You can have as many as you like.
One natural order, many comparators
Comparable has a limit: you can only have one natural order per class. And what if sometimes you want to sort by pages and other times by author? That is what Comparator is for: an order that lives outside the class. You can have as many as you like.
Four books in the order they were loaded: nothing guarantees they are sorted.
An unsorted list
Four books in the order they were loaded: nothing guarantees they are sorted.
Collections.sort(libros) uses compareTo: it compares pairs and relocates the books by title.
Result: 1984, El Aleph, Ficciones, Rayuela.
Natural order: by title
Collections.sort(libros) uses compareTo: it compares pairs and relocates the books by title. Result: 1984, El Aleph, Ficciones, Rayuela.
With a Comparator the order lives outside: comparingInt(Libro::getPaginas).reversed().
You did not touch the Libro class: the same objects, another criterion.
Comparator by pages, descending
With a Comparator the order lives outside: comparingInt(Libro::getPaginas).reversed(). You did not touch the Libro class: the same objects, another criterion.
thenComparing chains criteria: the author first and, on a tie, the title.
Borges appears twice: El Aleph and Ficciones are tie-broken by title.
sort orders the original list in place: if you want to keep the order, copy it first.
By author and, on a tie, by title
thenComparing chains criteria: the author first and, on a tie, the title. Borges appears twice: El Aleph and Ficciones are tie-broken by title. sort orders the original list in place: if you want to keep the order, copy it first.
The most used comparators: by field, reversed and chained with thenComparing.
With nullsLast the null values go last without the sort blowing up.
A Comparator works even for classes you did not write and cannot modify.
The comparators you will use most
The most used comparators: by field, reversed and chained with thenComparing. With nullsLast the null values go last without the sort blowing up. A Comparator works even for classes you did not write and cannot modify.
Orden.javajava
// Sort by pages, ascendinglibros.sort(Comparator.comparingInt(Libro::getPaginas));// Descendinglibros.sort(Comparator.comparingInt(Libro::getPaginas).reversed());// By author and, on a tie, by titlelibros.sort(Comparator.comparing(Libro::getAutor).thenComparing(Libro::getTitulo));// Nulls last, without blowing uplibros.sort(Comparator.comparing(Libro::getAutor,Comparator.nullsLast(Comparator.naturalOrder())));
a and b are two different objects on the Heap, even with exactly the same data.
The == operator compares references: it does not ask what the objects contain.
Two equal books, two objects
a and b are two different objects on the Heap, even with exactly the same data. The == operator compares references: it does not ask what the objects contain.
Object.equals() compares references too: it is true only for literally the same object.
For almost any domain class that is wrong: a.equals(b) should be true.
Default equals()
Object.equals() compares references too: it is true only for literally the same object. For almost any domain class that is wrong: a.equals(b) should be true.
Once equals is overridden, the comparison is by content: title, author and pages.
When every field matches, a.equals(b) returns true.
Overridden equals() compares fields
Once equals is overridden, the comparison is by content: title, author and pages. When every field matches, a.equals(b) returns true.
Overriding equals means signing a contract with five clauses.
Reflexive, symmetric and transitive: a equals itself, and equality goes both ways and chains.
Consistent: the same result if nothing changed. And against null: always false, never an exception.
The five rules of the contract
Overriding equals means signing a contract with five clauses. Reflexive, symmetric and transitive: a equals itself, and equality goes both ways and chains. Consistent: the same result if nothing changed. And against null: always false, never an exception.
The skeleton: shortcut for the same object, false for null or another class, then the fields.
Objects.equals tolerates null on both sides, and the parameter is Object o.
A correct equals
The skeleton: shortcut for the same object, false for null or another class, then the fields. Objects.equals tolerates null on both sides, and the parameter is Object o.
Libro.javajava
@Overridepublicbooleanequals(Object o){if(this== o)returntrue;// shortcut: same objectif(o ==null||getClass()!= o.getClass())returnfalse;Libro otro =(Libro) o;return paginas == otro.paginas&&Objects.equals(titulo, otro.titulo)// tolerates null on both sides&&Objects.equals(autor, otro.autor);}
If you write equals(Libro o) you are overloading, not overriding.
Collections call equals(Object) and keep using the comparison by reference.
@Override catches this mistake at compile time: always use it.
equals(Libro) is not equals(Object)
If you write equals(Libro o) you are overloading, not overriding. Collections call equals(Object) and keep using the comparison by reference. @Override catches this mistake at compile time: always use it.
Libro.javajava
// Overload: collections do NOT use itpublicbooleanequals(Libro o){...}// Override: the correct one@Overridepublicbooleanequals(Object o){...}
A HashSet does not scan everything comparing: first it computes which bucket each object goes in.
Only inside that bucket does it use equals() to check whether an equal one is already there.
The HashSet computes a bucket
A HashSet does not scan everything comparing: first it computes which bucket each object goes in. Only inside that bucket does it use equals() to check whether an equal one is already there.
Here equals() is written correctly, but hashCode() is still inherited from Object.
Each book yields a different hash and lands in another bucket: 2 and 11.
equals() never even ran: the Set holds two equal books.
equals() yes, hashCode() no
Here equals() is written correctly, but hashCode() is still inherited from Object. Each book yields a different hash and lands in another bucket: 2 and 11. equals() never even ran: the Set holds two equal books.
With hashCode() overridden, two equal books produce the same hash.
They land in the same bucket: now the Set does run equals().
equals() is true, add returns false and the duplicate is discarded.
With hashCode overridden
With hashCode() overridden, two equal books produce the same hash. They land in the same bucket: now the Set does run equals(). equals() is true, add returns false and the duplicate is discarded.
If you modify an object already stored in a HashSet, its hashCode changes.
It stays in the old bucket, but the lookup now checks the new one.
contains() is false for an object that is inside. Use immutable elements.
An object that changes after being stored
If you modify an object already stored in a HashSet, its hashCode changes. It stays in the old bucket, but the lookup now checks the new one. contains() is false for an object that is inside. Use immutable elements.
The rule is absolute: if a.equals(b) is true, both hashCode values must be equal.
The reverse is not required: two different objects can share a hashCode. That is a collision and it is normal.
The rule is absolute
The rule is absolute: if a.equals(b) is true, both hashCode values must be equal. The reverse is not required: two different objects can share a hashCode. That is a collision and it is normal.
If you override equals, override hashCode with Objects.hash(...).
Use the same fields in both: if hashCode uses one that equals ignores, the contract breaks.
hashCode with the same fields
If you override equals, override hashCode with Objects.hash(...). Use the same fields in both: if hashCode uses one that equals ignores, the contract breaks.
Libro.javajava
@OverridepublicinthashCode(){returnObjects.hash(titulo, autor, paginas);// the SAME fields as equals}
If your class only carries data, a record generates correct equals, hashCode and toString.
Three lines and the compiler guarantees the contract for you.
The shortcut: record
If your class only carries data, a record generates correct equals, hashCode and toString. Three lines and the compiler guarantees the contract for you.
Overriding equals but not hashCode: HashSets keep duplicates and get() returns null.
Writing equals(Libro o) instead of equals(Object o): it is an overload and goes unused.
Returning a - b in compareTo, or comparing String with ==.
Common mistakes (1 of 2)
Overriding equals but not hashCode: HashSets keep duplicates and get() returns null. Writing equals(Libro o) instead of equals(Object o): it is an overload and goes unused. Returning a - b in compareTo, or comparing String with ==.
Modifying an object already stored in a HashSet: its hash changes and contains() loses it.
Deleting with lista.remove(x) inside a for-each: use removeIf or iterator.remove().
And a compareTo inconsistent with equals: the TreeSet drops elements without warning.
Common mistakes (2 of 2)
Modifying an object already stored in a HashSet: its hash changes and contains() loses it. Deleting with lista.remove(x) inside a for-each: use removeIf or iterator.remove(). And a compareTo inconsistent with equals: the TreeSet drops elements without warning.
The guided challenge: a Libro class with title, author and pages, all immutable.
Six steps: equals, hashCode, Comparable, a HashSet, several sorts and a TreeSet.
The challenge: the Libro class
The guided challenge: a Libro class with title, author and pages, all immutable. Six steps: equals, hashCode, Comparable, a HashSet, several sorts and a TreeSet.
Steps 1 to 3: immutable fields, equals and hashCode over the three fields, and natural order by title.
With this, two identical books are equal and share the same hash.
equals, hashCode and compareTo
Steps 1 to 3: immutable fields, equals and hashCode over the three fields, and natural order by title. With this, two identical books are equal and share the same hash.
Libro.javajava
publicfinalclassLibroimplementsComparable<Libro>{privatefinalString titulo;privatefinalString autor;privatefinalint paginas;@Overridepublicbooleanequals(Object o){if(this== o)returntrue;if(o ==null||getClass()!= o.getClass())returnfalse;Libro otro =(Libro) o;return paginas == otro.paginas&&Objects.equals(titulo, otro.titulo)&&Objects.equals(autor, otro.autor);}@OverridepublicinthashCode(){returnObjects.hash(titulo, autor, paginas);// the same three fields}@OverridepublicintcompareTo(Libro otro){returnthis.titulo.compareTo(otro.titulo);// natural order: by title}}
Step 4: a == b is false, a.equals(b) is true and the HashSet discards the duplicate.
Step 5: you sort the list by the natural order and with three different Comparators.
Trying the HashSet and the sorts
Step 4: a == b is false, a.equals(b) is true and the HashSet discards the duplicate. Step 5: you sort the list by the natural order and with three different Comparators.
Point 6 of the challenge: a TreeSet whose compareTo only looks at the title.
It already holds β1984β by Orwell. We try to add another book titled β1984β.
The TreeSet trap
Point 6 of the challenge: a TreeSet whose compareTo only looks at the title. It already holds β1984β by Orwell. We try to add another book titled β1984β.
equals considers it different: the author and the pages change.
But the TreeSet ignores equals: it decides duplicates with compareTo == 0.
Result: the book vanishes with no error, no exception and no warning.
compareTo == 0 means duplicate
equals considers it different: the author and the pages change. But the TreeSet ignores equals: it decides duplicates with compareTo == 0. Result: the book vanishes with no error, no exception and no warning.
The fix: make compareTo return 0 exactly when equals returns true.
Compare title, then author, then pages, always with Integer.compare.
A compareTo consistent with equals
The fix: make compareTo return 0 exactly when equals returns true. Compare title, then author, then pages, always with Integer.compare.
Libro.javajava
@OverridepublicintcompareTo(Libro otro){int porTitulo =this.titulo.compareTo(otro.titulo);if(porTitulo !=0)return porTitulo;int porAutor =Objects.compare(this.autor, otro.autor,Comparator.nullsFirst(Comparator.naturalOrder()));if(porAutor !=0)return porAutor;returnInteger.compare(this.paginas, otro.paginas);// never the subtraction}
The for-each uses an Iterator; to delete while walking, use removeIf or iterator.remove().
Comparable is one natural order; Comparator, many. In compareTo only the sign matters.
Takeaways
The for-each uses an Iterator; to delete while walking, use removeIf or iterator.remove(). Comparable is one natural order; Comparator, many. In compareTo only the sign matters.
If you override equals, override hashCode with the same fields and the equals(Object o) signature.
TreeSet and TreeMap ignore equals and decide with compareTo. A record solves it for free.
The contract in one line
If you override equals, override hashCode with the same fields and the equals(Object o) signature. TreeSet and TreeMap ignore equals and decide with compareTo. A record solves it for free.
Reinforce the lesson with complete, runnable programs in the course repository.
Clone it and run each program while you read to see every concept in action.
Go deeper with real code
Reinforce the lesson with complete, runnable programs in the course repository. Clone it and run each program while you read to see every concept in action.