Java ya lo trae todo
Más adelante vas a implementar listas, pilas y colas a mano para entender cómo funcionan. Pero en el día a día no hace falta: Java lo trae todo, optimizado durante treinta años.
Lo vas a implementar a mano
TAD ListaTAD PilaTAD Cola En las próximas lecciones, para ver cómo funcionan por dentro
Java ya lo trae
ArrayListHashMapArrayDeque Treinta años de optimización y millones de aplicaciones
Usar una herramienta no es lo mismo que entenderla
Bien: el tipo es la interfaz
List<String> nombres = new ArrayList<>(); Map<String, Integer> stock = new HashMap<>(); Mal: te atás a la implementación
ArrayList<String> nombres = new ArrayList<>(); Cambiar a LinkedList es tocar una palabra
List<String> nombres = new LinkedList<>(); entrySet()
for (Map.Entry<String, Integer> e : stock.entrySet()) Cada entrada trae getKey() y getValue()
merge
contador.merge(palabra, 1, Integer::sum); Cuenta frecuencias sin ningún if
getOrDefault
stock.getOrDefault("azúcar", 0) Un valor por defecto en lugar de null
putIfAbsent
mapa.putIfAbsent(clave, valor); Guarda solo si la clave falta
computeIfAbsent
mapa.computeIfAbsent(k, x -> new ArrayList<>()).add(v); Arma un mapa de listas
ArrayDeque
Pila y cola
Inserta y saca por los extremos en O(1)
PriorityQueue
Sale el de mayor prioridad
No el que llegó primero
Los vas a implementar a mano en TAD Pila y TAD Cola
Clase genérica
public class Caja<T> El parámetro de tipo va entre <> después del nombre
Método genérico
public static <T> T primero(List<T> lista) Su propio parámetro de tipo, antes del retorno
Tipo acotado
<T extends Comparable<T>> Para poder llamar a compareTo con seguridad
Por convención, una letra mayúscula
T · type E · element K · key V · value R · result Los genéricos existen solo en tiempo de compilación
List<String> == List<Integer> → List ArrayList ArrayDeque HashSet TreeSet HashMap TreeMap LinkedHashMap PriorityQueue 1 Paso
Normalizar el texto
Minúsculas, sin puntuación
2 Paso
Contar con un Map
Map<String, Integer>
3 Paso
Ordenar por frecuencia
Descendente y luego alfabético
4 Paso
Palabras distintas
Las claves, como Set
5 Paso
Ignorar las vacías
de, la, el, y, que…
contains sobre VACIAS
Set · O(1) List · O(n)
Programas ejecutables de cada sección
Más adelante vas a implementar listas, pilas y colas a mano para entender cómo funcionan.
Pero en el día a día no hace falta: Java lo trae todo, optimizado durante treinta años.
Más adelante vas a implementar listas, pilas y colas a mano para entender cómo funcionan. Pero en el día a día no hace falta: Java lo trae todo, optimizado durante treinta años.
Cuando alguien diga "usá un HashMap", vas a saber que hay un arreglo y colisiones.
Esa es la diferencia entre usar una herramienta y entenderla.
Cuando alguien diga "usá un HashMap", vas a saber que hay un arreglo y colisiones. Esa es la diferencia entre usar una herramienta y entenderla.
Todo el framework nace de una jerarquía de interfaces, no de clases.
Iterable permite el for-each y Collection guarda elementos sueltos.
Todo el framework nace de una jerarquía de interfaces, no de clases. Iterable permite el for-each y Collection guarda elementos sueltos.
De Collection cuelgan tres familias: List, Set y Queue.
Cada una es una interfaz: el contrato, lo que luego llamarás TAD.
De Collection cuelgan tres familias: List, Set y Queue. Cada una es una interfaz: el contrato, lo que luego llamarás TAD.
Las clases concretas son las implementaciones: ArrayList, HashSet, ArrayDeque…
Cada una elige otra estructura por dentro: arreglo, tabla hash, árbol o nodos.
Las clases concretas son las implementaciones: ArrayList, HashSet, ArrayDeque… Cada una elige otra estructura por dentro: arreglo, tabla hash, árbol o nodos.
Map queda afuera: guarda asociaciones clave → valor, no elementos sueltos.
Por eso no extiende Collection y su interfaz es distinta.
Map queda afuera: guarda asociaciones clave → valor, no elementos sueltos. Por eso no extiende Collection y su interfaz es distinta.
La regla concreta: el tipo de la variable es la interfaz, no la implementación.
Cambiar a LinkedList es tocar una sola palabra.
La regla concreta: el tipo de la variable es la interfaz, no la implementación. Cambiar a LinkedList es tocar una sola palabra.
// Bien: el tipo de la variable es la interfazList<String> nombres = new ArrayList<>();Map<String, Integer> stock = new HashMap<>(); Si declarás ArrayList, quien use un método propio de ArrayList te obliga a tocar todo.
Es el mismo principio del TAD: programar contra el contrato, no contra el detalle.
Si declarás ArrayList, quien use un método propio de ArrayList te obliga a tocar todo. Es el mismo principio del TAD: programar contra el contrato, no contra el detalle.
// Mal: te atás a la implementaciónArrayList<String> nombres = new ArrayList<>(); Antes de Java 5 las colecciones guardaban Object: todo entraba y todo compilaba.
Agregás un texto y un número a la misma lista: compila perfecto.
El error llega recién al castear: ClassCastException, en ejecución y con usuarios.
Antes de Java 5 las colecciones guardaban Object: todo entraba y todo compilaba. Agregás un texto y un número a la misma lista: compila perfecto. El error llega recién al castear: ClassCastException, en ejecución y con usuarios.
Con genéricos la colección declara qué guarda: List<String>.
Agregar un número ni siquiera compila: el error aparece en tu IDE, antes de ejecutar.
Y al leer, el casteo desaparece: el compilador ya sabe que sale un String.
Con genéricos la colección declara qué guarda: List<String>. Agregar un número ni siquiera compila: el error aparece en tu IDE, antes de ejecutar. Y al leer, el casteo desaparece: el compilador ya sabe que sale un String.
El <> vacío de la derecha se llama diamante.
Le dice al compilador: el mismo tipo que declaré a la izquierda.
new ArrayList<String>() no está mal, solo es redundante.
El <> vacío de la derecha se llama diamante. Le dice al compilador: el mismo tipo que declaré a la izquierda. new ArrayList<String>() no está mal, solo es redundante.
List mantiene el orden de inserción y permite duplicados.
get(1) accede por índice y size() cuenta todo, incluidos los repetidos.
List mantiene el orden de inserción y permite duplicados. get(1) accede por índice y size() cuenta todo, incluidos los repetidos.
Set no permite duplicados: agregás java, poo y otra vez java.
El tercer java ya estaba: add lo ignora y el tamaño queda en 2.
Set no permite duplicados: agregás java, poo y otra vez java. El tercer java ya estaba: add lo ignora y el tamaño queda en 2.
HashSet no garantiza orden; LinkedHashSet lo conserva; TreeSet mantiene todo ordenado.
Cuidado: tus propias clases necesitan equals() y hashCode() para que el Set detecte duplicados.
HashSet no garantiza orden; LinkedHashSet lo conserva; TreeSet mantiene todo ordenado. Cuidado: tus propias clases necesitan equals() y hashCode() para que el Set detecte duplicados.
En un ArrayList, get(6) salta directo: una cuenta de dirección y listo.
En una LinkedList hay que seguir los enlaces, nodo por nodo, hasta llegar al 6.
Con 500 elementos serían 500 saltos: acceder por índice en una LinkedList es lento.
En un ArrayList, get(6) salta directo: una cuenta de dirección y listo. En una LinkedList hay que seguir los enlaces, nodo por nodo, hasta llegar al 6. Con 500 elementos serían 500 saltos: acceder por índice en una LinkedList es lento.
Los elementos de un ArrayList están pegados en memoria: la caché del CPU los trae juntos.
Los nodos de una LinkedList están dispersos por el Heap: más fallos de caché.
Por eso en la práctica LinkedList casi siempre pierde: ArrayList, salvo que midas lo contrario.
Los elementos de un ArrayList están pegados en memoria: la caché del CPU los trae juntos. Los nodos de una LinkedList están dispersos por el Heap: más fallos de caché. Por eso en la práctica LinkedList casi siempre pierde: ArrayList, salvo que midas lo contrario.
put(clave, valor) guarda una asociación: la clave apunta a su valor.
Primero yerba → 12 y después café → 5: dos entradas.
Si repetís una clave, put la sobrescribe: las claves son únicas.
put(clave, valor) guarda una asociación: la clave apunta a su valor. Primero yerba → 12 y después café → 5: dos entradas. Si repetís una clave, put la sobrescribe: las claves son únicas.
get("yerba") busca la clave y devuelve su valor: 20.
get("azúcar") no encuentra la clave y devuelve null.
get("yerba") busca la clave y devuelve su valor: 20. get("azúcar") no encuentra la clave y devuelve null.
Cuidado: ese null explota con NullPointerException si lo desempaquetás a int.
getOrDefault("azúcar", 0) devuelve 0 cuando la clave falta: mucho mejor.
Cuidado: ese null explota con NullPointerException si lo desempaquetás a int. getOrDefault("azúcar", 0) devuelve 0 cuando la clave falta: mucho mejor.
Un Map se recorre con entrySet(): cada entrada trae su clave y su valor.
Es la colección más usada de todas, y la que más se subutiliza.
Un Map se recorre con entrySet(): cada entrada trae su clave y su valor. Es la colección más usada de todas, y la que más se subutiliza.
Map<String, Integer> stock = new HashMap<>();stock.put("yerba", 12);stock.put("café", 5);stock.put("yerba", 20); // sobrescribe for (Map.Entry<String, Integer> entrada : stock.entrySet()) {System.out.println(entrada.getKey() + " → " + entrada.getValue());} Los métodos modernos eliminan casi todos los if que se escribían a mano.
merge cuenta frecuencias en una línea y putIfAbsent guarda solo si la clave falta.
Los métodos modernos eliminan casi todos los if que se escribían a mano. merge cuenta frecuencias en una línea y putIfAbsent guarda solo si la clave falta.
// En lugar de: contador.put(p, contador.containsKey(p) ? contador.get(p) + 1 : 1);contador.merge(palabra, 1, Integer::sum); // En lugar de: if (mapa.get(k) == null) mapa.put(k, v);mapa.putIfAbsent(clave, valor); computeIfAbsent crea la lista solo la primera vez que aparece la clave.
Es el patrón para agrupar valores bajo una clave sin chequear nada a mano.
computeIfAbsent crea la lista solo la primera vez que aparece la clave. Es el patrón para agrupar valores bajo una clave sin chequear nada a mano.
// En lugar de: if (!mapa.containsKey(k)) mapa.put(k, new ArrayList<>());mapa.computeIfAbsent(clave, k -> new ArrayList<>()).add(valor); ArrayDeque sirve como pila y como cola; PriorityQueue saca primero al de mayor prioridad.
Los vas a implementar a mano más adelante, pero ya podés usarlos hoy.
ArrayDeque sirve como pila y como cola; PriorityQueue saca primero al de mayor prioridad. Los vas a implementar a mano más adelante, pero ya podés usarlos hoy.
Deque<String> pila = new ArrayDeque<>();pila.push("a");pila.push("b");System.out.println(pila.pop()); // b Queue<Integer> prioridad = new PriorityQueue<>(); Por dentro, un HashMap es un arreglo de cajones llamados buckets.
Con capacidad 16 hay 16 buckets: la clave decide en cuál vive cada par.
Por dentro, un HashMap es un arreglo de cajones llamados buckets. Con capacidad 16 hay 16 buckets: la clave decide en cuál vive cada par.
hashCode() convierte la clave en un entero: para "gato" da 3165397.
Se mezclan los bits y la máscara & (n - 1) da el bucket: el 5.
El par se guarda en el bucket 5 sin recorrer nada: por eso get es O(1).
hashCode() convierte la clave en un entero: para "gato" da 3165397. Se mezclan los bits y la máscara & (n - 1) da el bucket: el 5. El par se guarda en el bucket 5 sin recorrer nada: por eso get es O(1).
Ahora mesa: su hash también cae en el bucket 5, siendo otra clave.
Es una colisión: las dos claves quedan encadenadas en el mismo bucket.
Dentro del bucket, equals() compara la clave real y decide cuál es cuál.
Ahora mesa: su hash también cae en el bucket 5, siendo otra clave. Es una colisión: las dos claves quedan encadenadas en el mismo bucket. Dentro del bucket, equals() compara la clave real y decide cuál es cuál.
Con get("mesa") se repite la cuenta: el hash lleva directo al bucket 5.
Ahí equals() descarta gato y confirma mesa, sin mirar los otros buckets.
hashCode() elige el cajón; equals() elige el elemento dentro del cajón.
Con get("mesa") se repite la cuenta: el hash lleva directo al bucket 5. Ahí equals() descarta gato y confirma mesa, sin mirar los otros buckets. hashCode() elige el cajón; equals() elige el elemento dentro del cajón.
Si hashCode() está mal hecho, la búsqueda cae en el bucket equivocado.
El mapa responde null aunque mesa esté guardado, y no lanza ninguna excepción.
Es el motivo de la próxima lección: equals() y hashCode() deben ser coherentes.
Si hashCode() está mal hecho, la búsqueda cae en el bucket equivocado. El mapa responde null aunque mesa esté guardado, y no lanza ninguna excepción. Es el motivo de la próxima lección: equals() y hashCode() deben ser coherentes.
No son solo para usar: también podés escribir tus propios genéricos.
Una clase genérica declara sus parámetros de tipo entre <>, como Caja<T>.
No son solo para usar: también podés escribir tus propios genéricos. Una clase genérica declara sus parámetros de tipo entre <>, como 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(); // sin casteo Una clase genérica declara un parámetro de tipo entre <>: Caja<T>.
T es un hueco: la clase funciona igual con cualquier tipo.
Una clase genérica declara un parámetro de tipo entre <>: Caja<T>. T es un hueco: la clase funciona igual con cualquier tipo.
Al usarla reemplazás T por un tipo concreto: Caja<String> o Caja<Integer>.
Cada versión se comporta como si estuviera escrita para ese tipo.
Al usarla reemplazás T por un tipo concreto: Caja<String> o Caja<Integer>. Cada versión se comporta como si estuviera escrita para ese tipo.
guardar("hola") entra sin problema y sacar() devuelve un String, sin casteo.
guardar(42) en una Caja<String> no compila: el compilador defiende el tipo.
La misma clase como Caja<Integer> sí acepta el 42.
guardar("hola") entra sin problema y sacar() devuelve un String, sin casteo. guardar(42) en una Caja<String> no compila: el compilador defiende el tipo. La misma clase como Caja<Integer> sí acepta el 42.
Un método genérico declara su propio parámetro de tipo antes del retorno.
primero sirve para una List<String>, una List<Integer> o la que le pases.
Un método genérico declara su propio parámetro de tipo antes del retorno. primero sirve para una List<String>, una List<Integer> o la que le pases.
public static <T> T primero(List<T> lista) {if (lista.isEmpty()) throw new NoSuchElementException("Lista vacía");return lista.get(0);} Podés acotar el tipo con extends para usar los métodos del tipo acotado.
Acá T debe ser comparable: así compareTo está garantizado.
Podés acotar el tipo con extends para usar los métodos del tipo acotado. Acá T debe ser comparable: así compareTo está garantizado.
// T tiene que ser comparable, así podemos usar 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>> acota el tipo: solo entran clases que se pueden comparar.
Integer y String implementan Comparable y pasan; una clase Perro sin compareTo no.
Así podés llamar a compareTo dentro del método con total seguridad.
<T extends Comparable<T>> acota el tipo: solo entran clases que se pueden comparar. Integer y String implementan Comparable y pasan; una clase Perro sin compareTo no. Así podés llamar a compareTo dentro del método con total seguridad.
El método recorre la lista y compara cada elemento con el mayor encontrado hasta ahora.
Cada vez que compareTo da positivo, el elemento nuevo pasa a ser el mayor.
Al terminar devuelve 12 y no hizo falta ningún casteo.
El método recorre la lista y compara cada elemento con el mayor encontrado hasta ahora. Cada vez que compareTo da positivo, el elemento nuevo pasa a ser el mayor. Al terminar devuelve 12 y no hizo falta ningún casteo.
Por convención, los parámetros de tipo son una sola letra mayúscula.
T es type, E element, K y V key y value, R result.
Por convención, los parámetros de tipo son una sola letra mayúscula. T es type, E element, K y V key y value, R result.
Los genéricos existen solo en tiempo de compilación: la JVM no sabe nada de ellos.
Es el borrado de tipos: el compilador verifica los tipos y después los elimina.
Los genéricos existen solo en tiempo de compilación: la JVM no sabe nada de ellos. Es el borrado de tipos: el compilador verifica los tipos y después los elimina.
En el bytecode, List<String> y List<Integer> son la misma cosa: List.
Por eso a.getClass() == b.getClass() da true: es la misma clase en ejecución.
En el bytecode, List<String> y List<Integer> son la misma cosa: List. Por eso a.getClass() == b.getClass() da true: es la misma clase en ejecución.
De ahí nacen las limitaciones: new T[10] no se puede, en ejecución no se sabe qué es T.
Los genéricos no aceleran nada: adelantan el error al momento de escribir la línea.
De ahí nacen las limitaciones: new T[10] no se puede, en ejecución no se sabe qué es T. Los genéricos no aceleran nada: adelantan el error al momento de escribir la línea.
Los genéricos adelantan el error de producción al momento de escribir la línea.
En ejecución, List<String> y List<Integer> imprimen true: son la misma clase.
Los genéricos adelantan el error de producción al momento de escribir la línea. En ejecución, List<String> y List<Integer> imprimen true: son la misma clase.
List<String> a = new ArrayList<>();List<Integer> b = new ArrayList<>();System.out.println(a.getClass() == b.getClass()); // true // T[] arreglo = new T[10]; // no se puede: en ejecución no se sabe qué es T java Borradotrue Orden de inserción y acceso por índice: ArrayList.
Insertar y borrar mucho en los extremos: ArrayDeque.
Orden de inserción y acceso por índice: ArrayList. Insertar y borrar mucho en los extremos: ArrayDeque.
Elementos únicos sin importar el orden: HashSet.
Elementos únicos y siempre ordenados: TreeSet.
Elementos únicos sin importar el orden: HashSet. Elementos únicos y siempre ordenados: TreeSet.
Clave → valor rapidísimo: HashMap; en orden de clave TreeMap; en orden de inserción LinkedHashMap.
Y para sacar siempre al de mayor prioridad: PriorityQueue.
Clave → valor rapidísimo: HashMap; en orden de clave TreeMap; en orden de inserción LinkedHashMap. Y para sacar siempre al de mayor prioridad: PriorityQueue.
Declarar con la clase en vez de la interfaz te ata a una implementación.
Objetos propios sin equals y hashCode guardan duplicados y get() devuelve null.
Y modificar una colección mientras se recorre lanza ConcurrentModificationException.
Declarar con la clase en vez de la interfaz te ata a una implementación. Objetos propios sin equals y hashCode guardan duplicados y get() devuelve null. Y modificar una colección mientras se recorre lanza ConcurrentModificationException.
mapa.get(k) sin contemplar null termina en NullPointerException: usá getOrDefault.
LinkedList "porque insertar es más rápido": en la práctica es más lenta que ArrayList.
Una clave mutable queda perdida en el bucket viejo; List.of(...) es inmutable.
mapa.get(k) sin contemplar null termina en NullPointerException: usá getOrDefault. LinkedList "porque insertar es más rápido": en la práctica es más lenta que ArrayList. Una clave mutable queda perdida en el bucket viejo; List.of(...) es inmutable.
El desafío: contar cuántas veces aparece cada palabra de un texto.
Normalizás, contás con un Map, ordenás por frecuencia y contás las distintas con un Set.
El desafío: contar cuántas veces aparece cada palabra de un texto. Normalizás, contás con un Map, ordenás por frecuencia y contás las distintas con un Set.
merge reemplaza el clásico if con containsKey: una línea en lugar de cuatro.
Y no hay forma de equivocarse en el caso de la primera aparición.
merge reemplaza el clásico if con containsKey: una línea en lugar de cuatro. Y no hay forma de equivocarse en el caso de la primera aparición.
public static Map<String, Integer> contar(String texto) {Map<String, Integer> frecuencias = new HashMap<>();// \p{L}+ toma secuencias de letras, incluidas las acentuadasfor (String palabra : texto.toLowerCase().split("[^\\p{L}]+")) {if (palabra.isBlank() || VACIAS.contains(palabra)) {continue;}// merge: si no está, guarda 1; si está, aplica Integer::sumfrecuencias.merge(palabra, 1, Integer::sum);}return frecuencias;} Las claves del mapa son un Set: te dan las palabras distintas sin lógica extra.
Se ordena por frecuencia descendente y, a igual frecuencia, alfabéticamente.
Las claves del mapa son un Set: te dan las palabras distintas sin lógica extra. Se ordena por frecuencia descendente y, a igual frecuencia, alfabéticamente.
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: agrupar palabras por su longitud, con computeIfAbsentMap<Integer, List<String>> porLongitud = new TreeMap<>();for (String palabra : distintas) {porLongitud.computeIfAbsent(palabra.length(), k -> new ArrayList<>()).add(palabra);} VACIAS es un Set porque solo preguntamos contains: en un Set cuesta O(1).
En una List serían O(n) por cada palabra: elegir bien es una decisión de rendimiento.
VACIAS es un Set porque solo preguntamos contains: en un Set cuesta O(1). En una List serían O(n) por cada palabra: elegir bien es una decisión de rendimiento.
private static final Set<String> VACIAS = Set.of("de", "la", "el", "y", "que", "en", "a", "los", "las", "un", "una", "es"); El JCF separa interfaces de implementaciones: declarás siempre con la interfaz.
Map no extiende Collection y los genéricos adelantan el error al compilar.
El JCF separa interfaces de implementaciones: declarás siempre con la interfaz. Map no extiende Collection y los genéricos adelantan el error al compilar.
En un HashMap, hashCode() elige el bucket y equals() elige el elemento.
Elegir bien la colección es una decisión de rendimiento. Los programas están en el repo del curso.
En un HashMap, hashCode() elige el bucket y equals() elige el elemento. Elegir bien la colección es una decisión de rendimiento. Los programas están en el repo del curso.