Java already ships it all
Later you will build lists, stacks and queues by hand to understand how they work. But day to day you do not need to: Java ships it all, tuned over thirty years.
You will build it by hand
TAD ListaTAD PilaTAD Cola In the next lessons, to see how they work inside
Java already ships it
ArrayListHashMapArrayDeque Thirty years of tuning and millions of applications
Using a tool is not the same as understanding it
Good: the type is the interface
List<String> nombres = new ArrayList<>(); Map<String, Integer> stock = new HashMap<>(); Bad: you tie yourself to the implementation
ArrayList<String> nombres = new ArrayList<>(); Switching to LinkedList means touching one word
List<String> nombres = new LinkedList<>(); entrySet()
for (Map.Entry<String, Integer> e : stock.entrySet()) Each entry carries getKey() and getValue()
merge
contador.merge(palabra, 1, Integer::sum); Counts frequencies with no if at all
getOrDefault
stock.getOrDefault("azúcar", 0) A default value instead of null
putIfAbsent
mapa.putIfAbsent(clave, valor); Stores only if the key is missing
computeIfAbsent
mapa.computeIfAbsent(k, x -> new ArrayList<>()).add(v); Builds a map of lists
ArrayDeque
Stack and queue
Inserts and removes at the ends in O(1)
PriorityQueue
The highest priority comes out
Not the one that arrived first
You will implement them by hand in ADT Stack and ADT Queue
Generic class
public class Caja<T> The type parameter goes between <> after the name
Generic method
public static <T> T primero(List<T> lista) Its own type parameter, before the return type
Bounded type
<T extends Comparable<T>> So you can safely call compareTo
By convention, one capital letter
T · type E · element K · key V · value R · result Generics exist only at compile time
List<String> == List<Integer> → List ArrayList ArrayDeque HashSet TreeSet HashMap TreeMap LinkedHashMap PriorityQueue 1 Step
Normalize the text
Lowercase, no punctuation
2 Step
Count with a Map
Map<String, Integer>
3 Step
Sort by frequency
Descending, then alphabetical
4 Step
Distinct words
The keys, as a Set
5 Step
Skip the stop words
de, la, el, y, que…
contains on VACIAS
Set · O(1) List · O(n)
Runnable programs for every section
Later you will build lists, stacks and queues by hand to understand how they work.
But day to day you do not need to: Java ships it all, tuned over thirty years.
Later you will build lists, stacks and queues by hand to understand how they work. But day to day you do not need to: Java ships it all, tuned over thirty years.
When someone says "use a HashMap", you will know there is an array and collisions.
That is the difference between using a tool and understanding it.
When someone says "use a HashMap", you will know there is an array and collisions. That is the difference between using a tool and understanding it.
The whole framework starts from a hierarchy of interfaces, not classes.
Iterable enables for-each and Collection holds loose elements.
The whole framework starts from a hierarchy of interfaces, not classes. Iterable enables for-each and Collection holds loose elements.
Three families hang from Collection: List, Set and Queue.
Each one is an interface: the contract, what you will later call an ADT.
Three families hang from Collection: List, Set and Queue. Each one is an interface: the contract, what you will later call an ADT.
The concrete classes are the implementations: ArrayList, HashSet, ArrayDeque…
Each one picks another structure inside: array, hash table, tree or nodes.
The concrete classes are the implementations: ArrayList, HashSet, ArrayDeque… Each one picks another structure inside: array, hash table, tree or nodes.
Map stays outside: it stores key → value associations, not loose elements.
That is why it does not extend Collection and has its own interface.
Map stays outside: it stores key → value associations, not loose elements. That is why it does not extend Collection and has its own interface.
The concrete rule: the variable’s type is the interface, not the implementation.
Switching to LinkedList means touching a single word.
The concrete rule: the variable’s type is the interface, not the implementation. Switching to LinkedList means touching a single word.
// Good: the variable's type is the interfaceList<String> nombres = new ArrayList<>();Map<String, Integer> stock = new HashMap<>(); If you declare ArrayList, anyone using an ArrayList-only method forces you to change it all.
It is the same principle as the ADT: program against the contract, not the detail.
If you declare ArrayList, anyone using an ArrayList-only method forces you to change it all. It is the same principle as the ADT: program against the contract, not the detail.
// Bad: you tie yourself to the implementationArrayList<String> nombres = new ArrayList<>(); Before Java 5 collections stored Object: everything went in and everything compiled.
You add a text and a number to the same list: it compiles perfectly.
The error only arrives at the cast: ClassCastException, at runtime and with users.
Before Java 5 collections stored Object: everything went in and everything compiled. You add a text and a number to the same list: it compiles perfectly. The error only arrives at the cast: ClassCastException, at runtime and with users.
With generics the collection declares what it stores: List<String>.
Adding a number does not even compile: the error shows in your IDE, before running.
And when reading, the cast disappears: the compiler already knows a String comes out.
With generics the collection declares what it stores: List<String>. Adding a number does not even compile: the error shows in your IDE, before running. And when reading, the cast disappears: the compiler already knows a String comes out.
The empty <> on the right is called the diamond.
It tells the compiler: the same type I declared on the left.
new ArrayList<String>() is not wrong, just redundant.
The empty <> on the right is called the diamond. It tells the compiler: the same type I declared on the left. new ArrayList<String>() is not wrong, just redundant.
List keeps insertion order and allows duplicates.
get(1) reads by index and size() counts everything, repeated ones included.
List keeps insertion order and allows duplicates. get(1) reads by index and size() counts everything, repeated ones included.
Set allows no duplicates: you add java, poo and java again.
The third java was already there: add ignores it and the size stays 2.
Set allows no duplicates: you add java, poo and java again. The third java was already there: add ignores it and the size stays 2.
HashSet guarantees no order; LinkedHashSet keeps it; TreeSet keeps everything sorted.
Careful: your own classes need equals() and hashCode() for the Set to detect duplicates.
HashSet guarantees no order; LinkedHashSet keeps it; TreeSet keeps everything sorted. Careful: your own classes need equals() and hashCode() for the Set to detect duplicates.
In an ArrayList, get(6) jumps straight there: one address calculation and done.
In a LinkedList you must follow the links, node by node, until you reach the 6th.
With 500 elements that is 500 hops: indexed access in a LinkedList is slow.
In an ArrayList, get(6) jumps straight there: one address calculation and done. In a LinkedList you must follow the links, node by node, until you reach the 6th. With 500 elements that is 500 hops: indexed access in a LinkedList is slow.
The elements of an ArrayList sit side by side in memory: the CPU cache loads them together.
The nodes of a LinkedList are scattered across the Heap: more cache misses.
That is why in practice LinkedList almost always loses: ArrayList, unless you measure otherwise.
The elements of an ArrayList sit side by side in memory: the CPU cache loads them together. The nodes of a LinkedList are scattered across the Heap: more cache misses. That is why in practice LinkedList almost always loses: ArrayList, unless you measure otherwise.
put(key, value) stores an association: the key points to its value.
First yerba → 12 and then café → 5: two entries.
If you repeat a key, put overwrites it: keys are unique.
put(key, value) stores an association: the key points to its value. First yerba → 12 and then café → 5: two entries. If you repeat a key, put overwrites it: keys are unique.
get("yerba") looks up the key and returns its value: 20.
get("azúcar") finds no such key and returns null.
get("yerba") looks up the key and returns its value: 20. get("azúcar") finds no such key and returns null.
Careful: that null blows up with a NullPointerException if you unbox it to int.
getOrDefault("azúcar", 0) returns 0 when the key is missing: much better.
Careful: that null blows up with a NullPointerException if you unbox it to int. getOrDefault("azúcar", 0) returns 0 when the key is missing: much better.
A Map is walked with entrySet(): each entry carries its key and its value.
It is the most used collection of all, and the most underused.
A Map is walked with entrySet(): each entry carries its key and its value. It is the most used collection of all, and the most underused.
Map<String, Integer> stock = new HashMap<>();stock.put("yerba", 12);stock.put("café", 5);stock.put("yerba", 20); // overwrites for (Map.Entry<String, Integer> entrada : stock.entrySet()) {System.out.println(entrada.getKey() + " → " + entrada.getValue());} The modern methods remove almost every if that used to be written by hand.
merge counts frequencies in one line and putIfAbsent stores only if the key is missing.
The modern methods remove almost every if that used to be written by hand. merge counts frequencies in one line and putIfAbsent stores only if the key is missing.
// Instead of: contador.put(p, contador.containsKey(p) ? contador.get(p) + 1 : 1);contador.merge(palabra, 1, Integer::sum); // Instead of: if (mapa.get(k) == null) mapa.put(k, v);mapa.putIfAbsent(clave, valor); computeIfAbsent creates the list only the first time the key appears.
It is the pattern for grouping values under a key without checking anything by hand.
computeIfAbsent creates the list only the first time the key appears. It is the pattern for grouping values under a key without checking anything by hand.
// Instead of: if (!mapa.containsKey(k)) mapa.put(k, new ArrayList<>());mapa.computeIfAbsent(clave, k -> new ArrayList<>()).add(valor); ArrayDeque works as a stack and as a queue; PriorityQueue serves the highest priority first.
You will implement them by hand later, but you can already use them today.
ArrayDeque works as a stack and as a queue; PriorityQueue serves the highest priority first. You will implement them by hand later, but you can already use them today.
Deque<String> pila = new ArrayDeque<>();pila.push("a");pila.push("b");System.out.println(pila.pop()); // b Queue<Integer> prioridad = new PriorityQueue<>(); Inside, a HashMap is an array of drawers called buckets.
With capacity 16 there are 16 buckets: the key decides which one holds each pair.
Inside, a HashMap is an array of drawers called buckets. With capacity 16 there are 16 buckets: the key decides which one holds each pair.
hashCode() turns the key into an integer: for "gato" it gives 3165397.
The bits are mixed and the & (n - 1) mask gives the bucket: number 5.
The pair is stored in bucket 5 without scanning anything: that is why get is O(1).
hashCode() turns the key into an integer: for "gato" it gives 3165397. The bits are mixed and the & (n - 1) mask gives the bucket: number 5. The pair is stored in bucket 5 without scanning anything: that is why get is O(1).
Now mesa: its hash also lands in bucket 5, even though it is another key.
That is a collision: both keys end up chained in the same bucket.
Inside the bucket, equals() compares the real key and decides which is which.
Now mesa: its hash also lands in bucket 5, even though it is another key. That is a collision: both keys end up chained in the same bucket. Inside the bucket, equals() compares the real key and decides which is which.
With get("mesa") the calculation repeats: the hash leads straight to bucket 5.
There equals() rules out gato and confirms mesa, without checking other buckets.
hashCode() picks the drawer; equals() picks the element inside the drawer.
With get("mesa") the calculation repeats: the hash leads straight to bucket 5. There equals() rules out gato and confirms mesa, without checking other buckets. hashCode() picks the drawer; equals() picks the element inside the drawer.
If hashCode() is badly written, the lookup lands in the wrong bucket.
The map answers null even though mesa is stored, and throws no exception.
That is the reason for the next lesson: equals() and hashCode() must agree.
If hashCode() is badly written, the lookup lands in the wrong bucket. The map answers null even though mesa is stored, and throws no exception. That is the reason for the next lesson: equals() and hashCode() must agree.
They are not only for using: you can also write your own generics.
A generic class declares its type parameters between <>, like Caja<T>.
They are not only for using: you can also write your own generics. A generic class declares its type parameters between <>, like Caja<T>.
public class Caja<T> {private T contenido; public void guardar(T contenido) { this.contenido = contenido; }public T sacar() { return contenido; }} Caja<String> cajaTexto = new Caja<>();cajaTexto.guardar("hola");String s = cajaTexto.sacar(); // no cast A generic class declares a type parameter between <>: Caja<T>.
T is a placeholder: the class works the same with any type.
A generic class declares a type parameter between <>: Caja<T>. T is a placeholder: the class works the same with any type.
When you use it you replace T with a concrete type: Caja<String> or Caja<Integer>.
Each version behaves as if it had been written for that type.
When you use it you replace T with a concrete type: Caja<String> or Caja<Integer>. Each version behaves as if it had been written for that type.
guardar("hola") goes in fine and sacar() returns a String, with no cast.
guardar(42) on a Caja<String> does not compile: the compiler defends the type.
The same class as Caja<Integer> does accept the 42.
guardar("hola") goes in fine and sacar() returns a String, with no cast. guardar(42) on a Caja<String> does not compile: the compiler defends the type. The same class as Caja<Integer> does accept the 42.
A generic method declares its own type parameter before the return type.
primero works for a List<String>, a List<Integer> or whatever you pass.
A generic method declares its own type parameter before the return type. primero works for a List<String>, a List<Integer> or whatever you pass.
public static <T> T primero(List<T> lista) {if (lista.isEmpty()) throw new NoSuchElementException("Empty list");return lista.get(0);} You can bound the type with extends to use the methods of the bound.
Here T must be comparable: that guarantees compareTo exists.
You can bound the type with extends to use the methods of the bound. Here T must be comparable: that guarantees compareTo exists.
// T must be comparable, so we can use compareTopublic static <T extends Comparable<T>> T maximo(List<T> lista) {T mayor = lista.get(0);for (T elemento : lista) {if (elemento.compareTo(mayor) > 0) mayor = elemento;}return mayor;} <T extends Comparable<T>> bounds the type: only comparable classes get in.
Integer and String implement Comparable and pass; a Perro class without compareTo does not.
That way you can call compareTo inside the method with total safety.
<T extends Comparable<T>> bounds the type: only comparable classes get in. Integer and String implement Comparable and pass; a Perro class without compareTo does not. That way you can call compareTo inside the method with total safety.
The method walks the list and compares each element with the largest found so far.
Each time compareTo is positive, the new element becomes the largest.
At the end it returns 12 and no cast was needed.
The method walks the list and compares each element with the largest found so far. Each time compareTo is positive, the new element becomes the largest. At the end it returns 12 and no cast was needed.
By convention, type parameters are a single capital letter.
T is type, E element, K and V key and value, R result.
By convention, type parameters are a single capital letter. T is type, E element, K and V key and value, R result.
Generics exist only at compile time: the JVM knows nothing about them.
It is type erasure: the compiler checks the types and then removes them.
Generics exist only at compile time: the JVM knows nothing about them. It is type erasure: the compiler checks the types and then removes them.
In the bytecode, List<String> and List<Integer> are the same thing: List.
That is why a.getClass() == b.getClass() is true: it is the same class at runtime.
In the bytecode, List<String> and List<Integer> are the same thing: List. That is why a.getClass() == b.getClass() is true: it is the same class at runtime.
That is where the limits come from: new T[10] is not allowed, at runtime T is unknown.
Generics speed up nothing: they bring the error forward to the moment you write the line.
That is where the limits come from: new T[10] is not allowed, at runtime T is unknown. Generics speed up nothing: they bring the error forward to the moment you write the line.
Generics bring the error forward from production to the moment you write the line.
At runtime, List<String> and List<Integer> print true: they are the same class.
Generics bring the error forward from production to the moment you write the line. At runtime, List<String> and List<Integer> print true: they are the same class.
List<String> a = new ArrayList<>();List<Integer> b = new ArrayList<>();System.out.println(a.getClass() == b.getClass()); // true // T[] arreglo = new T[10]; // not allowed: at runtime T is unknown java Borradotrue Insertion order and access by index: ArrayList.
Inserting and removing a lot at the ends: ArrayDeque.
Insertion order and access by index: ArrayList. Inserting and removing a lot at the ends: ArrayDeque.
Unique elements, order does not matter: HashSet.
Unique elements that stay sorted: TreeSet.
Unique elements, order does not matter: HashSet. Unique elements that stay sorted: TreeSet.
Key → value, very fast: HashMap; in key order TreeMap; in insertion order LinkedHashMap.
And to always take the highest priority first: PriorityQueue.
Key → value, very fast: HashMap; in key order TreeMap; in insertion order LinkedHashMap. And to always take the highest priority first: PriorityQueue.
Declaring with the class instead of the interface ties you to one implementation.
Your own objects without equals and hashCode store duplicates and get() returns null.
And modifying a collection while walking it throws ConcurrentModificationException.
Declaring with the class instead of the interface ties you to one implementation. Your own objects without equals and hashCode store duplicates and get() returns null. And modifying a collection while walking it throws ConcurrentModificationException.
mapa.get(k) without handling null ends in a NullPointerException: use getOrDefault.
LinkedList "because inserting is faster": in practice it is slower than ArrayList.
A mutable key gets lost in its old bucket; List.of(...) is immutable.
mapa.get(k) without handling null ends in a NullPointerException: use getOrDefault. LinkedList "because inserting is faster": in practice it is slower than ArrayList. A mutable key gets lost in its old bucket; List.of(...) is immutable.
The challenge: count how many times each word of a text appears.
You normalize, count with a Map, sort by frequency and count the distinct ones with a Set.
The challenge: count how many times each word of a text appears. You normalize, count with a Map, sort by frequency and count the distinct ones with a Set.
merge replaces the classic containsKey if: one line instead of four.
And there is no way to get the first appearance wrong.
merge replaces the classic containsKey if: one line instead of four. And there is no way to get the first appearance wrong.
public static Map<String, Integer> contar(String texto) {Map<String, Integer> frecuencias = new HashMap<>();// \p{L}+ takes runs of letters, accented ones includedfor (String palabra : texto.toLowerCase().split("[^\\p{L}]+")) {if (palabra.isBlank() || VACIAS.contains(palabra)) {continue;}// merge: if absent, store 1; if present, apply Integer::sumfrecuencias.merge(palabra, 1, Integer::sum);}return frecuencias;} The map’s keys are a Set: they give you the distinct words with no extra logic.
It sorts by descending frequency and, on a tie, alphabetically.
The map’s keys are a Set: they give you the distinct words with no extra logic. It sorts by descending frequency and, on a tie, alphabetically.
Set<String> distintas = frecuencias.keySet(); List<Map.Entry<String, Integer>> ordenadas = new ArrayList<>(frecuencias.entrySet());ordenadas.sort(Map.Entry.<String, Integer>comparingByValue().reversed().thenComparing(Map.Entry.comparingByKey())); // Bonus: group words by length, with computeIfAbsentMap<Integer, List<String>> porLongitud = new TreeMap<>();for (String palabra : distintas) {porLongitud.computeIfAbsent(palabra.length(), k -> new ArrayList<>()).add(palabra);} VACIAS is a Set because we only ask contains: on a Set it costs O(1).
On a List it would be O(n) per word: choosing well is a performance decision.
VACIAS is a Set because we only ask contains: on a Set it costs O(1). On a List it would be O(n) per word: choosing well is a performance decision.
private static final Set<String> VACIAS = Set.of("de", "la", "el", "y", "que", "en", "a", "los", "las", "un", "una", "es"); The JCF separates interfaces from implementations: always declare with the interface.
Map does not extend Collection and generics bring the error forward to compile time.
The JCF separates interfaces from implementations: always declare with the interface. Map does not extend Collection and generics bring the error forward to compile time.
In a HashMap, hashCode() picks the bucket and equals() picks the element.
Picking the right collection is a performance decision. The programs are in the course repo.
In a HashMap, hashCode() picks the bucket and equals() picks the element. Picking the right collection is a performance decision. The programs are in the course repo.