¿Un resumen de Big-O para las implementaciones de Java Collections Framework?

Es posible que enseñe pronto un “curso acelerado de Java”. Si bien es seguro suponer que los miembros de la audiencia conocerán la notación Big-O, probablemente no sea seguro suponer que sabrán cuál es el orden de las diversas operaciones en varias implementaciones de colecciones.

Podría tomarme un tiempo para generar una matriz de resumen, pero si ya está en el dominio público en alguna parte, me gustaría reutilizarla (con el crédito adecuado, por supuesto).

Alguien tiene punteros?

Este sitio web es bastante bueno pero no específico de Java: http://bigocheatsheet.com/ Aquí hay una imagen en caso de que este enlace no funcione

El libro Java Generics and Collections tiene esta información (páginas: 188, 211, 222, 240).

Implementaciones de lista:

get add contains next remove(0) iterator.remove ArrayList O(1) O(1) O(n) O(1) O(n) O(n) LinkedList O(n) O(1) O(n) O(1) O(1) O(1) CopyOnWrite-ArrayList O(1) O(n) O(n) O(1) O(n) O(n) 

Establecer implementaciones:

  add contains next notes HashSet O(1) O(1) O(h/n) h is the table capacity LinkedHashSet O(1) O(1) O(1) CopyOnWriteArraySet O(n) O(n) O(1) EnumSet O(1) O(1) O(1) TreeSet O(log n) O(log n) O(log n) ConcurrentSkipListSet O(log n) O(log n) O(1) 

Implementaciones de mapas:

  get containsKey next Notes HashMap O(1) O(1) O(h/n) h is the table capacity LinkedHashMap O(1) O(1) O(1) IdentityHashMap O(1) O(1) O(h/n) h is the table capacity EnumMap O(1) O(1) O(1) TreeMap O(log n) O(log n) O(log n) ConcurrentHashMap O(1) O(1) O(h/n) h is the table capacity ConcurrentSkipListMap O(log n) O(log n) O(1) 

Implementaciones de cola:

  offer peek poll size PriorityQueue O(log n) O(1) O(log n) O(1) ConcurrentLinkedQueue O(1) O(1) O(1) O(n) ArrayBlockingQueue O(1) O(1) O(1) O(1) LinkedBlockingQueue O(1) O(1) O(1) O(1) PriorityBlockingQueue O(log n) O(1) O(log n) O(1) DelayQueue O(log n) O(1) O(log n) O(1) LinkedList O(1) O(1) O(1) O(1) ArrayDeque O(1) O(1) O(1) O(1) LinkedBlockingDeque O(1) O(1) O(1) O(1) 

La parte inferior del javadoc para el paquete java.util contiene algunos buenos enlaces:

  • El resumen de colecciones tiene una bonita tabla de resumen.
  • El Esquema Anotado enumera todas las implementaciones en una página.

Los Javadocs de Sun para cada clase de colección generalmente le dirán exactamente lo que desea. HashMap , por ejemplo:

Esta implementación proporciona un rendimiento en tiempo constante para las operaciones básicas (get y put), suponiendo que la función hash dispersa los elementos correctamente entre los cubos. La iteración sobre las vistas de recostackción requiere un tiempo proporcional a la “capacidad” de la instancia de HashMap (el número de segmentos) más su tamaño (el número de asignaciones de valores-clave).

TreeMap :

Esta implementación proporciona un costo de tiempo de registro (n) garantizado para las operaciones containsKey, get, put y remove.

TreeSet :

Esta implementación proporciona un costo de tiempo de registro (n) garantizado para las operaciones básicas (agregar, eliminar y contener).

(énfasis mío)

El tipo anterior dio una comparación para HashMap / HashSet vs. TreeMap / TreeSet.

Hablaré sobre ArrayList vs. LinkedList:

Lista de arreglo:

  • O (1) get()
  • amortizado O (1) add()
  • si inserta o elimina un elemento en el medio utilizando ListIterator.add() o Iterator.remove() , será O (n) para desplazar todos los elementos siguientes

Lista enlazada:

  • O (n) get()
  • O (1) add()
  • si inserta o elimina un elemento en el medio usando ListIterator.add() o Iterator.remove() , será O (1)