¿Resumen de Big-O para implementaciones de Java Collections Framework? [cerrado]
Es posible que pronto imparta un "curso intensivo de Java". Si bien probablemente sea seguro asumir que los miembros de la audiencia conocerán la notación Big-O, probablemente no sea seguro asumir que sabrán cuál es el orden de las distintas operaciones en las distintas implementaciones de la colección.
Podría tomarme un tiempo para generar una matriz resumida yo mismo, pero si ya está disponible en algún lugar de dominio público, me gustaría reutilizarla (con el crédito adecuado, por supuesto).
¿Alguien tiene algún consejo?
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:
- La descripción general de colecciones tiene una bonita tabla de resumen.
- El esquema anotado enumera todas las implementaciones en una página.
Este sitio web es bastante bueno pero no específico de Java: http://bigocheatsheet.com/
