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

java collections framework español

Question

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?

Answer 1

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.

Answer 2

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)

Answer 3

Este sitio web es bastante bueno pero no específico de Java: http://bigocheatsheet.com/

Answer 4

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 recopilació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)